Please subscribe to the official Codeforces channel in Telegram via the link ×

MedoN11's blog

By MedoN11, history, 8 years ago, In English

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 !

  • Vote: I like it
  • 0
  • Vote: I do not like it

8 years ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it