RaidenEi's blog

How to solve this permutation problem?
By RaidenEi, history, 6 years ago, In English

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.

  • Vote: I like it
  • +12
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by RaidenEi (previous revision, new revision, compare).

→ Reply
»
6 years ago, # |
  Vote: I like it +2 Vote: I do not like it

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.

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    This one really looks harder IMO, but can you elaborate how did you solve it by inclusion-exclusion?

    → Reply
»
6 years ago, # |
  Vote: I like it +3 Vote: I do not like it

You might use this one:

http://codeforces.com/problemset/problem/285/E

It's exactly the same problem. You have an editorial there.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Holy! That was really helpful, thank you so much.

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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! :)

→ Reply