So I just found out that my solution which is almost same as this one gets TLE on test case 8 while latter got AC.
I can't figure-out why this happened?
Problem link -> C.Save More Mice
Solution:
It turns out that Arrays.sort() in java uses Quicksort which has worst time complexity of O(n^2) and Collections.sort() uses that has time complexity of O(nlogn).
refer to this article for more information.
Almost same != same
When I used Collections.sort() in place of Arrays.sort() I got AC too. Any idea why?
Yup, arrays.sort() is broken, and it's a pretty known fact in CF community, so it's pretty likely that every problem solved with java gets the test case that pushes sort() it into the TLE limit, either by strong pretests, or by being hacked by someone else.
It's because of Arrays.sort which can run in quadratic time for some inputs.