Mehrdad12's blog

By Mehrdad12, 11 years ago, In English

Hi all, I just write my solution to solve problem 285C. but i has "Time limit exceeded on test 8" error, but another person wrote a solution like mine, but it doesn't have this probelm, what's wrong? thanks for any help. my code:

public class Main {
    public static void main(String[] args) {
        // TODO code application logic here
        Scanner sc=new Scanner(System.in);
        PrintWriter pw=new PrintWriter(System.out);
        long c=0;
        int n=sc.nextInt();
        int[] a=new int[n];
        for(int i=0;i<n;i++)
            a[i]=sc.nextInt();
        Arrays.sort(a);
        for(int i=0;i<n;i++)
            c+=Math.abs(a[i]-(i+1));
        pw.print(c);
        pw.flush();
    }
}

other guy's code:

public class Contest {
    public static void main (String [] args) {
        Scanner in = new Scanner(System.in);
        PrintWriter out = new PrintWriter(System.out);        
        int n = in.nextInt();
        List <Integer> aa = new ArrayList <Integer> ();
        int [] a = new int[n];
        int t  = 7;
        long counter = 0;
        for(int i = 0; i < n; ++i) {
            a[(i + t) % n] = in.nextInt();
        }
        Arrays.sort(a);
        for(int i = 0; i < n; ++i){
            counter += Math.abs((i + 1) - a[i]);
        }
        out.println(counter);
        out.flush();
    } 
}
  • Vote: I like it
  • -5
  • Vote: I do not like it

| Write comment?
»
11 years ago, # |
Rev. 2   Vote: I like it +6 Vote: I do not like it

I'm not so sure, but I think that the worst case performance for Array.sort() is O(N²) in a really special case. That's why the second algorithm doesn't get TLE, because he changes the initial order of the array and the special case now is gone. I think that was discussed here before. Anyway, you should always shuffle your array before sorting it in Java.

»
11 years ago, # |
  Vote: I like it +3 Vote: I do not like it

I think this thread answers your question. When using objects java uses Tim sort and for primitive data types it uses dual pivot quick sort. As Mdantas said some special input case causes Arrays.sort() to go in O(n^2) while Tim sort even in worst case uses O(n*log(n)).