How to solve this gym problem ?

Revision en1, by MedoN11, 2016-04-27 04:12:43

Link to problem :

Idea: To solve this problem using a DFS, and maintaining a treap for each node, where it contains it’s corresponding binary-search tree.

Basically, recursively get the best BST of our right child, and best BST of our left child. ( If they exist ).

Ensure that the values added from each child node would not violate our corresponding binary search tree. If they do erase them, and get the best connected sub-tree you can get.

This approach gives a Wrong answer. Even though it’s very convincing.

Me and a friend of mine tried coming up with a test case to fail this but couldn’t find any.

Thanks !


  Rev. Lang. By When Δ Comment
en1 English MedoN11 2016-04-27 04:12:43 727 Initial revision (published)