zzzzsust19's blog

Why is my solution not getting TLE?
By zzzzsust19, history, 14 months ago, In English

This is a convex hull trick problem. I am building my convex hull from leaf to higher nodes. Every time I am going through all my child nodes, I am merging them together. In this solution, I am not applying light to heavy technique. Because of the increasing CHT size, I would expect my solution to get TLE on the given constraints. But for some reason, it's not getting TLE. Anyone got any proper explanation?

Problem: 932F - Сбежать через лист

My submission: 227235272

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

»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
14 months ago, # |
  Vote: I like it +3 Vote: I do not like it

It might be that on random tests the average size of the CHT is O(log N) where N is the number of elements added at some point in time. Also you might get lucky and have the heavy nodes coveniently placed.

→ Reply
  • »
    »
    14 months ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    Yeah, but if the tree is carefully created it's possible that no line in the convex hull get's deleted. There should be test cases like that

    → Reply