Editorial for DMOPC '22 Contest 2 P5 - Beautiful Bins - Olympiads Online Judge

Editorial for DMOPC '22 Contest 2 P5 - Beautiful Bins

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: 4fecta

First of all, note that since we have $A_i \ge 1$ $A_{i} \geq 1$ for all $i$ $i$ , any set of moves that results in a positive $B$ $B$ will always have an ordering of the moves such that none of the quantities ever go negative. Thus, the only thing that matters is the number of each move performed.

To reach a solution, consider maintaining the following two quantities at each index $i$ $i$ :

$l_i :=$ $l_{i} :=$ the number of balls that are moved from the range $[i, N]$ $[i, N]$ to the range $[1, i-1]$ $[1, i - 1]$ .
$r_i :=$ $r_{i} :=$ the number of balls that are moved from the range $[1, i-1]$ $[1, i - 1]$ to the range $[i, N]$ $[i, N]$ .

Note that by definition, we must have $l_i, r_i \ge 0$ $l_{i}, r_{i} \geq 0$ , and furthermore $r_i-l_i = \sum_{k=1}^{i-1} (A_k-B_k)$ $r_{i} - l_{i} = \sum_{k = 1}^{i - 1} (A_{k} - B_{k})$ since the number of balls in each segment must be the same. Initially, $l_2 = B_1-A_1$ $l_{2} = B_{1} - A_{1}$ and $r_2 = 0$ $r_{2} = 0$ . To obtain the values of $l_i$ $l_{i}$ and $r_i$ $r_{i}$ for larger $i$ $i$ , consider performing $s$ $s$ moves centered at index $i$ $i$ and $x$ $x$ moves that move a ball from $[1, i-1]$ $[1, i - 1]$ to $i$ $i$ . Clearly $s$ $s$ should be no larger than $l_i$ $l_{i}$ and $x$ $x$ should be no larger than $r_i$ $r_{i}$ , and we must also have $A_i-2s+x \le B_i$ $A_{i} - 2 s + x \leq B_{i}$ since there is no other way to get rid of any excess balls at index $i$ $i$ .

After these moves are determined, we have nice formulas for $l_{i+1}$ $l_{i + 1}$ and $r_{i+1}$ $r_{i + 1}$ :

$l_{i+1} = l_i+s-x+B_i-A_i$ $l_{i + 1} = l_{i} + s - x + B_{i} - A_{i}$
$r_{i+1} = r_i+s-x$ $r_{i + 1} = r_{i} + s - x$

Note that we add $s$ $s$ to $r_i$ $r_{i}$ since we introduce $s$ $s$ new balls that move from $i$ $i$ to $[i+1, N]$ $[i + 1, N]$ , and we subtract $x$ $x$ since we no longer consider the $x$ $x$ balls that move from $[1,i-1]$ $[1, i - 1]$ to $i$ $i$ . The formula for $l_{i+1}$ $l_{i + 1}$ can be derived in a similar manner.

If we consider all possible values of $s$ $s$ and $x$ $x$ at every index, then it is only possible if we can reach $l_N = 0$ $l_{N} = 0$ and $r_N = B_N-A_N$ $r_{N} = B_{N} - A_{N}$ in the end. The issue, however, is that this is far too slow on any reasonably sized input. To speed the solution up, note that the possible values of $l_i$ $l_{i}$ and $r_i$ $r_{i}$ always form a consecutive interval of integers. Thus, it suffices to only track the minimum and maximum possible values of $l_i$ $l_{i}$ and $r_i$ $r_{i}$ at each index. These may be computed greedily in $\mathcal{O}(1)$ $O (1)$ time each, which is fast enough for the given constraints.

Time Complexity: $\mathcal{O}(N)$ $O (N)$

Credit goes to azeng for discovering this elegant solution.

Comments

There are no comments at the moment.