## 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

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 .