It seems that some people haven't got the idea of this problem 285E - Positions in Permutations while the tutorial is still incomplete so I'd like to write some explanations about it.
A common approach for this kind of problem is DP. What we do here is to choose numbers for the good positions first, then fill the others later on. Let f(i, j, k) is the number of ways to choose j good positions in the first i-th position and k is a 2-bit number that represents whether number i and number i + 1 is already used or not. The DP transition is quite simple.
Let F(j) is the number of permutations with j good positions, then F(j) = Σ(f(n, j, k)) * (n - j)! (because there are n — j numbers left unchosen). However, there are cases we may form some extra good positions when putting these n — j numbers into our permutations, thus F(j) now stores the number of permutations with at least j good positions. But we want F(j) to be the number of permutations with exact j good positions, so we must exclude those permutations with more than j good positions.
Let's do it in descending order. First F(n) must be the number of permutations with exact n good positions. Hence, we may calculate F(n - 1) based on F(n), then F(n - 2) based on F(n - 1) and F(n), and so on... The last part is to calculate how many times F(j) is repeatedly counted in F(i) (i < j), it's simply C(j, i) (the number of ways to choose i good positions from j good positions).
The overall complexity is O(n^2).
Please refer to my submission 3376355 for an implementation.
could you kindly give more details about f(i, j, k) recursive formula?
Why not just calculate
F(j) — F(j+1), wouldn't it be the number of permutations with exact j good positions?No. Because F(j + 1) might be counted more than once in F(i). For example when n = 2, k = 1: F(2) = 1, F(1) = 2. Clearly, the answer is 0 because F(2) is counted twice in F(1).
Oh.. how could I not think of that. Thanks.
I think your explanation about the the state f(i, j, k) should be clearer, the 2-bit k that represents whether i and number i + 1 are used or not, is in fact if number i is present in "good" position i-1 and if i+1 is present in "good" position i, respectively.
Yes, that's what I mean. I think everyone can understand it easily so I try to make it short. Anyway, thanks for your interpretation.
I have different solution which directly call F[i][j] is the number of permutations of length i with j good positions. We will add one more dimension to handle some states, so it will be F[i][j][k]. We can create new permutation with length i+1 from a permutation(i,j) by insert (i+1) to the end of the permutation . After that, we swap (i+1) with the the element from 1 to i. By this way, we can retain at least j-1 good position in the permutation to form new permutation.
To manage DP accurately, we have to keep some extra property along with F[i][j]. The third dimension in DP formula of my approach handles whether the ith element = (i-1) and whether the (i-1)th = i. The state can be maped to 0->3. In my solution , there is one more state F[i][j][4] means number of permutation of length i with j good positions having i at the end(a[i]=i) because this state can not be demonstrated as I mentioned before.
About the transition of F[i][j]. Let me call the element having value i is uth. There are 4 ways of swap, 1st: swap with "no good" positions nor uth nor ith, 2nd: swap with good positions nor uth nor ith, 3rd: swap with uth, 4th: swap with ith
This is my submission. It might be confusing because of my bad implement. http://mirror.codeforces.com/contest/285/submission/3404593
That's what i can really understand,thank you very much!!
What is a simple transfer equation like？I can't understand.