ikk's blog

How would you solve #101 Problem C if n ≤ 50000?
By ikk, 12 years ago, In English

How would you solve #101 Problem C if n ≤  50000?

A typical solution for this involves repeatedly inserting an element at the ai-th position of a sequence n times.  This is the bottleneck of the overall solution, because this takes O(n2) time if the sequence is implemented by an array or by a linked list.  This obviously doesn't work if n ≤  50000.

In the solution submitted by hex539, the sequence is implemented by a custom balanced binary search tree (BST).  The running time of the bottleneck is reduced to , and thus this works even if n ≤  50000.

The problem with a balanced BST (if any) is that implementing it yourself is tedious and error-prone.  So the question is how you would solve it if n ≤  50000 without using a balanced BST, preferably by reducing the bottleneck to time.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it
maybe you can use <set> in STL
→ Reply
  • »
    »
    12 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    I don't think you can. Since the operator + is not defined for std::set<T>::iterator, you end up in incrementing it n times, thus getting an O(n2) solution.

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

Simple solution with complexity O(n*sqrt(n) http://codeforces.com/contest/141/submission/1109037

i-th element of list contains link to i+sqrt(n)-th element. So find i-th element - O(sqrt(n)), recalc links - O(sqrt(n)).

Sorry for my bad english.

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Thanks. Your description is clear.

    Your solution has reminded me of the possibility of using a skip list, which I think is simpler than a balanced BST.
    → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Even simpler solution. Time complexity is: O(n * log n) (sorting) + O(n) (final processing).
    → Reply