Read 600,000 input from the console in less than 2 seconds

Question

The Goal

I'm solving this problem:

Little Girl and Maximum Sum

The little girl loves the problems on array queries very much.

One day she came across a rather well-known problem: you've got an array of n elements (the elements of the array are indexed starting from 1); also, there are q queries, each one is defined by a pair of integers li, ri (1 ≤ li ≤ ri ≤ n). You need to find for each query the sum of elements of the array with indexes from li to ri, inclusive.

The little girl found the problem rather boring. She decided to reorder the array elements before replying to the queries in a way that makes the sum of query replies maximum possible. Your task is to find the value of this maximum sum.

Input The first line contains two space-separated integers n (1 ≤ n ≤ 2·105) and q (1 ≤ q ≤ 2·105) — the number of elements in the array and the number of queries, correspondingly.

The next line contains n space-separated integers ai (1 ≤ ai ≤ 2·105) — the array elements.

Each of the following q lines contains two space-separated integers li and ri (1 ≤ li ≤ ri ≤ n) — the i-th query.

Output In a single line print a single integer — the maximum sum of query replies after the array elements are reordered.

With test 7 (see the test results in the end of the question), the input is an array of size 200,000 with 200,000 queries (which have r and l values).

The input looks like this:

200000 200000
189622 189286 194361 184457 182376 183471 197548 184736 195806 ... 200,000 integers

188738 290041
33738 90041
122738 390041
... 200,000 line

You can download a sample input file, or you can create your own sample input. It wouldn't matter the numbers itself.

---

The Problem

I need to read 600,000 input lines without exceeding 2 seconds of execution time. The problem is, it doesn't even read the first 200,000 input in 2 seconds.

How can I speed up my code to read all 600,000 input within 2 seconds?

---

The Code

Here is my first attempt:

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int q = scanner.nextInt();
        int[] array = new int[n];
        for (int i=0; i<n; i++) {
            array[i] = scanner.nextInt();
        }
        int[][] qArray = new int[q][2];
        for (int i=0; i<q; i++) {
            qArray[i][0] = scanner.nextInt();
            qArray[i][1] = scanner.nextInt();
        }

        int[] index = new int[n];
        Arrays.sort(array);
        for (int i=0; i<q; i++) {
            for (int j = qArray[i][0]-1; j<qArray[i][1]; j++) {
                index[j]++;
            }
        }
        Arrays.sort(index);
        long sum =0;
        for (int i = 0; i<n; i++) {
            sum += index[i]*array[i];
        }
        System.out.println(sum);
    }
}

Here is my second attempt:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {

    public static void main(String[] args) {
        try {
            BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
            String input = bufferedReader.readLine();
            String[] SplitInput = input.split(" ");
            int n = Integer.parseInt(SplitInput[0]);
            int q = Integer.parseInt(SplitInput[1]);

            String input2 = bufferedReader.readLine();

            int[][] qArray = new int[q][2];
            for (int i=0; i<q; i++) {
                input = bufferedReader.readLine();
                SplitInput = input.split(" ");
                qArray[i][0] = Integer.parseInt(SplitInput[0]);
                qArray[i][1] = Integer.parseInt(SplitInput[1]);
            }

            String[] SplitInput2 = input2.split(" ");
            int[] array = new int[n];
            for(int i=0; i<n; i++){
                array[i] = Integer.parseInt(SplitInput2[i]);
            }

            int[] index = new int[n];
            Arrays.sort(array);
            for (int i=0; i<q; i++) {
                for (int j = qArray[i][0]-1; j<qArray[i][1]; j++) {
                    index[j]++;
                }
            }
            Arrays.sort(index);
            long sum = 0;
            for (int i=0; i<n; i++) {
                sum += index[i]*array[i];
            }
            System.out.println(sum);
        }
        catch (NumberFormatException ex) {
            System.out.println("Not a number !");
        }
        catch (IOException e) {
            e.printStackTrace();
        }
    }
}

---

Test Results

Attempt 1

7 Time: 2000 ms, memory: 20612 KB Verdict: TIME_LIMIT_EXCEEDED

Attempt 2

7 Time: 2000 ms, memory: 41340 KB Verdict: TIME_LIMIT_EXCEEDED

You can view my full test results here and here. Again, the problem is on Test 7.

Answer 1

Disclaimer, I said I was able to help you, I am, but I can't solve it for you. I haven't been able to limit it under 2 seconds, because I didn't properly understand the question itself. I understand what your algorithm does, technically, but I have issues to understand it conceptually, making me unable to find the big optimization. I found the big optimization. See bottom of the answer.

Remarks: I've seen your results on the test page for the smaller tests and there is absolutely no reason why your first tests last 200+ ms. I just don't understand that. They're all running consistently under 2 ms on my computer (using the Java internal System.nanotime() method). I believe the test include the startup of the JVM. If that's actually the case, may I suggest that you switch to a more optimized language like C or C++? Meaning that the test is somewhat rigged against interpreted languages.

Algorithm

The first problem is your algorithm itself. It's slow: You're actually iterating through 200,000 × x ints (which is a high value on average, from your file). In the worst case, you're iterating through 200,000 × 200,000 = 40,000,000,000 ints. No wonder you're having times around the 20 seconds.

That's way too much. Ideally, you should be able to reduce that double loop using optimization like using a map. You have a great amount of memory at your disposal (256 MB), use it. You already do it; do it more.

The big optimization lies somewhere here. I believe that instead of incrementing index by index you should find another optimization by skipping this index mechanism and using a better one. I believe that it's the reason why the question exists: find that algorithm and no other. I dislike that, but I don't judge it.

Reading data

I tested reading data through the input and your method is slow. I blame your use of Scanner.

I suggest you use this construction and this split method which run in < 100 ms total on my computer with your big test file (I insist... my computer is not your computer and our computers are not the computer your test is evaluated on). I believe that it can be reduced further, but I'd say it's good enough. It's not the big optimization we're looking for, but it's the second, I believe.

try (BufferedReader reader = new BufferedReader(new InputStreamReader(System.in))) {
  int[] counts = split(reader.readLine(), new int[2]);
  int n = c[0], q = c[1];
  int[] array = split(reader.readLine(), new int[n]);
  int[][] queries = new int[q][]; // Note, no size in the second part of the array creation.
  for (int i = 0; i < q; i++) {
    queries[i] = split(reader.readLine(), new int[2]);
  }
  ...
}

With the appropriate split method which is optimized for your use case:

static int[] split(String s, int[] a) {
  int n = 0, aIndex = 0;
  for (int sIndex = 0, sLength = s.length(); sIndex < sLength; sIndex++) {
    char c = s.charAt(sIndex);
    if (c == ' ') { // Separator
      a[aIndex++] = n;
      n = 0;
    } else if ('0' <= c && c <= '9') { // Number
      n = n * 10 + (c - '0'); // Add a digit to the current number
    }
  }
  a[aIndex] = n;
  return a;
}

Small optimizations

Conceptually, you have the following code:

for (int i = 0; i < q; i++) {
  // Fill qArray
}

for (int i = 0; i < q; i++) {
  // Work with index.
}

These two loops could be merged, further even eliminating the need for your qArray. You read data, and you process it directly. This is not really important if the loops are next to each other, but in between you're sorting stuff in an array in your first attempt, and you're both sorting an array and parsing the input in your second attempt. This makes your data go far from the CPU cache on one hand, but you're processing I/O on the other one. I don't know which one is better.

You have a bug in your code

I tried to rethink the problem and found a solution, but your answer was never the same as mine. And I actually found a bug in your code. I couldn't get the same result as you with your file.

In your final loop, the sum-loop, you store everything in a long, but it's actually possible to get an int overflow. So you should make your sum like this:

sum += (long)(index[i]) * array[i];

Found it!

Regarding your code, as I said, you have a problem because you potentially get more than 40 billion instructions. I could flatten your the solution with what you can see below. And I consistently hit the 500 ms now.

public static void main(String[] args) throws IOException {
  long nanos = System.nanoTime();
  myMain();
  nanos = System.nanoTime() - nanos;
  System.out.printf("Time: %sms%n", MILLISECONDS.convert(nanos, NANOSECONDS));
}

static void myMain() throws IOException {
  try (BufferedReader reader = new BufferedReader(new InputStreamReader(System.in))) {
    int[] counts = split(reader.readLine(), new int[2]);
    int n = counts[0], q = counts[1];
    int[] array = split(reader.readLine(), new int[n]);
    int[] indices = new int[n];
    for (int i = 0; i < q; i++) {
      int[] query = split(reader.readLine(), new int[2]);
      indices[query[0] - 1]++;
      if (query[1] < n) {
        indices[query[1]]--;
      }
    }
    for (int i = 1; i < n; i++) {
      indices[i] += indices[i - 1];
    }
    sort(array, 200_000);
    sort(indices, 200_000);
    long sum = 0;
    for (int i = 0; i < n; i++) {
      sum += (long)array[i] * indices[i];
    }
    System.out.println(sum);
  }
}

static void sort(int[] array, int n) {
  int[] counts = new int[n+1];
  for (int element: array) {
    counts[element]++;
  }
  int current = 0;
  for (int i = 0; i < counts.length; i++) {
    Arrays.fill(array, current, current + counts[i], i);
    current += counts[i];
  }
}

static int[] split(String s, int[] a) {
  int n = 0, aIndex = 0;
  for (int sIndex = 0, sLength = s.length(); sIndex < sLength; sIndex++) {
    char c = s.charAt(sIndex);
    if (c == ' ') {
      a[aIndex++] = n;
      n = 0;
    } else if ('0' <= c && c <= '9') {
      n = n * 10 + (c - '0');
    }
  }
  a[aIndex] = n;
  return a;
}

Enjoy!

If you have any question regarding this optimization, don't hesitate ;)