Codeforces div3

problem link:- link text

solution:-link text

Im getting TLE but my solution is O(n) and also time allotted is 2 sec.

I have documented my solution can someone plz suggest whats making TLE.

Test case for TLE

400000 399999


You have used qsort which is quick sort then how you can say your solution O(n)? In worst case it can be O(n²). So, try different approach which should be O(n) ans dont use sorting.

1 Like

I changed my code to c++(hardly any changes :slight_smile: ) made use of sort() function.

Still getting TLE.

Now can u identify , where time is exceeding. updated solution link


You actually need not use sorting for this problem because your array which is counting the occurences of characters can be calculated from original string itself. So, that will make solution O(n) instead of O(nlogn) and also it will save few more operation where you are copying a string and will also save memory.

Yeah i got but why my solution gives TLE , even if the alloted time is 2sec. And i searched sort() of c++ uses optimized quick sort version

Yes C++ sort use hybrid sorting algorithm and is optimized compared to qsort in C.
I never did codeforces so no idea about its judge but there are chances that the solution needs to be O(n) according to time limit or give fast IO a try. Even your code is too much overkill to the problem a simple solution is possible which requires fewer O(n) loops.

Someone Format it /cc @vijju123
And also explain how they did it.

strlen(s) takes O(n) time.
for( i=0;i<strlen(s);i++) takes O(n*n) time to run loop.

use -
for( i=0; i<l ; i++)