rahulpkvij's blog

Why does my code give TLE on TEST 49 ?? PLEASE HELP !
By rahulpkvij, history, 5 years ago, In English

https://mirror.codeforces.com/contest/1278/submission/75598239 Prob D DIV2 Educational Round 78.. https://mirror.codeforces.com/contest/1278/problem/D Can someone please help me figure out why my code gives TLE on TEST 49 ? It would be a huge help ! Thanks in advance!

  • Vote: I like it
  • -11
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hello! From what I could tell by looking at your code, you seem to be iterating through every possible pair of segments, checking for intersections, and then checking to see if the resulting graph is a tree. The problem is that iterating through every pair of intersections takes $$$O(n^2)$$$ time, which is way too much for $$$n < 5 \cdot 10^5.$$$ Could you find a more efficient way to find all pairs of intersections?

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hey ! Thank you for your reply !. I guess I am unable to understand how in the editorial we are finding all pairs of intersections in less than O(n^2) time.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I think I finally got it !. We need to sort on the basis of starting points AND ending points in order to avoid unnecessary checks where one segment is contained inside the other. We break the process when we reach n intersections

      → Reply