10 Things to Remember and Do When Participating in International Student Programming Competitions

Today I’m going to tell you about the International Collegiate Programming Contest (ICPC) and give some advice to those who might take part in a student programming competition.

Credit: www.u-aizu.ac.jp

First of all, let’s talk about the rules of these competitions. There are many different types of programming contests. Today we are talking about team contests for students, and these contests usually adhere to the rules of ICPC. Teams consist of three students and are provided with one computer for 5 hours. During these 5 hours, teams are tasked with solving a set of problems. Every problem contains a description of the input data your program should read, the way you need to handle the data, and the information your program should output. For example, the problem may be as follows: Read an array of integers and output their sum (It's unlikely that you’ll encounter such a problem in a real contest because of its simplicity).

Each problem has a fixed set of tests, and when your team submits a solution, the solution will be tested on this set. The program will be run on every test, and its output will be checked for correctness. If the output of the program is incorrect on any test, the program will get the wrong answer (WA) verdict. If the program uses too much memory, it will get the memory limit exceeded (ML) verdict, and if the program works too slow, it will get the time limit exceeded (TL) verdict. If the program passes all the tests, it will get the OK verdict.

When a team gets the OK on any problem, they receive a penalty equal to the time that has passed since the start of the competition. Teams also receive a 20 minute-penalty for every wrong attempt. Teams are sorted in decreasing order of the number of solved problems, and then in ascending order of penalty.

With this in mind, we can proceed to the advice.

1. Limits are also part of the statement. Every problem contains time and memory limits, and constraints on input data. These limits and constraints may affect the complexity of a solution. For example, there may be a task: Read an array of integers and output them in ascending order. Then, there should be a constraint on the length of an array. If the length of an array isn’t larger than 1000, you may write a solution using bubble sort algorithm, and it will fit in 1 second. But if the length of an array is up to 100,000, you should use a more optimal algorithm like, say, quicksort.
2. Test your code before submission. As you already know, every wrong submission nets you an additional penalty. That’s why you should be sure that your solution at least passes all the samples of tests, which are written in the statement. It might also be helpful to test the solution on some edge cases and run the solution on some maximal tests to check if it fits within the time limit. Of course, you will need to generate these tests by yourself.
3. In most team competitions it’s possible to print your source code during the contest. This may sound weird to you. Why would someone print code if they have a computer? But don’t forget that teams consist of three people and they have only one computer. So, if one participant occupies the computer while finding a bug, his teammates cannot write a solution for another task. That’s why they can print their code and read it from paper.
4. Don’t supervise the one who is sitting in front of the computer. Unless they’re working on a really hard problem or there are no other tasks left to solve. This is important because you won’t speed your teammate up much if you help them, but you can solve some other problem in the meantime. And when they finish and you’ll need to write solution for the next problem, you’ll have more choice as to what to code next.
5. Coupled with the previous, organize your workplace such that the one who is sitting in front of the computer doesn’t sit between the other two people. Since these people won’t communicate with the third, they will communicate with each other.
6. Solve problems together with your teammates. This is a huge advantage of all team contests. Someone suggests an idea, and someone else develops it. And together you’ll solve a task much faster.
7. Problems aren’t usually sorted in terms of complexity. That’s why you need to read all the problems. The best thing to do is to have every problem read by someone in the first hour. You may also look at the standings to see which tasks are easier.
8. If you’ve spent a lot of time on some problem and still didn’t manage to solve it, switch to another problem. When you return to this one later, you may get a new idea. There are too many problems and too little time to spend all of it on one problem.
9. If you don’t know if there’s a bug in your code or you have written a hard problem with many tricky cases and don’t want to get a lot of penalty points for a wrong solution, you might implement a stress test. A stress test is a way to automate the process of testing your solution. To use it, you need to write a slow solution for the same problem, which will surely be right. After that, you can write a script which will generate a small random test many times, run both solutions on this test and compare their outputs. If the outputs aren’t equal, it will stop, and you’ll get a test on which your solution doesn’t work. In most cases, if your program is wrong, it will fail on some small test.
10. Don’t forget that a contest is still just a contest. It's not worth it to get too upset due to a bad result. Participate for your enjoyment. And good luck!