ravelo1991's blog

About Round #251 bad things happen on judge
By ravelo1991, 10 years ago, In English

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?

  • Vote: I like it
  • -5
  • Vote: I do not like it

Comments Comments (8)
| Write comment?
»
10 years ago, # |
  Vote: I like it +8 Vote: I do not like it

The same happened to me, it's only after the contest, that it was accepted when I replaced the int[] arr = new int[n] with Integer[] arr = new Integer[n] ..

And it makes me confused, as I made a benchmark to compute the difference of sorting between int[] and Integer[] using Arrays.sort(), Integer[] was 2.3 slower than int[].

Any idea, anyone?

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +19 Vote: I do not like it

    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)).

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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

      → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Excellent View! Thx：）

      → Reply
»
10 years ago, # |
  Vote: I like it +6 Vote: I do not like it

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).

→ Reply
»
10 years ago, # |
  Vote: I like it +11 Vote: I do not like it

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

→ Reply
»
10 years ago, # |
  Vote: I like it -16 Vote: I do not like it

I think, Scanner is too slow..

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    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 :).

    → Reply