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

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

The first subtask rewards bitmask solutions.

**Time Complexity:**

#### Subtask 2

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

```
...101...
...110...
```

A `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.

Similarly,

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

**Time Complexity:**

Fun note:

There are side cases where that need to be considered. However, they were not tested.

## Comments