Codeforces Round #702 Div3 Solution

A. Dense Array

Solution

If found the $\frac{max}{min}>2$ then just insert $2\cdot{min}$ in array.

Code

Submission #111639857 - Codeforces
Codeforces. Programming competitions and contests, programming community

B. Balanced Remainders

Solution

Let find one of i which make $c_i>\frac{n}{3}$. Then move $c_i-\frac{n}{3}$ numbers to $c_{i+1}$. Then i++, and check if $c_i>\frac{n}{3}$ again.

The only small trap: this operation needs to be done 2 rounds. (which means do i++ 6 times.). Because in 1st round, the number of $c_i$ is not enough for $c_{i+1}$, most number is in $c_{i+2}$.

Code

Submission #111642201 - Codeforces
Codeforces. Programming competitions and contests, programming community

C. Sum of Cubes

Solution

Brute force +  binary search. Violence enumerates $a$ between 1 and 10000. Then binary search b for $x-a^3$.

There is another solution (I not tried this). Violence enumerates $a$. But get a inaccurate $b'$ directly by $\sqrt[3]{x-a^3}$. Then enumerate b from $b'-5$ to $b'+5$

Code

Submission #111643445 - Codeforces
Codeforces. Programming competitions and contests, programming community

D. Permutation Transformation

Solution

Sort $a$. Then scan the $a$. For each $a[i]$ we scan now, it must be the new node of the tree. After that, we just sort $a$ by index again.

Code

Submission #111644826 - Codeforces
Codeforces. Programming competitions and contests, programming community

E. Accidental Victory

Solution

Sort $a$. For each people $i$. let count the total tokens before $i$ (inclusive). Then just check if the total tokens can bigger or equal than people $i+1$. If so, can win. Otherwise fail.

But be careful. If some $i$ failed. Then all the people which $j<i$ failed.

Code

Submission #111646868 - Codeforces
Codeforces. Programming competitions and contests, programming community

F. Equalize the Array

Solution

Count the number of occurrences of each number. And sort the count from largest to smallest. And then scan the code.

When scanning $i^{th}$ number, remove all the number after $i^{th}$ count. Because all these count smaller than $count[i]$. Only can occurrence 0 times.

Similarly, remove number before $i^{th}$ count until it occurrence only $count[i]$ times.

Code

Submission #111648672 - Codeforces
Codeforces. Programming competitions and contests, programming community

G. Old Floppy Drive

Solution

binary search + implementation.

Firstly, let's focus on the case no need second round (back to 1). Then calculate prefix max value of $a$ to array $max$. So just binary search the first point which is larger or equal than $x$.

If one round is not enough. Then we check the sum of $a$. If $sum\leq{0}$, then no way, return -1.

If need more than one round and can have solution. Then find the first round $r$ that make $x-r\cdot{sum}\leq{max[n]}$. Then binary search $x-r\cdot{sum}-{max[n]}$ in $max$

Code

Submission #111652034 - Codeforces
Codeforces. Programming competitions and contests, programming community