[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,…,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 dpi,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 dpi,1,0−dpi,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≤l≤i−1 (the transitions are similar, but using dpi−l,*,k⊕1 instead of dpi−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 you calculate dpi,∗,∗, assume that dpj,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 ±2! It turns out it's enough to add −2⋅(−1)n to the result, for n≥3. (AC code: 181878668)
So my questions are:
- Why is the initial solution wrong?
- Why is the solution with −2⋅(−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,…,n] such that there are no weird subarrays of length between 2 and n−1 where all the values are contiguous."