CrapCoder's blog

help me out in lightoj 1097
By CrapCoder, history, 11 years ago, In English

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 ??

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

»
11 years ago, hide # |
 
Vote: I like it +5 Vote: I do not like it

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.

→ Reply
  • »
    »
    11 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    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

    → Reply
    • »
      »
      »
      11 years ago, hide # ^ |
      ← Rev. 3  
      Vote: I like it +5 Vote: I do not like it

      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

      → Reply