elizabeth_zou_fanboi's blog

Among permutations of length N, how many satisfy |a_i − i| ≠ K
By elizabeth_zou_fanboi, history, 3 hours ago, In English

a permutation is valid only if |ai — i| != k for all 1<=i<=n. Count the number of valid permutations.

Constraints: 2 ≤ N ≤ 2000

1 ≤ K ≤ N − 1

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

»
3 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

"how many satisfy |a_i − i| ≠ K"

Could you clarify please?

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

    a permutation is valid only if |ai — i| != k for all 1<=i<=n.Count no of valid permutations.

    → Reply
»
70 minutes ago, # |
  Vote: I like it -6 Vote: I do not like it

Step 1: Generate all permutations of length $$$N$$$.

Step 2: Perform a linear scan, adding $$$1$$$ to the result if $$$|a_i - i| \ne k$$$ for all $$$i$$$ from $$$1$$$ to $$$N$$$.

Space complexity is $$$O(N \cdot N!)$$$ and time complexity is $$$O(N \cdot N!)$$$.

→ Reply