Will O(n sqrt(n)) solution work for n=10^5 and Test cases=5 with time limit=2sec?

I have found a solution with time complexity O(n sqrt(n)) for a problem with n<=10^5, test cases<=5, individual array Integers are <=10^5 and time limit is 2 seconds. But i am getting TLE for most of the cases in last sub-task. Language used= python, pypy

I don’t understand why all cases of last subtask not working although 2 cases of last subtask got accepted.

Theoretically it should work. But it also depends on what you are doing apart from your loops and all. If you are doing some heavy computations, then it will give TLE because of these overhead. It would be much better if you provide us with your code also. You can also try the same logic with some other faster language. One time in a long contest, I was getting TLE in Python but the same logic got me an AC in Java.

Yes it should work easily if you have optimized your solution in terms of hidden constants…
Please try to optimize it…
O(N*sqrt(N)) is perfect logic for passing in 2 secs…

This is literally asking for help for a question from ongoing March Long Challenge.

You are saying like if someone asked how to submit solution on CodeChef and you are saying “this is literally cheating and he is asking for help about all questions in long challenge !!”

No, your exaggerated situation is not cheating. But yes if codechef is fine with such things, then instead of making people ask about the required complexity on its forum it might as well just write the required complexity they are looking for in the question itself, that would be fair for everyone.

I would have surely liked it if in 2 question, on which I got tle because of different time complexity, required complexity were written right below the I/O section, would have saved me a day or two

aparichit_vyav, here is a hint for you, you can easily see the min required complexity by looking constraints and time limit :slight_smile:

tieros, here is a task for you, try to get this code AC

https://www.codechef.com/viewsolution/23483251

It is O(N*root(N)) as desired. :slight_smile:

When array is full of big values your solution sometimes goes worse than O(N*root(N)). I tested it with 100k * 100k and it took 1.3 secs to complete. Actually wish we knew what was in those test cases, whatever I did, I couldn’t pass last two cases.

Bingo!!!

I agree with @tieros
You can always predict time complexity…
Try precalculating root(N) part and it should pass
and @aparichit_vyay do see editorial page for link

//