Editorial for DMOPC '22 Contest 3 P3 - Ina's Takodachis
Submitting an official solution before solving the problem yourself is a bannable offence.
Let's deal with the special case first:
- If , Ina would just need to perform the operation times to even out the two heights.
- Otherwise, it is impossible.
For every other , 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 time.
In this subtask, it is sufficient to continuously increment from until either a working height has been found or we have reached some pre-determined upper bound. Given that the maximum of is , a generous upper bound is , or . The total runtime complexity of the brute force is .
When , the process is the same as the previous subtask.
For all other , observe the following lemma: If some height works, then also works when ; otherwise, also works.
We once again set upper . Using the lemma, instead of checking all the heights from to , we can check plus each modulo of . After finding a modulo that works, we can then find the minimum height that works by decrementing in step of if , or in step of otherwise. The decrementing process can be done efficiently using a binary search. This reduces the runtime to , which is sufficient to get the full score.