rofi93's blog

Help needed for SPOJ — ORDERSET
By rofi93, history, 8 years ago, In English

I was trying to solve this problem using AVL tree, but getting RE. Can't find out what I'm doing wrong. Can someone help me ??

Solution — https://ideone.com/l7a0jg

UPDATE

Got AC. The bug was I was accessing directly root->subtree_size without checking if the root is NOT NULL.

Here's my AVL tree implementation, pastebin and ideone

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

»
8 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

think about treaps in this problem

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

Auto comment: topic has been updated by rofi93 (previous revision, new revision, compare).

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

This problem has a really nice and easy offline solution using BIT.

You can solve it online (as you did using your own AVL, congrats!) or using an Ordered Set from C++ (not the set from STL)

→ Reply
»
8 years ago, hide # |
← Rev. 12  
Vote: I like it +1 Vote: I do not like it

The following is a slight update to your AVL tree solution. All the functions dealing with the structure node have been updated and included as member functions and friend member functions of the class AVL_tree. Algorithms in all functions are essentially the same, except for the function find_k_smallest which has been rewritten as a recursive function.

The 209 lines of code between lines 14 and 222 in this update should be equivalent to your 311 lines of code between lines 102 and 412 in ideone. The only difference is 102 lines reduction (about 33%) in the code size, and probably a slightly more readable code.

Finally, note that it is simple to add to this problem a command that prints the k-th largest key in the set using the function find_k_smallest. The answer is 

root->find_k_smallest( root->size + 1 - k )
→ Reply