iLoveIOI's blog

Construction Problem
By iLoveIOI, history, 5 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

»
5 years ago, # |
  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