Editorial for DMOPC '22 Contest 3 P3 - Ina's Takodachis

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: kdrkdr

Subtask 1

Let's deal with the special case N = 2 first:

  • If h_1 \ge h_2, Ina would just need to perform the operation h_2 - h_1 times to even out the two heights.
  • Otherwise, it is impossible.

For every other N, we can check if Ina can set all Takodachis to some height using the following process: First, we can calculate the number of operations she needs to perform. Then we iterate starting from the end, and greedily use as many +2s as possible, while fixing parity issues with the +1s. Throughout that process, it is important to make sure that at no point does the number of +1s used exceeds the number of +2s used. This process takes \mathcal O(N) time.

In this subtask, it is sufficient to continuously increment from max(h_i) until either a working height has been found or we have reached some pre-determined upper bound. Given that the maximum of h_i is 10^3, a generous upper bound H is 10 \times h_i, or 10^4. The total runtime complexity of the brute force is \mathcal O(NH).

Subtask 2

When N = 2, the process is the same as the previous subtask.

For all other N, observe the following lemma: If some height x works, then x+2 also works when 3 \mid N; otherwise, x+6 also works.

We once again set upper H = 10 \times h_i = 10^{13}. Using the lemma, instead of checking all the heights from \max(h_i) to H, we can check H plus each modulo of 6. After finding a modulo that works, we can then find the minimum height that works by decrementing in step of 2 if 3 \mid N, or in step of 6 otherwise. The decrementing process can be done efficiently using a binary search. This reduces the runtime to \mathcal O(N \log H), which is sufficient to get the full score.


There are no comments at the moment.