Getting Used to Contest Style

Introduction


No one could resist the impulse to say WTF when first seeing the code of a programming contest problem solution. Contest style code seems to ignore all the code-writing protocols — self-explanatory variable names, well-defined functions, clear comments, and avoidance of global variables. To give you a taste of it, you might see something like this. 



#include <bits/stdc++.h>
using namespace std;
const int M = 1e9;
#define maxs 4096
int m, n, f[13][maxs], F[13], field[13][13];
bool state[maxs];
int main()
{
    scanf("%d%d", &m, &n);
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
            cin >> field[i][j];
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
            F[i] = (F[i] << 1) + field[i][j];
    int MAXSTATE = 1 << n;
    for (int i = 0; i < MAXSTATE; i++)
        state[i] = ((i&(i<<1))==0) && ((i&(i>>1))==0);
    f[0][0] = 1;
    for (int i = 1; i <= m; i++)
        for (int j = 0; j < MAXSTATE; j++)
            if (state[j] && ((j & F[i]) == j))
                for (int k = 0; k < MAXSTATE; k++)
                    if ((k & j) == 0)
                        f[i][j] = (f[i][j] + f[i-1][k]) % M;
    int ans = 0;
    for (int i = 0; i < MAXSTATE; i++)
        ans += f[m][i], ans %= M;
    cout << ans << endl;
    return 0;
}

One of the first things I found challenging in competitive programming was this grotesque style of coding, which is the product of participants' insatiable desire to code faster. Even if you are shrew in C++, it could be torture trying to read the solutions written by experienced contestants. Just figuring out the roles of variables takes forever, not even mentioning the underlying algorithms. 

Perhaps this uncanny coding style is the culprit that scared many people away from competitive programming. Because if you cannot read the code, you will have a hard time understanding the solutions. If you don't fully understand the solutions, it's hard for you to get better. Therefore, in this article, I will unveil the arcane coding style of competitive programming and clear the first obstacle on your way to enjoying programming contests. 

To point out before you continue reading, the following contents are in C++. It is the most widely used language in contests like ICPC and OI because it is speedy yet not as complicated as C. Unless for some unique problems — like those which require big integer operations — C++ is almost always your best choice. 

1. Global Variables — they make your life a lot easier. 


The first thing to notice in contest style code is the extensive use of global variables. It is a standard move to declare all the variables you could think of at the beginning of your code. For example: 



#include <bits/stdc++.h>
using namespace std;

int x,y,z,a[100];
bool t,s;

int main(){...}

To understand why people do this in contests, let’s first recall why we hate global variables in the first place. It’s because it would cause a problem called shadowing, which makes our programs error-prone. For example:


string a = "World"; 
void func(){
  //Local variable
  string a = "Bam! You are shadowed by me!"
  
  cout << "Hello" << a;  
  /*Prints out Hello Bam! You are shadowed by me!*/
}

Avoiding global variables during the development of large projects with thousands of line of code and potentially years of future maintenance is indeed worthwhile. But things are different during contests. In most cases, a solution to a particular problem wouldn’t exceed 100 lines of code. As long as you keep an eye on your variable names, global variables won’t cause any problem at all. 

1.1 The advantages of using global variables. 


First of all, since everything is global. You don’t need to pass values among functions anymore. That means there is no need to worry about pointers, or references, or calculating the scope of variables. Just declare every function as void, and you are good to go. Remember, during contests, we want to use every minute in thinking, not typing. 


int n, m, ans, arr[100];

void algorithmA(){
  /*Something*/
}

void algorithmB(){
  /*Something*/
}
int main(){
  algorithmA();
  algorithmB();
  cout << ans; 
  return 0;
}

Secondly, global variables get a free initialization — 0 for numbers and false for boolean. We know that when we declare local variables without initialization, they store random garbage values(not necessarily 0). If we need base case values for algorithms like Dynamic Programming, we need to use for-loops or memset function to initialize the arrays.  However, if you declare the variables as global, initialization is already there for you. 

1.2 The naming of global variables


Everyone has their habits in terms of naming global variables, but there is one universal principle: names should be as short as possible. Here are some popular names for different kinds of global variables. Notice that it’s totally OK for you to develop your own naming conventions, but familiarizing yourself with these names can make it much easier for you to read solutions written by others. 


/*Common names for input data size*/
int n,m,k;

/*Common names for input data*/
int a[105];
int mat[105];
int arr[105];

/*Prefix sum array or other arrays related to sum*/
int s[105];

/*Common names for Dynamic Programming arrays*/
int f[105][105];
int dp[105][105];

/*Starting node for graph problems*/
int s;

/*Variables that store final answer*/
int res;
int ans;

/*Counter variables*/
int cnt;
int c;
int tot;

/*Temporary Variables*/
int t;
int tmp;

2. Primitive arrays — they can represent everything. 


We use primitive arrays and some basic STL data structures to store everything. You might be thinking: what if my array size is variable? Luckily, every contest problem will specify the upper bound of data size and use the first line of input to tell you how many lines of data are in a particular test case. You can just declare arrays with the size of upper bounds. Contest judges want problems to be about algorithms, not I/O. Here is an example of a contest problem.

Here is how you can store data in this problem.


#include <bits/stdc++.h>
using namespace std;
int a[105]; /*Since we know n <= 100, 105 should be enough*/
int n; /*n is used to store input size*/
int main(){
  cin >> n; 
  for(int i = 1; i <= n; i++)cin >> a[i];
  /*Solve the problem*/
  /*...*/
}

For now, just remember you have to befriend yourself with primitive arrays. In future posts, I will introduce how you can represent more complicated data structures with primitive arrays. 

3. Structs — all you need for OOP.


Contestants almost never define full-fledged classes to store data. It’s like using a supercomputer to do arithmetics. Forget good-old object-oriented programming rules here because ain’t nobody got time for that. When there is a need to encapsulate data, we turn to super lightweight structs. Just specify the data it stores and you are good to go. Here is an example of using structs to store edges in a directed graph.


struct Edge{
  int to, w;  /*The node it points to and the edge weight*/
};

If you want to create an array of edges, just tail the struct definition with an array declaration. If this statement is global, all the member variables are initialized to default values. 


struct Edge{
  int to, w;  /*The node it points to and the edge weight*/
}arr[105]; // Creat an array of Edge called arr.

You don’t even need constructors. Here is an example of pushing an Edge to a vector. Notice the statement inside the push_back function creates an Edge object, and the order of data has to match the ones in your struct declaration. 


/*Push back an Edge with weight 2 pointing to node 4 to vector 'vec'. */
vec.push_back((Edge){4,2}); 

4. Macros — get rid of meaningless numbers in your code.


In contest problems, there are always some constants. The most frequent ones are the upper bound of data size. Another common one would be infinity. Macros can save you a lot of time when these constants are used very often. 


#define N 10005 //Max size
#define M 200005 //Max size
#define INF 1999999999 //Infinity

int arr[M][M], f[N], s[N];

5. Cstdio — it can save your life sometimes. 


When it comes to scanning input data, some people prefer cin/cout. I used to be one of them until I ran into problem 919c on codeforces. Admittedly, cin/cout can be pretty smart and user-friendly, they will get you TLE(Time Limit Exceed) on some I/O heavy test cases. Therefore, it’s always good to familiarize yourself with that.


#include <cstdio> 

There are many functions in cstdio, but all you need to know is scanf and printf. Click the link for detailed usage clarification and examples. 

Summary


Up to this point, we have discussed some basic routines when it comes to writing fast contest code. If you internalize all these habits, it should get you started on reading other people’s solutions quickly. There are, of course, many other techniques. But those are hard to remember without understanding the related algorithms first. I will introduce them in future posts. 


Copyright © 2019 by Kangmin Tan. All rights reserved.

For permission to reprint articles from this site, please contact kangmint@usc.edu.

Categories contest
%d bloggers like this: