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

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

Hey guys I wanted to share with you something I discovered.

I was checking contests I took part in last year and stumbled into round 308 Div2. Problem D: This

This problem could be solved by simple O(n^3) by just picking all triplets and see if they make a triangle.

Well last year I calculated m1 = (y[k] — y[j]) / (x[k] — x[j]) and calculated m2 = (y[j] — y[i]) / (x[j] — x[i]) as doubles and if (m1 == m2) then it's triangle.

Looking at the constraints n <= 2000 so this answer should pass in the problem's time limit which is 4 seconds. But I got TLE.

This year while checking my previous solution, I decided to just convert the equation like this:

=> m1 = m2

=> (y[k] — y[j]) / (x[k] — x[j]) = (y[j] — y[i]) / (x[j] — x[i])

=> (y[k] — y[j]) * (x[j] — x[i]) = (y[j] — y[i]) * (x[k] — x[j])

So now both l1 and l2 could be calculated as integers, I did this and AC. Wow.

Seems like double division in C++ takes time, while multiplication as integers is faster, that's why I got AC.

Previous (TLE) Submission: Submission 18887929

Current (AC) Submission: Submission 18887986

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

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

This problem could be solved by simple O(n^3) ...
Expected solution is O(n^2 * logn).

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

    You can notice that time limit is 4 seconds so O(n^3) should pass. And it actually passed.

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

      From editorial : I am sorry, that O(n^3 / 6) solutions passed, my solution with O(n^3 / 6) didn't pass before the contest, so I decided, that TL 4 sec is good(it was for Java TL).

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

        But O(n^3) solutions did actually pass, and editorial's solution is not the only one there. And I'm not discussing the solution I'm just discussing that double division got TLE while integer multiplication passed.