Help needed for SPOJ — ORDERSET

6 лет назад, # ^ |

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

→ Ответить

6 лет назад, # ^ |

Have you tried random inputs?

→ Ответить

6 лет назад, # ^ |

Tried some. Didn't get any error.

→ Ответить

6 лет назад, # ^ |

← Rev. 2 →

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.

→ Ответить

6 лет назад, # ^ |

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.

→ Ответить

6 лет назад, # ^ |

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

→ Ответить

6 лет назад, # ^ |

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.

→ Ответить

6 лет назад, # ^ |

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.

→ Ответить

6 лет назад, # ^ |

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

→ Ответить

6 лет назад, # ^ |

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

→ Ответить

shahidul_brur

6 лет назад, # ^ |

Yes, I solved it using treap: https://ideone.com/N7XOC5

→ Ответить

6 лет назад, # ^ |

Thanks. :D

→ Ответить

6 лет назад, # |

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

→ Ответить

snacache

6 лет назад, # |

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)

→ Ответить

des1997

6 лет назад, # ^ |

the one in pb_ds

→ Ответить

6 лет назад, # ^ |

← Rev. 2 →

BIT with coordinate compression ??

→ Ответить

6 лет назад, # ^ |

Yes

→ Ответить

6 лет назад, # |

← Rev. 12 →

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 )

→ Ответить

6 лет назад, # ^ |

Thanks. :D

→ Ответить

6 лет назад, # ^ |

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.

→ Ответить

6 лет назад, # ^ |

How does OOP improve performance?

→ Ответить

6 лет назад, # ^ |

← Rev. 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?

→ Ответить

6 лет назад, # ^ |

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?

→ Ответить

Improving the Performance of Object-Oriented Languages with Dynamic Predication of Indirect Jumps

6 лет назад, # ^ |

With pleasure. You may find the following paper on computer architecture support for programming languages and operating systems interesting.

RE: 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.

→ Ответить

6 лет назад, # ^ |

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

→ Ответить

snacache

6 лет назад, # ^ |

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

→ Ответить