Hi Codeforces community,
Recently I have come across a problem which turned out to be tough for me. I hope that I can get some help from you.
Problem Statement
A permutation A of first N integers from 1 to N is good if it has exactly K good positions. A position i is good only if abs(A[i] - i) = 1. The task is to count how many permutation of first N integers like that, modulo 109 + 7.
Input
N and K, 1 ≤ N ≤ 1000, 0 ≤ K ≤ N
Output
Number of permutation of first N integers from 1 to N that has exactly K good positions, modulo 109 + 7
Example
For N = 3, K = 2, there are 4 permutations that has 2 good positions. They are (1, 3, 2) , (2, 1, 3) , (2, 3, 1) , (3, 1, 2).
You may want to submit your solution here (written in Vietnamese, required SPOJ account): http://www.spoj.com/PTIT/problems/P172PROI/
I think it is a DP problem although I could not come up with a solution or any idea. Any help will be appreciated.
Thanks in advance.
Auto comment: topic has been updated by RaidenEi (previous revision, new revision, compare).
Position i is good if a[i] = i - 1 or a[i] = i + 1.
So when you want to know what place will number i take, you must know if positions i - 1 and i + 1 are free.
So DP will be like dp[i][j][mask] — for all numbers from 1 to i - 1 you have alredy found place, you now have j good positions, mask have 3 bits for positions i - 1, i, i + 1. I think 3rd bit is optional.
Correct! This is exactly a part of solution provided in this editorial in case you are interested http://mirror.codeforces.com/blog/entry/7126
You might want to take a look at this problem too. They have some similarities and without much thought I'd say that the solution to that problem works for counting an exact number of special positions (this time generalized by a difference of exactly K). Both my solution and the official one use inclusion-exclusion principle.
This one really looks harder IMO, but can you elaborate how did you solve it by inclusion-exclusion?
You might use this one:
http://mirror.codeforces.com/problemset/problem/285/E
It's exactly the same problem. You have an editorial there.
Holy! That was really helpful, thank you so much.
Can someone provide links to such similar problems for practice? Problems where the problem statement is like — "Find all permutations of the given array which satisfies the given condition.".
Thanks! :)
Try this.
A even more harder version of this, with N ≤ 109, K ≤ 105: Perfect Permutations — HackerEarth
Wow, thanks for sharing this. I was sure that the lowerbound for this was O(n*k) but seems that I'm wrong.
You can try to solve this
UPD: Wow, both of us has the same rating :o
Hehe Yeah! :P @Lyn
Thanks @Shinobu @Lyn