I've been working on this problem from JOISC 2020:

JOI20_building4 oj.uz link

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 dp[i][j][k] == 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 $$$(j1, j2)$$$, $$$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!