Hi there! Couple of days ago I was solving problem 796C-Bank Hacking. I came up with O(nlog(n)) order solution, but it failed with Time Limit Exceeded status. The max input size was 3*10^5, which implies that order O(n*log(n)) algorithm must fit into time limit. The tutorial for the contest also mentioned the same order solution. After a few hours of debugging, I have realized that the problem is in input reading part. Well, my code used built in BufferedReader in java:
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
Bank banks[] = new Bank[n];
String tokens[] = br.readLine().split(" ");
List<Integer> g[] = new List[n];
int max = Integer.MIN_VALUE;
for(int i =0 ;i<n;i++) {
g[i] = new ArrayList<>();
int val = Integer.parseInt(tokens[i]);
max = Math.max(max, val);
banks[i] = new Bank(i, val);
}
for(int i = 0;i<n-1;i++){
tokens = br.readLine().split(" ");
int a = Integer.parseInt(tokens[0])-1;
int b = Integer.parseInt(tokens[1])-1;
g[a].add(b);
g[b].add(a);
}
The code slice already consumed about 800 ms for the maximum size input. After I have submitted a linear time alternative solution, but I still decided to find more faster way of reading. I have found williamfiset 's InputReader which claimed to be much faster than the BufferedReader. Finally I decided to write my own FastScanner inspired with his idea. Well here it is (Currently I have just implemented it for Integers):
import java.io.*;
import java.util.*;
public class FastScanner {
static final int DEFAULT_BUFF = 1024, EOF = -1, INT_MIN = 48, INT_MAX = 57;
static final byte NEG = 45;
static final int[] ints = new int[58];
static {
int value = 0;
for (int i = 48; i < 58; i++) {
ints[i] = value++;
}
}
InputStream stream;
byte[] buff;
int buffPtr;
public FastScanner(InputStream stream) {
this.stream = stream;
this.buff = new byte[DEFAULT_BUFF];
this.buffPtr = -1;
}
public int nextInt() throws IOException {
int val = 0;
int sign = readNonDigits();
while (isDigit(buff[buffPtr]) && buff[buffPtr] != EOF) {
val = (val << 3) + (val << 1) + ints[buff[buffPtr]];
buffPtr++;
if (buffPtr == buff.length) {
updateBuff();
}
}
return val*sign;
}
private int readNonDigits() throws IOException {
if (buffPtr == -1 || buffPtr == buff.length) {
updateBuff();
}
if (buff[buffPtr] == EOF) {
throw new IOException("End of stream reached");
}
int signByte = -1;
while (!isDigit(buff[buffPtr])) {
signByte = buff[buffPtr];
buffPtr++;
if (buffPtr >= buff.length) {
updateBuff();
}
if (buff[buffPtr] == EOF) {
throw new IOException("End of stream reached");
}
}
if(signByte == NEG) return -1;
return 1;
}
public void close() throws IOException {
stream.close();
}
private boolean isDigit(int b) {
return b >= INT_MIN && b <= INT_MAX;
}
private void updateBuff() throws IOException {
buffPtr = 0;
stream.read(buff);
}
}
The FastScanner class in my code worked very fast and the maximum size input reading time has reduced up to 47 ms. As a result I have got accepted even with O(nlog(n)) order solution, just by replacing the reading part by the following code slice:
FastScanner in = new FastScanner(System.in);
int n = in.nextInt();
Bank banks[] = new Bank[n];
List<Integer> g[] = new List[n];
for(int i =0 ;i<n;i++) {
g[i] = new ArrayList<>();
int val = in.nextInt();;
banks[i] = new Bank(i, val+2);
}
for(int i = 0;i<n-1;i++){
int a = in.nextInt()-1;
int b = in.nextInt()-1;
g[a].add(b);
g[b].add(a);
}
You may find my last submission here if you want.
Further I plan to upgrade and test my FastScanner, and never use BufferedReader when fast reading is important.
Thank you for attention.
