Editorial for CPC '19 Contest 1 P3 - Admiral Kuznetsov
Submitting an official solution before solving the problem yourself is a bannable offence.
The first subtask rewards bitmask solutions.
Solution courtesy of.
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:
1 can only change to a
0 if a group of aircraft takes 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.
Finally, and make sure that negative indexed cells aren't used.
There are side cases where that need to be considered. However, they were not tested.