Блог пользователя ZhassanB

Автор ZhassanB, история, 7 лет назад, По-английски

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.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +32
  • Проголосовать: не нравится

Автор ZhassanB, история, 8 лет назад, По-английски

Greetings! My solution to the problem B in Codeforces Round 358 div2 edition, surprisingly failed at 105 th test with verdict 'time limit exceeded'. My code was written in Java, and simply run at O(n) time. I have tried many times by changing Scanner to BufferedReader, but still cannot realize the reason why it cannot pass the time limit. Here is my code. Can somebody guess the reason of failure?

P.S It is not because of Scanner and not because of java compiler version. Moreover I have checked with generated input in my computer and it works fine in about 100 to 250 ms.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +9
  • Проголосовать: не нравится