Noob5644's blog

HELP IN CODEFORCES ROUND 745 div 2
By Noob5644, history, 3 years ago, In English

https://mirror.codeforces.com/contest/1581/problem/A

what is the logic ?? i just know the ans is (2*n)!/2 ,but how ?

  • Vote: I like it
  • -13
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
3 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Assume there is a unsatisfied permutation $$$P$$$ and $$$x$$$ is the number of $$$i$$$ that satisfy $$$p_i < p_{i + 1}$$$ and $$$x < n$$$. So just reverse $$$P$$$, the number of $$$i$$$ satisfy $$$p_i < p_{i + 1}$$$ in our new permutation is $$$2 * n - 1 - x > 2 * n - n - 1 = n - 1$$$. It's easy to see that the answer is $$$\frac{(2*n)!}{2}$$$

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

if any permutation doesn't satisfied that condition then it reverse will do and if that permutation does then its reverse doesn't.

so half will satisfy and other half( reverse one) will not.

→ Reply