Блог пользователя ikk

Автор ikk, 13 лет назад, По-английски

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.

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
maybe you can use <set> in STL
  • »
    »
    13 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
13 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Simple solution with complexity O(n*sqrt(n) http://mirror.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.

  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    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.
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Even simpler solution. Time complexity is: O(n * log n) (sorting) + O(n) (final processing).