PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: iceknight1093
Tester: sushil2006
Editorialist: iceknight1093
DIFFICULTY:
Simple
PREREQUISITES:
None
PROBLEM:
Given are two binary arrays A and B.
You can do the following:
- Choose an index i (1 \leq i \leq \min(|A|, |B|)) such that A_i = B_i.
- Delete A_i.
Find the maximum possible number of operations that can be performed.
Also find a way to perform these operations.
EXPLANATION:
Let’s try to find some elements that cannot be deleted, no matter what.
Consider some element A_i.
If A_i = B_i, of course this element can be deleted.
If not, then our only hope of deleting A_i is to delete some elements before it, which shifts its position a bit to the left - which will hopefully result in it matching some element of B.
Specifically, if we’re able to delete k elements before index i, we can try matching A_i to B_{i-k}.
With this in mind, let’s define M_i to be the maximum number of elements that can be deleted before index i.
Then, the element A_i can be matched with any of B_i, B_{i-1}, B_{i-2}, \ldots, B_{i - M_i}.
If any of these elements equal A_i, we’ll be able to delete it; otherwise we won’t.
If we’re able to delete A_i, we have M_i = M_{i-1} + 1; whereas if we can’t delete A_i, we have just M_i = M_{i-1}.
The only part that needs to be sped up here is the check for whether any of B_i, B_{i-1}, B_{i-2}, \ldots, B_{i - M_i} equal A_i.
There are several ways to do this quickly:
- Store the positions of all zeros and all ones in B as two separate lists.
Then, binary search over the list corresponding to A_i to check if it has any element in [i-M_i, i]. - Alternately, while iterating i from 1 upward, just store the last seen position of both 0 and 1 in B.
If anything lies in the range [i-M_i, i], it will be this last occurrence.
At the end of the above process, we’ll have decided for each element whether it can never be deleted, or if there can potentially exist some process to delete it.
You might note that some details are a bit unclear as of now: mainly, even if we decide that some A_i is “deletable” because it matches one of B_i, B_{i-1}, \ldots, B_{i-M_i}, it’s not obvious that we can always even make M_i deletions before it - that’s just a theoretical maximum.
However, things actually work out quite nicely: it’s always possible to perform exactly M_i deletions before index i; and this can be done for all indices simultaneously - that is, every element we decided was deletable can in fact be deleted from A.
Below is a constructive proof.
Construction
Recall that M_i is defined to be the maximum number of deletions before index i.
For an index i, let j \leq i be the nearest index such that B_j = B_i.
Our claim is that if j \lt i - M_i, it’s never possible to delete A_i, otherwise we always can.
The construction for this is in fact quite straightforward.
Let’s decide which element must be deleted first.
Clearly, it must be some i for which A_i = B_i already.
Among all such indices, it’s ideal to take the rightmost one - because taking anything else would end up shifting some of these indices, and might break the A_i = B_i condition for them.
Now, taking the rightmost valid index might then create some more valid indices to its right (since only these elements will have their indices shifted).
This way, some new valid indices are potentially created, and once again we take the rightmost valid index, and so on and so forth.
Simply repeating this process till no valid index remains is optimal!
This is because, after making some element become valid by performing some deletions before it, we never make it “invalid”, because no deletion will be performed to its left before it is deleted.
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Editorialist's code (PyPy3)
for _ in range(int(input())):
n, m = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
L, zero, one = 0, -1, -1 # last occurrence of 0 and 1
for i in range(n):
if i < m:
if b[i] == 0: zero = i
else: one = i
if a[i] == 0:
if zero < L: L += 1
else:
if one < L: L += 1
print(L)