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?
Did you even read your submission's verdict? It says wrong answer on test 1 (aka the samples!).
First thanks for willing to help!
Sorry, I was mistaken when coping the submission link, I mean this 86974560
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:
Can speed up I/O. Also maybe pypy 3 is faster than python 3.