Loading [MathJax]/jax/output/HTML-CSS/fonts/TeX/fontdata.js

TheScrasse's blog

By TheScrasse, history, 2 years ago, In English

[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 n1 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 1n400.

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,0dpi,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 2li1 (the transitions are similar, but using dpil,,k1 instead of dpi1,,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 dpi,,, we 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 n3. (AC code: 181878668)

So my questions are:

  • Why is the initial solution wrong?
Hint
  • 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 n1 where all the values are contiguous."
  • Vote: I like it
  • +125
  • Vote: I do not like it

| Write comment?
»
2 years ago, # |
  Vote: I like it +30 Vote: I do not like it

Sorry if this may be a very major spoiler, but I think this should be mentioned.

Spoiler
  • »
    »
    2 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it
    Spoiler
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Update:

    Spoiler

    Sorry for tagging: orzdevinwang, Motarack

»
2 years ago, # |
  Vote: I like it +2 Vote: I do not like it
Other open question

Btw, why are chromate00's comments always downvoted?

  • »
    »
    2 years ago, # ^ |
    Rev. 2   Vote: I like it +22 Vote: I do not like it

    Seeing the same person everywhere isn't so much a blessing, to many it is a curse. That's why.

  • »
    »
    2 years ago, # ^ |
    Rev. 2   Vote: I like it -17 Vote: I do not like it

    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.

»
2 years ago, # |
  Vote: I like it -27 Vote: I do not like it

no