My program is running in O(n) time (I hope so) but it is showing TLE in java. Can anyone please tell me what am I doing wrong here. I have used fast input with both BufferedWriter and PrintWriter but it is still showing tle. I know there is no problem with my logic because the same logic is accepted in C++. So can someone please tell me what is wrong with my java code.
Solution: Java: 82284306 CPP: 82285437
Problem: 1324D - Пара тем
Edit 2: The code worked after I replaced array with ArrayList. Can anyone explain to me why did this happen? Thanks in advance.
try shuffling your array before sorting.
UPD: I just tried it. It works.
Can you please tell why did that work?
If you read the javadocs for Arrays#sort, you will see that it uses Dual Pivot Quicksort algorithm. If you studied a basic algo course before, you would know that the performance of quicksort rests mainly upon its pivoting step — If you are lucky, the chosen pivot is almost always the median. So the depth of the quicksort recursion, in this case, is $$$\mathcal{O}(\log n)$$$. Hence, quicksort's performance is worst when the pivot is (almost) always skewed towards the extreme left or right. The test data that your code failed on was designed to cause this behavior in quicksort. So the solution is to simply shuffle the array so that no one can predict which will be the chosen pivot, reducing the likelihood that quicksort will hit its worst case behavior.
Thanks, till now I believed that sort function worked upon merge sort but I was wrong. Now the random ordering make sense.
Well, Collections#sort does use merge sort. So you can use that as an alternative. You don't even have to shuffle the array beforehand in that case.
Yup that maybe the reason why ArrayList worked then.
Another neat little function is Arrays.parallelSort(), which works for primitive arrays.
Otherwise you can use Arrays.sort() for object arrays like Integer, Long, etc. since Java uses merge sort for sorting array of objects.