Блог пользователя RaidenEi

Автор RaidenEi, история, 7 лет назад, По-английски

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.

  • Проголосовать: нравится
  • +12
  • Проголосовать: не нравится

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

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.

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

You might use this one:

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

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

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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