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

help me out in lightoj 1097
Автор CrapCoder, история, 8 лет назад, По-английски

this is the problem link ...... http://lightoj.com:81/volume/problem/1097 it can be solved using bit but how does it fit into the complexity ??

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

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

The example helps us see that the answer is at most 1429431. Now we can easily simulate the process with the help of Fenwick tree or some other tree-like data structure but I prefer Fenwick when it's possible to use it since it's really really easy to code. So, let's say that all numbers are available at the beginning (increase all indices from 1 to 1429431 by 1). We should extend our data structure so that it can quickly tell us which is the K-th available number for given K. This can be easily done with binary search over the answer and then with the standard query we check if there are at least K-1 numbers less than the fixed. Also, every number is crossed out at most one time so our solution is actually fast enough — http://ideone.com/WmKP2d.

→ Ответить
  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Implementation might be easier in this approach, but better complexity can be achieved with a segment tree based algorithm. To find the K-th available number you are doing a binary search with a Fenwick tree query. That's , while you can do it with segment tree in .

    The idea is to store the summation of range in every node of the segment tree. Then if k<=tree[left] then the answer is in the left child of this node. Otherwise, you need to look for k-tree[left] in the right side of the tree.

    BTW, why do you define common variables to gibberish? Are there any advantages? :p

    → Ответить
    • »
      »
      »
      8 лет назад, # ^ |
      ← Rev. 3   Проголосовать: нравится +5 Проголосовать: не нравится

      Yes, I know that and an algorithm with slightly better complexity can be achieved with BST since its operations are O(log Size) instead of O(log MaxSize) which sounds better but I am pretty sure segment tree will perform better in practice and still I prefer the shortest working algorithm. And I saw such defines in I_love_Tanya_Romanova's codes and the first time I wondered wtf he was doing but some days after that I tried to declare a global variable called left and the compiler didn't allow me to do so because of some function called left which I didn't know it exists so that helps to avoid collisions :)

      UPD: I forgot to put log in the brackets :D

      → Ответить