Hello codeforces community,↵
↵
<a href="http://www.codechef.com/problems/CHEFDTRE">problem link</a>↵
↵
<a href="http://www.codechef.com/viewsolution/7298175">mysolution link</a>↵
↵
I tried the following solution in this problem and got TLE for the subtask2.↵
For each union operation i tried to merge smaller size set into bigger size set and added element to the corresponding balanced bst. so for each union operation i will be taking time O((number of element in smaller size set) * (log(element in the bigger size set)) and find the kth element in O(log(size of given set)). what is the worst case complexity of this solution ? I think it is O(N*log^2(N)) amortized. O(N*log^2(N)) was it unacceptable ? Please help me.
↵
<a href="http://www.codechef.com/problems/CHEFDTRE">problem link</a>↵
↵
<a href="http://www.codechef.com/viewsolution/7298175">mysolution link</a>↵
↵
I tried the following solution in this problem and got TLE for the subtask2.↵
For each union operation i tried to merge smaller size set into bigger size set and added element to the corresponding balanced bst. so for each union operation i will be taking time O((number of element in smaller size set) * (log(element in the bigger size set)) and find the kth element in O(log(size of given set)). what is the worst case complexity of this solution ? I think it is O(N*log^2(N)) amortized. O(N*log^2(N)) was it unacceptable ? Please help me.
