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.
I see your point, but why exactly is it becoming TLE? My analysis of the N log N seems correct
1 Like
No, I’m afraid it’s not, and the testcase was designed explicitly to trigger the O(N^2) behaviour
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