rofi93's blog

Help needed for SPOJ — ORDERSET
By rofi93, history, 6 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

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

think about treaps in this problem

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    I was just trying to learn AVL tree that's why. :(

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

      Have you tried random inputs?

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

        Tried some. Didn't get any error.

        → Reply
        • »
          »
          »
          »
          »
          6 years ago, # ^ |
          ← Rev. 2   Vote: I like it +1 Vote: I do not like it

          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.

          → Reply
        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it +7 Vote: I do not like it

          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.

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

            Ok. That's a good idea. I will test my AVL tree implementation first then.

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

            Solved it. :D

            The bug was for finding k'th smallest I was accessing root->subtree_size without checking that if root is NOT NULL.

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              6 years ago, # ^ |
                Vote: I like it +7 Vote: I do not like it

              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.

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

                Thanks for the suggestion. :D Will keep it in mind. :D

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

    Do you have any treap implementation. If yes can you share ??

    → Reply
»
6 years ago, # |
  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
»
6 years ago, # |
  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
»
6 years ago, # |
← 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
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Thanks. :D

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

      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.

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

        How does OOP improve performance?

        → Reply
        • »
          »
          »
          »
          »
          6 years ago, # ^ |
          ← Rev. 8   Vote: I like it +8 Vote: I do not like it

          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?

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

            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?

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

        For CP, I don't prefer OOP actually. :P

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

          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

          → Reply
          • »
            »
            »
            »
            »
            »
            6 years ago, # ^ |
            ← Rev. 2   Vote: I like it 0 Vote: I do not like it

            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.

            → Reply