"Sherlock and queries" challenge

Question

I'm writing some Java code for some pretty large datasets, in a puzzle I'm trying to solve. The output is correct, but the program doesn't run within the time limit for all the test cases. I've tried a number of optimizations, but can't think about how to improve it. I'd appreciate your suggestions.

The puzzle is here.

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer tok = new StringTokenizer(br.readLine());
int N = Integer.parseInt(tok.nextToken());
int M = Integer.parseInt(tok.nextToken());
long[] A = new long[N];
int[] B = new int[M];
long[] C = new long[M];    
tok = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) A[i] = Long.parseLong(tok.nextToken());
tok = new StringTokenizer(br.readLine());
for (int i = 0; i < M; i++) B[i] = Integer.parseInt(tok.nextToken());
tok = new StringTokenizer(br.readLine());
for (int i = 0; i < M; i++) C[i] = Long.parseLong(tok.nextToken());
br.close();

for (int i = 0; i < M; i++) {
    for (int j = B[i] - 1; j < N; j += B[i]) {
        A[j] = (A[j] * C[i]) % 1000000007;
    }
}
for (long l : A) System.out.print(l + " ");

Answer 1

This is one of the beefs I have with online judging systems like this..... it is not testing the algorithm, or anything like that. Instead, consider doing the very last line like:

// the longest value will be 11 chars long because % 1000000007 + " "
StringBuilder sb = new StringBuilder(N * 11);
for (long l : A) {
    sb.append(l).append(" ");
}
System.out.print(sb.toString());

A single println is almost always N times faster than N printlns.

If that does not make it work in time, then consider reading the entire System.in in to a buffer, and parsing it from the buffer.

Answer 2

Scanner is very ergonomic for parsing inputs, you can simplify your code quite a bit, instead of StringTokenizer (of which you created many):

class Solution {
    public static void main(String[] args) throws IOException {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        int M = scanner.nextInt();
        long[] A = new long[N];
        int[] B = new int[M];
        int[] C = new int[M];
        for (int i = 0; i < N; i++) A[i] = scanner.nextInt();
        for (int i = 0; i < M; i++) B[i] = scanner.nextInt();
        for (int i = 0; i < M; i++) C[i] = scanner.nextInt();

        // ...
    }
}

All the input values fit within an int, so I changed the type of C to int[], and use .nextInt for all inputs. I left the type of A as long[] to let the A[i] * C[i] calculation step exceed the int limit (before the modulo).

---

Another thing, BufferedReader closes the underlying stream, in this case System.in (see the implementation on grepcode). I think it's not a good practice to close a stream you didn't open, normally it should be the caller's responsibility.

---

How about giving the \$10^9 + 7\$ constant a name:

private static final int MODULO = (int) 1e9 + 7;

---

Unfortunately none of this will get you pass all tests. I have a feeling that the fastest solution is more a matter of math and logic than code review material.

---

Btw, next time it's good if you include the full code. That way we can test run our suggestions easier on the hosting website, otherwise we have to guess that the implementation must be in the main method of a class named Solution.