Help with TLE

I have written this code for the problem PUMPWAT.
It seems to be getting a TLE verdict, though I’m sure the complexity is \mathcal O (N \log N) and there is no infinite loop.
Like, for the first pivot \mathcal O (N) time, for the next two combined \mathcal O(N) time and same for next 4 and so on…
So overall N\log N time.
It’s kind of annoying. I looked up some AC solutions and they do the same thing. Morever its an ‘easy’ problem which is annoying me quite a bit. Can someone help?
Edit:
For instance, see this sol:
https://www.codechef.com/viewsolution/27879006
It seems to be the same as mine with different var names.
And yes, even if the split is not at the middle the complexity is \mathcal O (N \log N) not \mathcal O (N^2), because 2nd and 3rd “cut” both together still take up \mathcal O (\N) time, similarly for 4,5,6,7 cuts and so on: even if the cut is not at the middle.

Consider this testcase.

1 Like

I see your point, but why exactly is it becoming TLE? :sweat_smile: My analysis of the N log N seems correct :sweat_smile:

1 Like

No, I’m afraid it’s not, and the testcase was designed explicitly to trigger the O(N^2) behaviour :slight_smile:

Add the line:

    cout << "L: " << L << " R: " << R << endl;

as the first statement of moves, and recall that if L \le R, then your solution loops over all values from L to R.

2 Likes

Oh, I see now. I’ll fix it.
Thanks!

1 Like