I've been working on this problem from JOISC 2020:
Problem summary
You're given two arrays $$$a$$$ and $$$b$$$ of length $$$2n$$$. You have to pick exactly $$$n$$$ elements from each array to form a sequence of $$$2n$$$ total elements (alternating picks between the two arrays), such that the resulting sequence is non-decreasing. If possible, also print such a sequence using 'A' and 'B' to indicate from which array each element was chosen.
Dynamic programming
Here's a fairly natural DP approach:
Let $$$\text{dp}[i][j][k]$$$ be true if it's possible to build a valid sequence using the first $$$i$$$ elements, having picked exactly $$$j$$$ elements from array $$$a$$$, with the $$$i^\text{th}$$$ pick taken from:
- $$$a$$$ if $$$k = 1$$$
- $$$b$$$ if $$$k = 0$$$
This setup lets us ensure non-decreasing order, since we can directly compare the current value to the previous picked value (from either $$$a$$$ or $$$b$$$).
Let $$$arr[0] = b$$$, $$$arr[1] = a$$$. Then the transition becomes:
$$$\text{dp}[i][j][k]={\text{dp}[i-1][j-k][1]\,\text{and}\, a[i-1]\le \text{arr}[k][i]} \,\text{or}\,{\text{dp}[i-1][j-k][0]\,\text{and}\, b[i-1]\le \text{arr}[k][i]}$$$
Here's a code snippet for the transition:
dp[0][0][0] = dp[0][0][1] = true;
int *arr[] = {b, a};
for (int i = 1; i <= n << 1; ++i) {
for (int j = 0; j <= n; ++j) {
for (int k = 0; k < 2; ++k) {
if (j - k >= 0) {
dp[i][j][k] = (dp[i - 1][j - k][1] && a[i - 1] <= arr[k][i]) || (dp[i - 1][j - k][0] && b[i - 1] <= arr[k][i]);
}
}
}
}
This solution is correct, but it's too slow ($$$O(n^2)$$$) to pass the full constraints.
Observation
This is where I’m stuck.
The editorial claims something interesting:
For fixed $$$i$$$ and $$$k$$$, the set of $$$j$$$ values for which $$$\text{dp}[i][j][k] == \text{true}$$$ always forms a contiguous interval.
That is, if $$$\text{dp}[i][j_1][k]$$$ and $$$\text{dp}[i][j_2][k]$$$ are both true, then for all $$$j$$$ in the range $$$(j_1, j_2)$$$, $$$dp[i][j][k]$$$ is also true.
This would allow us to compress the DP state $$$\text{dp}[i][*][k]$$$ into a simple $$$[l, r]$$$ range and optimize everything to $$$O(n)$$$.
And testing it seems to support the claim. I printed the $$$\text{dp}[2n][*][k]$$$ bitmasks for the sample inputs:
for (int i = 0; i <= n; ++i) {
printf("%c", (char)dp[n << 1][i][0] + 0x30);
}
printf("\n");
for (int i = 0; i <= n; ++i) {
printf("%c", (char)dp[n << 1][i][1] + 0x30);
}
printf("\n");
outputs
Sample 1:
0011
0000
Sample 2:
111
011
Sample 3:
000
000
Sample 4:
0011110
0001111
Looks like the $$$1$$$'s form a contiguous block every time.
My question
I have no clue how to prove this formally.
Why does the set of valid pick counts from a (i.e., $$$j$$$ values such that $$$\text{dp}[i][j][k] == \text{true}$$$) always form a contiguous interval?
Any ideas, intuition, or sketch of a proof would be very appreciated.
Thanks in advance!
Note: I figured out that proving this is equivalent to proving that $$$\text{dp}[i][0] \bigcup \text{dp}[i][1]$$$ is a contiguous range for all $$$i$$$, for which maybe some kind of induction will work.
In other words, this means that for any two arrays $$$a$$$ and $$$b$$$, the union of the range of number of elements you pick from $$$a$$$ such that the answer exists if you pick $$$a_i$$$ and if you pick $$$b_i$$$ will be a contiguous range.
This still doesn't give much intuition though.
Here's a brute-force induction proof I thought of. There are four conditions in the dynamic programming transition (here):
Let $$$\text{dp}[i]$$$ be shorthand for $$$\text{dp}[i][0] \bigcup \text{dp}[i][1]$$$. There are $$$2^4 = 16$$$ possible ways to obtain $$$\text{dp}[i]$$$.
Out of all of these ways, any ways with conditions $$$1$$$ and $$$2$$$ or $$$3$$$ and $$$4$$$ satisfied will already be done, since the original interval, or it $$$+1$$$ is entirely covered by one of the parts. The same thing applies to $$$1$$$ and $$$2$$$ or $$$3$$$ and $$$4$$$ being false, as this means we'll only build either the left or right part of $$$\text{dp}[i]$$$.
So then we're left with:
Let us analyze each of these individually.
$$$0101$$$ means we pick the right half of $$$\text{dp}[i-1]$$$, then the right half $$$+1$$$. This will obviously be contiguous. $$$1010$$$ is the same thing just for the left half.
So now:
$$$0110$$$ gives $$$a_{i-1} \le a_i \lt b_{i-1} \land b_{i-1} \le b_i \lt a_{i-1}$$$ and $$$1001$$$ gives $$$a_{i-1} \le b_i \lt b_{i-1} \land b_{i-1} \le a_i \lt a_{i-1}$$$. Both of these have the contradiction $$$b_{i-1} \lt a_{i-1} \land a_{i-1} \lt b_{i-1}$$$ in them. So they were never possible.
Therefore this proves all $$$16-2=14$$$ possible transition cases.