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.
Hey, even I have a version of input reader in java. But I don't know whether it's fast enough :v Can you please check this for me and tell whether or not it will pass that solution. In case it doesn't I'll be using your version of reader from now onwards. Thanks!
class I{ private InputStream stream; private byte[] buf = new byte[1024]; private int curChar; private int numChars; private SpaceCharFilter filter;
public I() { this.stream = System.in; } public int read() { if (numChars == -1) { throw new InputMismatchException(); } if (curChar >= numChars) { curChar = 0; try { numChars = stream.read(buf); } catch (IOException e) { throw new InputMismatchException(); } if (numChars <= 0) { return -1; } } return buf[curChar++]; } public int in_i() { int c = read(); while (isSpaceChar(c)) { c = read(); } int sgn = 1; if (c == '-') { sgn = -1; c = read(); } int res = 0; do { if (c < '0' || c > '9') { throw new InputMismatchException(); } res *= 10; res += c - '0'; c = read(); } while (!isSpaceChar(c)); return res * sgn; } public String readString() { int c = read(); while (isSpaceChar(c)) { c = read(); } StringBuilder res = new StringBuilder(); do { res.appendCodePoint(c); c = read(); } while (!isSpaceChar(c)); return res.toString(); } public double in_d() { int c = read(); while (isSpaceChar(c)) { c = read(); } int sgn = 1; if (c == '-') { sgn = -1; c = read(); } double res = 0; while (!isSpaceChar(c) && c != '.') { if (c == 'e' || c == 'E') { return res * Math.pow(10, in_i()); } if (c < '0' || c > '9') { throw new InputMismatchException(); } res *= 10; res += c - '0'; c = read(); } if (c == '.') { c = read(); double m = 1; while (!isSpaceChar(c)) { if (c == 'e' || c == 'E') { return res * Math.pow(10, in_i()); } if (c < '0' || c > '9') { throw new InputMismatchException(); } m /= 10; res += (c - '0') * m; c = read(); } } return res * sgn; } public long in_l() { int c = read(); while (isSpaceChar(c)) { c = read(); } int sgn = 1; if (c == '-') { sgn = -1; c = read(); } long res = 0; do { if (c < '0' || c > '9') { throw new InputMismatchException(); } res *= 10; res += c - '0'; c = read(); } while (!isSpaceChar(c)); return res * sgn; } public boolean isSpaceChar(int c) { if (filter != null) { return filter.isSpaceChar(c); } return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1; } public String next() { return readString(); } public interface SpaceCharFilter { public boolean isSpaceChar(int ch); }}
This is the kind of reason why I switched to C++. Watch out for TreeSet too, if you have to use it with a constant factor > 5 then you will TLE even in n log n.
It's not like Java users have to face difficulty due to input output. Most of the times if efficient reader is used, it will pass the time limits. And for the TreeSet, I have never got TLE with it and this is for sure that since Java is supported in ACM ICPC and all other prestigious contests where other languages like python aren't allowed, you dont have to worry about such stuff. If proper algorithm is applied, you'll pass the test.
I would like to see a java solution to this problem:
http://usaco.org/index.php?page=viewproblem2&cpid=745 (4 second TL for java, 256mb)
I used the proper algorithm (n log n) and optimized forever. Still TLE on 6 out of 10 cases. Then I copy-pasted the editorial code. TLE on 4 out of 10 cases. It's impossible to solve with java.
Then I tried to code it in C++. Passed in n log^2 n. TreeSet/Map is just bad.