Codeforces Round 697 (Div. 3)

Solutions for Codeforces Round 697 (Div. 3) (contest 1475). 6/7 problems verified against sample I/O. Difficulty range: 900-1900.

7 items

Codeforces Round 697 (Div. 3)

Type: Div. 3 | Problems: 7 | Verified: 6/7 | Rating range: 900-1900 | Time: 15m 30s

Problem	Name	Rating	Tags	Solve Time	Verified
A	Odd Divisor	900	math, number-theory	1m 53s	✓
B	New Year's Number	900	brute-force, dp, math	3m 41s	✓
C	Ball in Berland	1400	combinatorics, graphs, math	2m 54s	✗
D	Cleaning the Phone	1800	binary-search, dp, sortings	1m 42s	✓
E	Advertising Agency	1600	combinatorics, math, sortings	1m 46s	✓
F	Unusual Matrix	1900	2-sat, brute-force, constructive-algorithms	2m 3s	✓
G	Strange Beauty	1900	dp, math, number-theory	1m 31s	✓

Practice › Codeforces Solutions › Codeforces Round 697 (Div. 3) ›

CF 1475F - Unusual Matrix

We are given two square binary matrices of the same size, called a and b. Each element is either 0 or 1. The allowed operations are flipping an entire row or flipping an entire column, where flipping means XORing each element with 1.

Practice › Codeforces Solutions › Codeforces Round 697 (Div. 3) ›

CF 1475G - Strange Beauty

We are given an array of integers, and Polycarp defines an array as beautiful if, for every pair of distinct elements, one divides the other. In other words, for all $i ne j$, either $ai$ divides $aj$ or $aj$ divides $ai$.

Practice › Codeforces Solutions › Codeforces Round 697 (Div. 3) ›

CF 1475E - Advertising Agency

Masha has a list of bloggers, each with a certain number of followers, and she wants to hire exactly k of them to maximize the total audience reached. The input gives n, the total bloggers, k, the number she can hire, and an array a of length n with each blogger's follower count.

Practice › Codeforces Solutions › Codeforces Round 697 (Div. 3) ›

CF 1475B - New Year's Number

We are given a number $n$, and we want to know whether it can be built by adding together some number of 2020s and some number of 2021s.

Practice › Codeforces Solutions › Codeforces Round 697 (Div. 3) ›

CF 1475D - Cleaning the Phone

We are given a phone with a list of installed apps. Each app consumes some amount of memory and also has a “cost” measured in convenience loss if we delete it. Every app contributes either 1 or 2 convenience points.

Practice › Codeforces Solutions › Codeforces Round 697 (Div. 3) ›

CF 1475C - Ball in Berland

I can't reliably diagnose this one from the sample alone because the sample input/output pair does not identify the problem.

Practice › Codeforces Solutions › Codeforces Round 697 (Div. 3) ›

CF 1475A - Odd Divisor

We are asked to determine if a given integer $n$ has an odd divisor greater than one. In other words, we want to know if there exists some odd number $x 1$ that divides $n$ evenly. If $n$ is divisible by such a number, the answer is "YES"; otherwise, it is "NO".