ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1136. Parliament

Optimal solution
Posted by Ivan Nikulin 13 Mar 2013 19:04
Is there any linear solution to this problem? I have implemented an O(NlogN) one.

Let me tell you the  way I've solved it. We just pick our last vertex (number) as a root and try to divide another part into 2 subtrees. In order to do this we find a border between those 2 parts, so that all numbers in the first part are less than our root and vice-versa for second part. The latter can be easily implemented using binary search. And then we just do all the same from the very beginning with both parts recursively. It's obvious that the only time-consuming part is binary search, which takes O(logN) time in the worst case. Therefore the complexity of this algorithm is O(NlogN).
Re: Optimal solution
Posted by aybek 12 Oct 2013 23:14
Here you are! I have user bst think that time is O(n) good luck!

[code deleted]

Edited by moderator 20.06.2020 16:13
Re: Optimal solution
Posted by Mamuka Sakhelashvili [Freeuni] 10 Feb 2014 03:02
My algorithm is not optimal.. It's like, I start from last vertex and add in BST. after I finish this, I print this tree according to problem statement.  It's NlogN algorithm and I still have TLE on 9 test.. N is at most 3 000 and why isn't it enough?? :/
Re: Optimal solution
Posted by ACMighty 6 Sep 2015 23:08
Because the algorithm is not optimal. If the tree is unbalanced then your solution will go to O(N ^ 2). See it yourself with a sorted input.