Do you really understand Connected Components DP?

Правка en1, от TheScrasse, 2022-11-21 18:03:42

[title inspired from 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.

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,\text{*},k \oplus 1}$$$ instead of $$$dp_{i-1, \text{*}, 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 you calculate $$$dp_{i,*,*}$$$, 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."
Теги dp, dumb_experiments

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
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)