dheetCoder's blog

[Pattern] Permutations
By dheetCoder, history, 21 month(s) ago, In English

Suppose we have given a permutation of length n. Can we find the count of a specific binary string of length n-1. Such that for each permutation p we increment the count of binary string b, where b[i]=='1' if p[i+1]>p[i] else '0' for each i from 0...n-2. For n=5 I have runned the bruteforce code

Code

Getting the output

result
  • Vote: I like it
  • +1
  • Vote: I do not like it

»
21 month(s) ago, # |
  Vote: I like it +9 Vote: I do not like it

Yes, but it's hard.
1776N - Count Permutations

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    Actually the solution in $$$O(n^2)$$$ is much easier. See this problem.

    Solution sketch
    → Reply