Subtask 1

The first subtask rewards bitmask solutions.

Time Complexity: ~\mathcal{O}(2^N \times N)~

Subtask 2

Solution courtesy of Dormi.

Let ~dp[i]~ be the units of time needed to match the first ~i~ spots with the final configuration.

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

First the trivial cases:

If ~start_i = end_i~, then ~dp[i] = dp[i-1]~.

If ~start_i = 0~ and ~end_i = 1~, then ~dp[i] = dp[i-1]+1~.

We observe that at location ~i~, only up to 4 aircraft can be affected by an operation. So only the past 4 ~dp~ values matter.

~N~ states and a ~4~-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 ~cnt(a, b)~ denote the number of aircraft on the initial deck between positions ~a~ and ~b~, inclusive. ~cnt2(a, b)~ counts the same for the final configuration.

~dp[i] = \min(dp[i], dp[i-3] + (3 - cnt(i-2, i)) + 1 + cnt2(i-2, i))~

Similarly,

~dp[i] = \min(dp[i], dp[i-4] + (4 - cnt(i-3, i)) + 1 + cnt2(i-3, i))~

Finally, ~dp[0] = 0~ and make sure that negative indexed cells aren't used.

Time Complexity: ~\mathcal{O}(N)~

Fun note:

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