iLoveIOI's blog

Construction Problem
By iLoveIOI, history, 6 years ago, In English

Given n<=1000000 and k<=n*(n-1)/2 construct a sequence of length n that has exactly k inversions. How do I solve this? Thanks!

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

»
6 years ago, hide # |
 
Vote: I like it +8 Vote: I do not like it

Every number $$$1 \le i \le n$$$ can add maximum $$$n - i$$$ inversions. So we can run from $$$1$$$ to $$$n$$$ and if $$$cnt_{inversion} + (n - i) \le k$$$ then place $$$i$$$ on maximum right unused position and doing $$$cnt_{inversion} += (n - i)$$$. Else place $$$i$$$ on minimal left unused position and $$$cnt_{inversion}$$$ was not changed.

My solution
→ Reply