Tipps and Tricks

for programming contests

Goal

Reduce time spent by coding and debugging.

These coding guidelines help you code faster and with less errors during contests.

Containers

  • std::vector<T>
  • std::map<K,V>, std::set<T>
  • std::deque<T> (std::stack<T>, std::queue<T>)
vector<int> v(4); // v={0,0,0,0} v.size()==4
v.clear();        // v={}        v.size()==0
v.push_back(4);   // v={4},      v.size()==1
v.push_back(6);   // v={4,6},    v.size()==2
v.push_back(3);   // v={4,6,3},  v.size()==3
v.pop_back();     // v={4,6},    v.size()==2

Do not use: std::list (more than 3× slower in almost any case).

Maps

Key-value mapping, always sorted

map<int, int> m; // m={},           m.size()==0
m[3] = 5;        // m={3: 5},       m.size()==1
m[7] = 2         // m={3: 5, 7: 2}, m.size()==2
int x = m[2];    // x=0, m={2: 0, 3: 6, 7: 2}, m.size()==3

Range-based for loop

vector<int> v{3,1,4,1,5};
for (int i : v)
  cout << i << '\n';
// prints 3 1 4 1 5

map<int, int> m;
m[3] = 5; m[7] = 2; m[1] = 3;
for (auto& p : m)
  cout << p.first << ' ' << p.second << '\n';
// prints 1 3, 3 5, 7 2

Iterators

  • More general pointers
  • container.begin(), container.end()
  • Dereferencing: *it = x
  • Incrementing: it++ und it += n
  • Comparison: it == it2
vector<int> v{5,2,3};
for (auto it=v.begin(); it!=v.end(); ++it)
  std::cout << *it << ' ';
// Output: 5 2 3

auto it=v.begin();
*it = 0;   // v={0,2,3}
it += 2;   // it points to 3
*it = 9;   // v={0,2,9}
*--it = 4; // v={0,2,9}

Algorithms

Do useful things with iterators!

  • std::sort
  • std::binary_search, std::lower_bound, std::upper_bound
  • std::unique
  • std::reverse
  • Doc: http://en.cppreference.com (available on grader too)

Use algorithms

Algorithms work between two iterators: start and end (exclusively).

vector<int> v{5,4,3,2,1};
sort(v.begin(), v.begin()+2); // v={4,5,3,2,1}
sort(v.begin()+2, v.end());   // v={4,5,1,2,3}
sort(v.begin(), v.end());     // v={1,2,3,4,5}

bool func(int lhs, int rhs) {
 return tie(lhs&1, lhs >> 1) < tie(rhs&1, rhs >> 1);
}
sort(v.begin(), v.end(), func);
// v = ?

Why STL

Pro STL:
  • Debugging with -D_GLIBCXX_DEBUG
  • Integrated interface for algorithms
  • Not slower than raw arrays
So:
  • Do not use arrays
  • Do not use new/delete

Input/Output

#include <iostream>
int n;
cin >> n;
vector<int> v;
for (int i=0; i<n; ++i) {
  int x;
  cin >> x;
  v.push_back(x);
}
cout << n.size() << '\n';

Do not slow down your programs:

  • Avoid std::endl!
  • std::endl='\n'+std::flush and std::flush is slow, especially on our grader.

Use I/O Streams

Use the I/O streams instead of printf and scanf.

  • No bugs with wrong flags (%d but long long)
  • Change types easily (int -> long long)
  • Equally fast

Make it even faster:

// Turn off synchronization between cin/cout and scanf/printf
ios_base::sync_with_stdio(false);

// Disable automatic flush of cout when reading from cin
cin.tie(0);

Terminal Basics

Change directory:

cd <directory>

Show current directory:

pwd

Show files in directory (list):

ls

Compile

g++ -Wall -Wextra -std=c++11 -g3 -ggdb3 -D_GLIBCXX_DEBUG x.cc -o x
-Wall -Wextra:

Enable warnings and extra warnings

-std=c++11 or -std=c++14:

Enable C++11. If you have a more recent gcc, you can also enable C++14.

-g3 -ggdb3:

Write debug informations for gdb.

-D_GLIBCXX_DEBUG:

Bound-checking for containers and iterators

Testing

Input the sample file:

./prog <sample01.in

Input all sample files:
for f in *.in
do
  echo "-- $f --"
  ./prog <$f
done
Short:
for f in *.in; do echo "-- $f --"; ./prog <$f; done
                                                                                             

Debugging

In case of a crash use gdb (Gnu DeBugger):
$ gdb prog
(gdb) run <sample01.in
(gdb) bt

printf-Debugging

Print state information:
for (int i=0; i<10; ++i) {
  cerr << "i=" << i << " sum=" << sum << '\n';
  sum += i;
}
Useful macro for debugging:
#define DEB(x) cerr << x << '\n'

for (int i=0; i<10; ++i) {
  DEB("i=" << i << " sum=" << sum);
  sum += i;
}
Before submitting: remove it at one place
#define DEB(x) // cerr << x << '\n'

Locating the error

If wrong answer:

  • Do you have a counterexample? If yes: printf-Debugging
  • Tink of counterexamples and corner cases and test them
  • Why is the approach correct?
  • Read task description again
  • Read code
  • Try other tasks
  • Write brute force solution, automatically generate tests and check against your solution

Time limit: 1 second = 107 calculation steps.

Error prevention

Use std::assert.

#include <cassert>

void dfs(int n) {
  // n must not be visited
  assert(!graph[n].visited);

  graph[n].visited = true;
  for (int nb : graph[n].adj) {
    if (!graph[nb].visited)
      dfs(nb);
  }
}

Include everything

#include <bits/stdc++.h>

RTFM

Read the doc: http://en.cppreference.com