Editorial for DMOPC '20 Contest 6 P2 - Interpretive Art

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: 4fecta

The solution relies on 2 key observations.

  1. When we perform a brush stroke on a range, we can consider it as moving all of the 0s to the left of the range and all of the 1s to the right. This also means that 0s can only move to the left, whereas 1s can only move to the right.
  2. If we number the 0s in A (first 0, second 0, third 0, etc.), then their relative order never changes after any brush stroke.

The key idea now is that we must match the i-th 0 in A with the i-th 0 in B. First, let us check for impossibility. There are 2 cases where it is impossible to turn A into B.

  1. If the number of 0s in A is not equal to the number of 0s in B.
  2. If the i-th 0 in A is to the left of the i-th 0 in B (since 0s can only move to the left, these will never be matched).

All other cases are possible; we can simply spend 1 brush stroke for each pair of 0s in A and B and match them into the correct positions. We now provide an algorithm that uses the minimum possible number of brush strokes, assuming that it is possible to turn A into B:

Consider the first "chunk" of 0s in B, consisting of k consecutive 0s. We can simply find the position of the k-th 0 in A, and use a brush stroke from index 1 to the position of the k-th 0 in A (unless the position of the k-th 0 in A is the same as the position of the k-th 0 in B, in which case this chunk is already matched). This will match the chunk of 0s, as well as the following chunk of 1s; if it didn't, then there would be a 0 in A where there should be a 1, but since 0s only move to the left and no more 0s are needed on the left side, this contradicts the assumption of possibility. Also, note that any other combination of strokes that matches the first chunk of 0s in B will result in the exact same arrays A and B, so 1 is definitely the optimal number of brush strokes if any are needed. Then, since the first chunk of 0s and 1s are matched, we can remove these chunks and restart the algorithm on the shortened arrays, where the proof of correctness is propagated.

That may sound like a mouthful, but it is really only there for logical rigour and a proof of optimality. The TL;DR is to just match every chunk of 0s in B with the correct number of 0s in A from left to right.

Subtask 1

Simply simulating the algorithm above yields an \mathcal{O}(N^2) or \mathcal{O}(N^2 \log N) solution, both of which are sufficient to pass this subtask.

Time Complexity: \mathcal{O}(N^2) or \mathcal{O}(N^2 \log N)

Subtask 2

A slightly optimized approach is required for this subtask. For example, one may store the index of the i-th 0 in A for all i, and only consider using a brush stroke when encountering an index j such that B_j = 0 and B_{j+1} = 1. There are, of course, a ton of other possible approaches as well.

Time Complexity: \mathcal{O}(N)


There are no comments at the moment.