C++ I/O for Competitive Programming

Overview

These are some input parsing techniques I’ve learned in ‘Algorithmic Problem Solving’ class. It would be good to just memorize these patterns and be able to code this as quick as possible. This way I can focus on the logic itself.

Some Facts

Leading whitespace is ignored by cin.

For example,

1
2
3
int i, j;
cin >> i;
cin >> j;

And you type:

1
2
3
4
3
<enter>
54
<enter>

3 is read into i. The newline following the 3 is still on the input buffer. Since std::cin ignores whitespace, the first return is ignored. Then the integer 54 is read in to j and the second return is left on the input buffer.

Different Ways of Parsing Test Cases

Sometime Automatic Answer tells you how many test cases there are. Some problems say ‘parse until a termination line of all zeros’. Others will have you read until end of file.

This class allowed me to use Java or C++ and I used Java to solve many questions. But I am going to explain everything in C++ because I don’t really like Java.

1. Parse Until The End Of Line

The input will consist of a series of pairs of integers a and b, separated by a space, one pair of integers per line.

Sample Input:

1
2
1 5
10 20

code for parsing:

1
2
3
4
int a, b;
while (cin >> a >> b){
// logic
}

Input contains multiple test cases, and one case one line. Each case starts with an integer N, and then N integers follow in the same line.

1
2
4 1 2 3 4
5 1 2 3 4 5

code:

1
2
3
4
5
6
7
int n, a;
while (cin >> n) {
while(n--){
cin >> a;
//logic
}
}

The input will consist of a series of pairs of integers a and b, separated by a space, one pair of integers per line.

2. Parse Until The Terminating Line

Input contains multiple test cases. Each test case contains a pair of integers a and b, one pair of integers per line. A test case containing 0 0 terminates the input and this test case is not to be processed.

1
2
3
1 5
10 20
0 0

code:

1
2
3
4
int a,b,sum=0;
while((cin >> a >> b) && (a!=0||b!=0)){
// logic
}

Input contains multiple test cases. Each test case contains a integer N, and then N integers follow in the same line. A test case starting with 0 terminates the input and this test case is not to be processed.

1
2
3
4 1 2 3 4
5 1 2 3 4 5
0

code:

1
2
3
4
5
6
7
8
9
int num, n, i;
while((cin >> num) && num != 0)
{
while(num--)
{
cin >> a;
// logic
}
}

3. Known Test Cases

Input contains an integer N in the first line, and then N lines follow. Each line consists of a pair of integers a and b, separated by a space, one pair of integers per line.

Sample Input:

1
2
3
2 // tells there is going to be two test cases
1 5
10 20

1
2
3
4
5
int num, a, b;
cin >> num;
while (num-- && (cin >> a >> b)){
cout << a+b << endl;
}

Input contains an integer N in the first line, and then N lines follow. Each line starts with a integer M, and then M integers follow in the same line.

1
2
3
2
4 1 2 3 4
5 1 2 3 4 5

1
2
3
4
5
6
7
8
int num, n, a;
cin >> num;
while (num-- && (cin >> n)) {
while(n--){
cin >> a;
//logic
}
}

4. Parse File

1
freopen("input.txt", "rt", stdin);

IO Optimizations

Put the following line in the beginning of the program.

1
ios_base::sync_with_stdio(false)

This line turns off the synchronization between iostream (cpp) and stdio (inherited from c). The default is ‘on’ and it allows iostreams and stdio functions to be freely interleaved even for the same underlying stream. Turning it off allows iostreams to run faster.

1
cin.tie(NULL)

The second optimization technique is to break ties between cin and cout. By default, cin is tied to cout, which means that cout is flushed before any operation on cin. Turning it off also allows iostreams to run faster.

Use \n instead of endl since endl not only outputs a newline character, but also flushes the stream’s buffer.

Please refer to Yet again on C++ input/output for more detail.

References

Tips and Tricks for Using C++ I/O
Yet again on C++ input/output