_Erased's blog

By _Erased, history, 5 years ago, In English

The tutorial of the problem 1322B - Подарок says "Bonus:Solve the problem in O(NlogC)." Can someone please explain how to do it?

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

»
5 years ago, # |
Rev. 3   Vote: I like it +8 Vote: I do not like it

Instead of $$$\log(C)$$$ "normal" sorts, you can use only one radix sort: for each step, the numbers modulo $$$2^{i+1}$$$ are sorted and you can use two pointers to get the $$$i$$$-th bit of the answer.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Using radix sort and two pointers 77988238