Блог пользователя NeverSayNever

Автор NeverSayNever, история, 9 лет назад, По-английски

Hello codeforces community,

problem link

mysolution link

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.

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
9 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Yes, I think it is O(Nlog2N). Another way to analyse the complexity is: for each individual element, say x, we will inserting x into a Balanced BST(BBST) at most O(logN) times, because when we merge smaller BBST with larger BBST, the size of the BBST grows by at least double and eventually the size could be at most N.

And queries are O(logN) worst case, so I think it should have passed. BTW, I can't see your solution, its not public. Probably your implementation has a higher constant.