Hi there! Couple of days ago I was solving problem [796C-Bank Hacking](http://codeforces.com/problemset/problem/796/C).↵
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 buildt 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 about 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](https://github.com/williamfiset/FastJavaIO/blob/master/src/main/java/fastjavaio/InputReader.java) '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](http://codeforces.com/contest/796/submission/27793950) 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. ↵
↵
↵
↵
↵
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 buil
↵
~~~~~↵
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 about 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](https://github.com/williamfiset/FastJavaIO/blob/master/src/main/java/fastjavaio/InputReader.java) '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](http://codeforces.com/contest/796/submission/27793950) 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. ↵
↵
↵
↵
↵