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

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

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

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

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

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

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