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.

Authors: crackersamdjam

Subtask 1

The first subtasks rewards bitmask solutions.

Time Complexity: \mathcal{O}(2^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 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 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))

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

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

Time Complexity: \mathcal{O}(N)


Comments

There are no comments at the moment.