## Editorial for CPC '19 Contest 1 P3 - Admiral Kuznetsov

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

Time Complexity:

Solution courtesy of Dormi.

Let be the units of time needed to match the first spots with the final configuration.

is a string of the initial deck and represents the final configuration.

First the trivial cases:

• If , then
• If and , then

We observe that at location , only up to 4 aircraft can be affected by an operation. So only the past 4 values matter. states and a -cell transition would work.

Consider the following:

...101...
...110...

A 1 can only change to a 0 if a group of aircraft take off. Here is the process:

First, aircraft land to fill all three spots. Then, they take off. Finally, more aircraft land to cover the final configuration.

Let denote the number of aircraft on the initial deck between positions and , inclusive. counts the same for the final configuration.

Similarly,

Cases where need to be considered separately because groups of aircraft taking off may overlap.

Finally, and make sure that negative indexed cells aren't used.

Time Complexity: