What are some cool C++ tricks to use in a programming contest?

Using auto to declare dataypes can save lot of time during programming contests.

When a variable is defined as auto, compiler determines its type during compile-time. For example,
  1. auto a = 1; // a will become 'int'
  2. auto b = 1LL; // b will become 'long long'
  3. auto c = 1.0; // c will become 'double'
  4. auto d = "variable"; // d will become 'string'

This is extremely useful when dealing with iterators. For iterating over map<int,vector<int>> Map, instead of writing this,
  1. for(map<int,vector<int>>:: iterator it = Map.begin(); it != Map.end(); it++ ){}

it is possible to write this.
  1. for(auto it = Map.begin(); it != Map.end(); it++ ){}

There is an even shorter way to write it.
  1. for(auto &it : Map){}
These type of loops are called range based loops, previously which was supported by java only. Note that, it is not an iterator in range based loops. So for accessing elements, it. should be used instead of it->.
  • Loop in C-string:
  1. char s[100];
  2. for (int i = 0; s[i]; ++i) { ... }
This is extremely useful (also avoids the strlen usage, that you could forget is O(n) and put on for condition).
  • Testing if not negative 1:
  1. if (~x) { ... }
In competitive programming we tend to write as little as possible, só a simple x ! = -1 can be shortened to 2 characters.
This works because negative numbers use two’s complement, so -1 is represented as all ones in binary. The tilde (~) operation inverts all bits of the variable, so the -1 turns into a zero, and any other number turns into something not zero. The if condition is valid if it’s not zero, so ~x is valid for any value different than zero.
  • Least significant 1 bit
  1. int lsb = x&-x;
This is a very useful operation than returns the LSB (EDIT: the least significant bit with value 1) of a number. If you’re used to Fenwick Tree (aka Binary Indexed Tree, or just BIT) then you know how useful it is.
This also works because of two’s complement. If you AND any number and it’s negative you obtain the LSB. Very simple and fast.
  • More than one operation per line
  1. if (dist[v] > dist[u] + w)
  2. dist[v] = dist[u] + w, q.push(v);
Many people don’t know this, but you can have statements split by commas. This I tend to use in every problem I solve, it reduces the code and avoids the use of semicolons.
The only down side is that you can’t use with breakcontinue or return (not statements :/). So when I have to use any of these I have to add braces and semicolons.
  • Scanf on array
  1. int a[100];
  2. for (int i = 0; i < n; ++i) scanf("%d", a+i);
This I don’t like very much because it doesn’t work for arrays with higher dimensions, but since most problems have at most 1D input it’s quite useful too (although I tend to use the &a[i], but my teammates use this trick).
  • Order array without losing original order
  1. int a[100], p[100];
  2. // receive input
  3. for (int i = 0; i < n; ++i) scanf("%d", &a[i]), p[i] = i;
  5. sort(p, p+n, [=](int i, int j) { return a[i] < a[j]; });
This is extremely useful!
First you don’t lose the original order (for offline algorithms this can be necessary).
Second you can do the same for how many dimensions you have (for 2D points: x[] and y[]; or 3D: x[], y[] and z[]; or any number of arrays..) and you don’t have to create structures (lot’s of lines saved) or use tuple or pairs (these are annoying in competitive programming. Using pair of pair you have something like: x.first.second + x.second.second and you line goes extra large and hard to read).
  • Infinite
  1. const int INF = 0x3f3f3f3f;
This infinite constant is very useful too. I used to do something like x = 2e9; but I had to take care about not adding infinites (because of integer overflow) and stuff like this. This constant can be doubled without overflowing and also can be set very easily this way:
  1. int dist[1000];
  2. memset(dist, 63, sizeof(dist)); // 0x3f == 63
For shortest path algorithms I always use this (I used to tend -1 version, but I had to do additional checks to verify if dist == -1 and if not..) and in CP BFS and SSSP are very common problems.
I think that’s all for now. If I remember any other trick I’ll edit this post, but that’s all I can remember for now!

Amazing Facts about Programming

Amazing Facts about programming  The first programmer was a lady named Ada Lovelac . She was a writer and gifted mathematician...

Popular Tutorials