Codeforces Educational Round 85 | Problem B - MIddle Class | TLE

Can someone please explain why I’m getting a TLE for test case 9?
Here is the solution : (scroll down for the test cases)

I don’t understand how I’m getting a TLE on testcase 9, when testcase 6 got AC, and testcase 6 has the exact same value of n, and larger value for x. Please help!

Also, Mifafaovo’s AC solution for the same problem is here. Both the solutions follow the same logic.

EDIT 1: I saw a java solution from another user, and then changed my code. Made the following change :-
instead of int a[] = new int[n];
i wrote Integer a[] = new Integer[n];

And now I’ve got AC. Can you please explain the difference between int and Integer? And why am I not getting AC with ‘int’?

1 Like

int is primitive data type while Integer is a wrapper class which wraps primitive int type into an object.

You can read more from her: Difference between an Integer and int in Java

Thanks for that. But can you explain why I’m getting a TLE when I use ‘int’? Also, test case 6 has the same number of values, still it was accepted. How?

see my code may be you get some idea

man your code is so large how you write such a long code in a challenge that’s appreciable.

Arrays.sort is actually O(n^2) when used on an array of primitives, like int. Integer is an object, which Arrays.sort is implemented differently for, and it works in O(n\log(n)) for any object datatypes. See here (and maybe Google other things) for more information.

In the CP context, there are 3 ways to get over this:

  • Force the use of the object-based implementation of Arrays.sort every time by using Integer and Long arrays instead of their primitive counterparts
  • Shuffle your array each time, to counteract cases specifically designed to cause primitive Arrays.sort to be O(n^2)
  • Switch to a different programming language (probably not ideal)

So if quicksort (the algorithm in primitive Arrays.sort) is at worst O(n^2), why does Java use it? The key is that it’s quick, as the name implies, for most cases. In fact, basically the only time it will fail is when the test case is specifically designed against the quicksort implementation, such as this quicksort killer (may or may not work with new versions of Java). So a method like shuffling will almost always allow quicksort to pass. It’s probably a good idea to wrap it in a template so you don’t forget to shuffle/convert to objects and accidentally get hacked. This is an example of this, back when I used Java for one reason or another.

3 Likes

He only wrote main method during the contest. Reader part written there is part of template for fast I/O many programmers use this in competitive programming.

1 Like

I have to check about this again, I am not sure but quick sort is used in case of primitives and merge sort in case of Objects.
So, Sorting on objects guarantee you O(nlog(n)) but sorting on primitives can be O(n^2).

1 Like

ok i dont have any idea about java that why i confused how someone wriiten such a long code for an easy problem

1 Like

Thanks a lot @galencolin! Really appreciate your help.

bro i only wrote the main method. The rest is just for fast I/O, copied all that from a file.

1 Like