Kaleab_Asfaw's blog

TLE for Round #655 Div 2 Problem D (Omkar and circle), help
By Kaleab_Asfaw, history, 4 years ago, In English

Hey, In Round #655 problem D I am having TLE , 86974560

My idea (mostly similar to the editorial's but have some changes) is in the below image, Let n = 5, a = [1, 2, 3, 4, 5] and I have 2 steps. One step 1 I start from the first element and move by 2, so from 1 --> 3 --> 5 --> 2 --> 4. I will create a array for this [1, 3, 5, 2, 4]. Then I will find the maximum sum of length (n + 1)/2 as maxx1.

On step 2 I will repeat the above from starting from the second element and move by 2, 2 --> 4 --> 1 --> 3 --> 5. [2, 4, 1, 3, 5]. Then find the maximum sum of length (n + 1)/2 as maxx2.

Return the max(maxx1, maxx2). That was all, I am sure it works (No Wrong Answer).

I guess the Time Complexity will be around O(n). Someone tell me if it is larger or know why the TLE occured?

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

Comments Comments (3)
| Write comment?
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Did you even read your submission's verdict? It says wrong answer on test 1 (aka the samples!).

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    First thanks for willing to help!

    Sorry, I was mistaken when coping the submission link, I mean this 86974560

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

      Im no Python expert, but to generate this list:

      path[1:]

      takes $$$O(sz(path))$$$, and it seems you are doing it $$$O(n)$$$ times, so the time complexity is $$$O(n^2)$$$. Also including these lines:

      import sys

input = sys.stdin.readline

      Can speed up I/O. Also maybe pypy 3 is faster than python 3.

      → Reply