ontheqt's blog

By ontheqt, history, 4 years ago, In English

Can anyone explain why the following code gets TLE on test case 46? What should I do to get an AC. The problem is a straightforward application of prefix sums.

public static void main(String[] args) {
        FastScanner fs = new FastScanner();
        int n = fs.nextInt();
        long[] A = new long[n];
        long[] B = new long[n];

        for(int i=0; i<n; ++i){
            A[i] = fs.nextLong();
            B[i] = A[i];
        }
        Arrays.sort(B);
        for(int i=1; i<n; ++i){
            A[i] += A[i-1];
            B[i] += B[i-1];
        }
        int m = fs.nextInt();
        while(m-- != 0){
            long ans;
            int t = fs.nextInt();
            int l = fs.nextInt()-1;
            int r = fs.nextInt()-1;
            if(t == 1){
                ans = A[r]- (l-1 < 0 ? 0 : A[l-1]);
            }
            else{
                ans = B[r] - (l-1 < 0 ? 0 : B[l-1]);
            }
            System.out.println(ans);
        }
    }
  • Vote: I like it
  • -3
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

From participating in the Kotlin contest, I think Arrays.sort(B) is the problem because Java uses an algorithm with worst case time complexity O(n^2) and there are test cases that may be achieving this. To fix this either shuffle the array before sorting (i.e. override the sort function), or use Long[] instead of long[].

In the case of Kotlin it was better performance wise to shuffle first because IntArray (equivalent to int[]) performed much faster than Array<Int> (equivalent to Integer[]).

I'm not sure the best approach for Java, but someone definitely does.