A collection of useful tips, tricks and traps. Feel free to contribute through sending an email or through a Piazza post.

A useful Makefile

Create a file called Makefile in your directory (or just home directory for exams) with these contents (copied verbatim)

CXX = g++
CPPFLAGS = -Wall -Wextra -Wshadow -Wformat=2 -Wfloat-equal -Wconversion -Wlogical-op \
           -D_GLIBCXX_DEBUG -D_GLIBCXX_DEBUG_PEDANTIC -D_FORTIFY_SOURCE=2 \
           -fsanitize=address -fsanitize=undefined -fno-sanitize-recover -fstack-protector \
           -O2 --std=c++14 \

These extra flags do a mix of static analysis and extra run time checks that catch some common mistakes in your program. Many instances of undefined behavior now at least trigger a warning when you run the program, instead of (worst case) silently working.

This is not a panacea though. It won’t catch anywhere near all bugs, but it catches some particularly simple ones.

One extra warning: these flags slow down execution speed dramatically. So switch to something more light weight if you need to run a program for a while or you want to get a gauge of the running time of a program.

A brute force comparison script

For many problems, a useful way of debugging is to write a brute force and a random data generator and repeatedly generate data and compare the brute force’s output to your program’s output until there’s a mismatch. This is particularly useful for problems with subtasks where you can use the subtask solution as your brute force.

For this, I will assume you have:

  • Your solution is an executable named soln.
  • You have a brute force executable named brute_force.
  • A random data generator titled gen. I usually write these in Python.

Then to generate random data until there’s a mismatch, just run

./gen > random.in; while diff <(./soln < random.in) <(./brute_force < random.in); do echo "all good"; ./gen > random.in; done

If this ever stops, a mismatch has been found and the input responsible is stored in random.in.

Speeding up IO

Iostream

Iostream and cin/cout by default are quite a bit slower than scanf/printf. This occasionally matters for problems with a lot of input. To speed up input, add the following lines directly below main:

int main() {
    cin.tie(nullptr);
    cin.sync_with_stdio(false);

The former stops cout from flushing every time cin tries to read (having cout flush is desirable for interactive programs but it introduces unnecessary flushing in our case).

The latter unsyncs iostream from cstdio. Calling this speeds up input even if you aren’t using cstdio but you should not then use C style input in your program.

Endl

There are 2 common ways to print a new line when using cin, either << '\n'; or << endl;

The difference is the latter one flushes output. Again this is desirable for interactivity but frequent flushing is extremely slow. For competitions, you should generally use '\n' not endl.

Common Traps

Overflows

  • Whenever you find yourself needing to multiply ints, check if you should use long longs instead.
  • If you are working mod a large prime (usually 1000000007), check you mod at each step. This is easiest if you define a helper function.

Mod negative numbers

  • C++ % is a bit weird, -5 % 3 == -2, not 1 as you might expect. If you need to subtract 2 numbers mod a prime, you might want to have a helper function along the lines of

    long long madd(long long a, long long b) { return ((a+b) % MOD + MOD) % MOD; }

Oddities with DOMJudge

First, note that you only get 1 verdict back and there’s no guarantee which it is. So just because you have a TIMELIMIT verdict, it doesn’t mean your program doesn’t also have a run time error.

RUN-ERROR

This is the most mysterious verdict. It essentially includes all possible run time errors for your program. These include, but are not limited to:

  • Going out of bounds.
  • Exceeding memory limits (by default you are given 512 MB).

And strangely enough:

  • Your program returning a non-zero exit code.