_Erased's blog

Doubt in problem B-Present
By _Erased, history, 5 years ago, In English

The tutorial of the problem 1322B - Present 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.

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

Using radix sort and two pointers 77988238

→ Reply