Kanata18's blog

Combinatorics problem
By Kanata18, history, 4 weeks ago, In English

Hello codeforces community!!

On this occasion I bring up a combinatorics problem.

This is the problem:

How many permutations of length N exist such that the following holds: for each i (1 <= i < N) p[i+1] — p[i] != 1

Constants: 1 <= N <= 500

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I haven't proved my solution yet, but this should solve the task in $$$\mathcal{O}(n)$$$.

Solution
→ Reply
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

It occurred to me to do it using: Connected Component DP (although I don't know how to implement it)

→ Reply
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

This problem is the exact same as CSES — Permutations II, although the constraints are $$$n \leq 5000$$$.

Note, this task could be solved in $$$O(n)$$$, you can check it on USACO Guide — Solution

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

Thank you very much for the material

→ Reply