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

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:


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


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.


There are no comments at the moment.