Do you really understand Connected Components DP?

Revision en6, by TheScrasse, 2022-11-21 18:50:05

[title inspired by this blog]

Hello everyone,

today, during a NEERC virtual contest, I found an unintended solution for problem 1089I - Interval-Free Permutations. I've checked all the official submissions and no one of them uses my solution, so I think it's worth sharing it.

Abridged statement: count the permutations of $[1, \dots, n]$ such that there are no subarrays of length between $2$ and $n-1$ where all the values are contiguous. For example, the permutation $[2,8,4,6,3,5,1,7]$ is bad because it contains $[4,6,3,5]$ as a subarray. Output the answer (modulo a prime, given in the input) for all $1 \leq n \leq 400$.

My solution:

• Let's use PIE (inclusion-exclusion principle) on minimal bad subarrays.
• Let's use Connected Components DP, somehow keeping track of minimal bad subarrays.

• Let $dp_{i,j,k}$ be the number of ordered sets of $j$ connected components with total length $i$, and $k =$ parity of minimal bad subarrays. Then, the number of good permutations of length $i$ is $dp_{i,1,0} - dp_{i,1,1}$.
Instead of adding elements one at a time to the permutation, let's consider two cases:
- We add only one element (using the standard Connected Components DP transitions);
- We add a minimal bad subarray of length $2 \leq l \leq i-1$ (the transitions are similar, but using $dp_{i-l,*,k \oplus 1}$ instead of $dp_{i-1, *, k}$. Note that the number of ways to add a minimal bad subarray of length $l$ is equal to the number of good permutations of length $l$.
• When we calculate $dp_{i,*,*}$, we assume that $dp_{j,1,*} = 0$ ($j < i$), because the corresponding elements are good as arrays but bad as subarrays.

This solution is actually wrong: in most cases, it produces the correct output $\pm 2$! It turns out it's enough to add $-2 \cdot (-1)^n$ to the result, for $n \geq 3$. (AC code: 181878668)

So my questions are:

• Why is the initial solution wrong?
Hint
• Why is the solution with $-2 \cdot (-1)^n$ correct? Actually I don't know, I've just found the formula using the samples.
• Can this solution be generalized to solve harder problems? For example,
"An array is weird if the local minimums are bitonic (i.e., decreasing, then increasing). Count the weird permutations of $[1, \dots, n]$ such that there are no weird subarrays of length between $2$ and $n-1$ where all the values are contiguous."

#### History

Revisions

Rev. Lang. By When Δ Comment
en6 TheScrasse 2022-11-21 18:50:05 14
en5 TheScrasse 2022-11-21 18:48:58 37 Tiny change: 'he answer for all $' -> 'he answer (modulo a prime, given in the input) for all$'
en4 TheScrasse 2022-11-21 18:47:37 47
en3 TheScrasse 2022-11-21 18:30:18 8
en2 TheScrasse 2022-11-21 18:09:58 12 Tiny change: ' inspired from [this](ht' -> ' inspired by [this](ht'
en1 TheScrasse 2022-11-21 18:03:42 2781 Initial revision (published)