German Collegiate Programming Contest
Designing low-time complexity algorithms is a lot of fun. Algorithms are, of course, a foundational component of theoretical computer science. Typically, designing an algorithm would entail proving the algorithm’s and its complexity’s correctness mathematically. Proofs are great, but I feel like most software engineers have thought: what if I just implement my idea and run some unit tests? (Of course I realise that this does not work reliably for algorithms which haven’t already been analysed mathematically…)
Introducing: competitive programming. As the name implies, competitive programming is oftentimes carried out in the form of a, well, competition. And one particularly enjoyable experience during my studies was participating in the German Collegiate Programming Contest (GCPC).
I took part as part of a team of three, an opportunity that arose from a prior course on competitive programming, which provided some foundational knowledge and practical experience ahead of time.
Competitive programming revolves around solving well-defined algorithmic problems under strict constraints. Each task specifies the format of the input and expected output, as well as a time limit within which the solution must run. The challenge lies in designing an algorithm that is not only correct for all possible cases but also efficient enough given the input size. Solutions are implemented and submitted to an online judge, where they are compiled and executed against a set of hidden test cases. Of course, the judge’s support does limit the languages usable for implementation. Our judge in class supported two of the most common ones: C++ and Python, and I chose to exclusively work with C++. The contest’s judge also allowed for Java and Haskell.
The GCPC itself followed this exact structure, albeit at a larger scale. We were presented with a problem set of thirteen problems of varying difficulty and given 5 h to solve as many as possible. Teams were ranked primarily by the number of problems solved and secondarily by the time taken to solve them, with penalties applied for incorrect submission attempts. An additional constraint was that each team was limited to a single machine, which introduced an interesting coordination challenge. While it might seem efficient to divide problems among team members, implementation and submission had to be carefully scheduled, encouraging a more collaborative and strategic workflow.
All problems can be found here. The final scoreboard can be found here. I recall solving problem J individually towards the end of the competition, while my teammates were figuring out F. J, in this case, is somewhat special. It included being given some binary string, then returning a ternary string of the same length, and then, in a second pass, receiving a transformed version of that ternary string back (the limits of that transformation are specified in the problem), which finally had to be decoded back into the original binary string. Meaning, my submission program was being executed twice per test case and had to function primarily based on an internally devised logic. If you are curious about the details, just check out the problem set linked above and try to solve some of the problems yourself. ;)
Our team approached the contest with a mix of joint problem-solving and individual contributions, constantly balancing discussion with execution time. In the end, we solved eight out of thirteen problems, placing 22nd out of 110 teams. Within our university, we ranked fifth, notably behind teams that all had prior competition experience, while it was a first for the three of us. Given that this was our first contest, I was very pleased with our result. Additionally, I was also graded a 1.0 (A) in my competitive programming course. The exam was, in fact, styled just like the GCPC, except it lasted just 4 h and the team size was two.