Reminder: in case of any technical issues, you can use the lightweight website m1.codeforces.com, m2.codeforces.com, m3.codeforces.com. ×

Any hints on Romanian IOI 2017 Selection #3 Pitmutation?

Revision en1, by Roundgod, 2019-01-12 12:22:44

This is a problem in CSAcademy Contest Romanian IOI 2017 Selection #3, Pitmutation, which basically is: Given two permutations A, B of length N with some positions fixed while some positions remains unknown, find the number of configurations such that there are exactly S positions p1, p2, ..., pS, where Api > Bpi, both N, S ≤ 300.

I've already come up a solution when there are no fixed positions. For simplicity, we can consider B as identity permutation and later multiply the answer by N!. Then we decompose the permutation into cycles. Let dp[i][j] denote the number of configurations, when there are i elements remaining, and the needed number of Api > Bpi positions is j. Enumerate the length of cycle the smallest element is in for transferring, which involves precalculating another DP: dp2[i][j] denote the number of permutations A of length i that consists of one cycle such that there are j positions x where Ax > A(x + 1)%i. This precomputation can be done in O(N2). With the help of this array, the original can be calculated in O(N3). Also can be optimized to using FFT. Furthermore, since we only concern the answer with S such positions, and every time we are multiplying the same polynomial, so we only need 2 times of DFT, and thus the complexity is O(N2).

However, I can't generalize this solution to the case where there are fixed positions, and also I can't find an editorial for this problem. Is there anyone willing to share some insights? Thanks in advance!

History

Revisions Rev. Lang. By When Δ Comment
en1 Roundgod 2019-01-12 12:22:44 1727 Initial revision (published)