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