1. Introduction

The Contest

The International Collegiate Programming Contest (ICPC) is an annual international programming competition for students in their first five years of university. There are several layers of competitions: national (in our case the GCPC), regional (NWERC) and the ICPC world finals. Students participate in teams of three and strive to solve several programming problems. For each successfully solved problems, the team gets a colorful baloon and one point counting towards the final scoreboard.

The Problems

The problems in these programming competitions are short, concise and usually to be implemented within one program file. They read text as input and produce text as output. They are always algorithmic problems and not software engineering problems. They usually come with little story, motivating it as a (fake) real-world problem; followed by a more formal description, a sample input and a sample output. Here is an example that I just made up:

Problem 1.1 Dominik has just finished the washing-up. Now he wants to stack the bowls and stow them away in his cupboard. However, a bowl can only be stacked into a wider, and both breadth and heigh of his cupboard are limited (Dominik lives in a 2D flat, so depth is not an issue). Viewed from the side, all bowls are U-shaped and its bottom and sides have a thinkness of 1. Here is an example of how Dominik barely managed to stow them away:

Here is a configuration where one of the bowls does not fit into the cupboard, no matter how Dominik re-arranges them.

Input: the first line contains three integers w,h,n, where 1≤w≤105 and 1≤h≤104 are width and height of the interior of the cupboard, respectively, and 1≤n≤102 is the number of bowls. This is followed by n lines, each containing the description of one bowl, namely two integers w and h, the width and height of the bowl (the outer dimensions, i.e., including the thickness of the walls).

Note that the walls of each bowl have thickness 1, so a bowl of width 10 fits into a bowl of width 12 but not of width 11, and if you put a height-10-bowl into another bowl, their combined height is 10+1=11.

Output: a single line containing a single word, either possible or impossible.

Sample Input 1 
20 6 7
4 4 
3 4 
6 5 
6 5 
8 4 
4 4 
12 6
Sample Output 1 
possible
Sample Input 2 
20 6 4
6 5 
4 6 
11 6 
9 5
Sample Output 2 
impossible

This is a problem I made up without thinking too much (doing the drawings took lots of time though). I don't know how to solve it efficiently, nor whether an efficient solution exists at all. Most ICPC problems have an efficient solution, sometimes they are easy to spot, sometimes fiendishly difficult. Sometimes implementing them (in Java, C, Python, or other languages) is straightforward, sometimes it is extremely tricky.

This Course

Ideally, this course motivates some of you to participate in the German Collegiate Programming Contest (and maybe even in the regionals, or finals...), but this is in now way a requirement. Our focus will be twofold:

  1. Implementing fundamental algorithms or algorithmic concepts, like Longest Increasing Subsequence (Chapter 2.3) depth-first search and its variants, flow algorithms, or several brute-force search algorithms.
  2. Working on actual ICPC-style problems. Here we can use online repositories with huge number of problems, taken for local, regional, or final contests, labeled by difficulty and topic and so on. These repositories also come with online judges, i.e., you can upload your solution and it will be judged against a number of (hidden) test cases; the result will then be published on a scoreboard.

One thing that is crucial during an actual contest but which we will have to de-emphasize during this course is

  1. Speed. A contest runs for a limited number of hours, and the team that solves the most problems wins (ties are broken by giving preference to teams that solve their problems quickly). However, in this class, speed is not important. In fact, focusing on speed early on will be detrimental to your programming skills and ultimately also to your skills as a competitive programmer (if you plan to participate).

When I say that speed is not important I mean that you should take time really thinking your solution through, designing test cases, and being careful when actually implementing the solution. What often matters is the speed of the algorithm. Often, problems have an obvious but inefficient solution, for example of time complexity O(n2), but a clever one with linear running time. In that case, you can be sure that some test cases are designed to make your O(n2) solution fail with a time limited exceeded error.