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

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

#### Subtask 1

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 `+2`

s as possible, while fixing parity issues with the `+1`

s. Throughout that process, it is important to make sure that at no point does the number of `+1`

s used exceeds the number of `+2`

s 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 .

#### Subtask 2

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.

## Comments