### TheScrasse's blog

By TheScrasse, history, 15 months ago,

[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."
• +125

| Write comment?
 » 15 months ago, # |   +30 Sorry if this may be a very major spoiler, but I think this should be mentioned. SpoilerThe sequence in the problem exists already on OEIS. The record number for the sequence is A111111. As you can guess by reading the description on OEIS, your result (without the $-2 \cdot (-1)^n$) may be related to A059372.
•  » » 15 months ago, # ^ | ← Rev. 2 →   0 SpoilerOops, I wasn't allowed to check OEIS during the contest and I forgot to check it after the contest.
•  » » 15 months ago, # ^ |   0 Update: SpoilerSome of the shortest (unofficial) submissions (for example, 122355989, 66989827) seem to calculate A059372 using other formulas (one of them works in $O(n^2)$), then add $-2 \cdot (-1)^n$. I hope some contestants found it without guessing.Sorry for tagging: orzdevinwang, Motarack
•  » » » 15 months ago, # ^ |   +14 Update 2: SpoilerA formal proof of the $-2 \cdot (-1)^n$ seems to appear on this paper, also listed on OEIS. I think I am not knowledgeable enough to understand the entire paper, though.
•  » » » 15 months ago, # ^ | ← Rev. 2 →   +28 This problem is the same as LOJ3397, which $n$ is $10^5$. I learned the solution to that problem, it doesn't need to guess.
 » 15 months ago, # |   +2 Other open questionI still don't get why my code produces A059372.Btw, why are chromate00's comments always downvoted?
•  » » 15 months ago, # ^ | ← Rev. 2 →   +22 Seeing the same person everywhere isn't so much a blessing, to many it is a curse. That's why.
•  » » 15 months ago, # ^ | ← Rev. 2 →   -17 Btw, why are chromate00's comments always downvoted? Probably because he/she writes so many comments and that irritates people, but that's not a reason to downvote them at all.
 » 15 months ago, # |   -27 no