In the problem B the solution is very short and probably every body make a n*log(n) solution by sorting the array and then pass over the array in O(n) to get the solution. There should'nt happen things like this: This is my code and it was Time Limit Exceded only because it was made in java.
int n =nextInt();
long x = nextLong();
long[] a = new long[n];
for (int i = 0; i < n; i++)
a[i]=nextLong();
Arrays.sort(a);
long resp = 0;
for (int i = 0; i < n; i++)
{
resp += (x*a[i]);
x--;
x = Math.max(1,x);
}
out.println(resp);I would like to know who is in charge of this king of issue?
The same happened to me, it's only after the contest, that it was accepted when I replaced the
int[] arr = new int[n]withInteger[] arr = new Integer[n]..And it makes me confused, as I made a benchmark to compute the difference of sorting between
int[]andInteger[]usingArrays.sort(),Integer[]was 2.3 slower thanint[].Any idea, anyone?
Because java uses qick sort for primitive array.So worst complexity time is O(n^2) even if it uses randomisation algorithm for choosing pivot in some cases.Otherwise it uses tim sort which is O(nlog(n)).
I had no idea that for primitive data types, quick-sort is used. This is the first time I've fallen victim to using Arrays.sort() on primitive data-type array. I always thought merge-sort was implemented on the backend code, never really looked into it. As I've found out today, I was horribly wrong. Well, at least I learned something today.
For those who still have doubts/more information visit the documentation: http://docs.oracle.com/javase/7/docs/api/java/util/Arrays.html
Excellent View! Thx：）
There are special tests on which solutions in Java with sorting of primitive data types arrays work too slow: 1, 2 (first link in Russian only, use Google Translate).
As 1e9 says, Arrays.sort uses quicksort, which could be O(N^2).
Collections.sort use merge sort, which is always O(N*log(N)).
You can check it at the documenation for Arrays and Collections
I think, Scanner is too slow..
Topic author uses self-written routines instead of
Scanner.BTW, my anti-Java6-quicksort is almost 3 years old, Java 6 is now deprecated, but new victims continue to appear :).