Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official. ×

### rofi93's blog

By rofi93, history, 3 months ago, ,

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

•
• +2
•

 » 3 months ago, # |   0 think about treaps in this problem
•  » » 3 months ago, # ^ |   +3 I was just trying to learn AVL tree that's why. :(
•  » » » 3 months ago, # ^ |   0 Have you tried random inputs?
•  » » » » 3 months ago, # ^ |   0 Tried some. Didn't get any error.
•  » » » » » 3 months ago, # ^ | ← Rev. 2 →   +1 Try designing specific cases to test each of the four rotation cases. Then print the properties of each node to see if you got each one right.
•  » » » » » 3 months ago, # ^ |   +7 I got another tip: you can look for AVL Tree problems on sites where tests are visible (e.g. HackerRank). Then use your AVL tree there. Then view the tests where you tree fails.
•  » » » » » » 3 months ago, # ^ |   0 Ok. That's a good idea. I will test my AVL tree implementation first then.
•  » » » » » » 3 months ago, # ^ |   0 Solved it. :DThe bug was for finding k'th smallest I was accessing root->subtree_size without checking that if root is NOT NULL.
•  » » » » » » » 3 months ago, # ^ |   +7 Nice job! Now you've leveled up your debugging skills. Remember to craft specific cases to test parts of your code next time. It would be easier that way compared to trying to eyeball the bug.
•  » » » » » » » » 3 months ago, # ^ |   0 Thanks for the suggestion. :D Will keep it in mind. :D
•  » » 3 months ago, # ^ |   0 Do you have any treap implementation. If yes can you share ??
•  » » » 3 months ago, # ^ |   0 Yes, I solved it using treap: https://ideone.com/N7XOC5
•  » » » » 3 months ago, # ^ |   0 Thanks. :D
 » 3 months ago, # |   0 Auto comment: topic has been updated by rofi93 (previous revision, new revision, compare).
 » 3 months ago, # |   0 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)
•  » » 3 months ago, # ^ |   +3 the one in pb_ds
•  » » 3 months ago, # ^ | ← Rev. 2 →   +3 BIT with coordinate compression ??
•  » » » 3 months ago, # ^ |   +1 Yes
 » 3 months ago, # | ← Rev. 12 →   +1 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 ) 
•  » » 3 months ago, # ^ |   +1 Thanks. :D
•  » » » 3 months ago, # ^ |   0 With pleasure.Hope that more object-oriented programming features are utilized in your C++ code to enhance its performance as well as its readability, maintainability, and re-usability.
•  » » » » 3 months ago, # ^ |   0 How does OOP improve performance?
•  » » » » » 3 months ago, # ^ | ← Rev. 8 →   +8 I wrote "Hope" in the beginning! It is generally accepted that OOP code which calls virtual member functions at run-time is often slower than its equivalent procedural-style code whose function calls are embedded by the linker in the executable code, even though the OOP code is often more compact, as a virtual function call requires extra CPU cycles to dereference the function call to the actual function call using the class hierarchy virtual functions table. Further information about this issue is available at Qura.com: Software Performance: Is object oriented code more expensive in terms of CPU usage than procedural code?
•  » » » » » » 3 months ago, # ^ |   0 Thanks for the link! I was just momentarily astonished by the remark that OOP may improve performance.Btw. You seem to know your programming languages quite well. Are you a software engineer?
•  » » » » » » » 3 months ago, # ^ |   0 With pleasure. You may find the following paper on computer architecture support for programming languages and operating systems interesting. Improving the Performance of Object-Oriented Languages with Dynamic Predication of Indirect JumpsRE: knowledge in programming languages I am a life-long learner and object-oriented programming lover. I like to learn how things work, and to share this humble experience with other fellows whenever possible.
•  » » » » 3 months ago, # ^ |   0 For CP, I don't prefer OOP actually. :P
•  » » » » » 3 months ago, # ^ |   0 But if I were you I should use a simpler binary search tree in Competitive Programming. I think treaps are easier to code correctly than AVLs. In treaps, rotations are not necessary
•  » » » » » » 3 months ago, # ^ | ← Rev. 2 →   0 Yes. Treaps are easier and AVL actually can't be implemented in an onsite contest, only online may be if you already have the code.