CS 97SI: Introduction to Programming Contests

Course Information and Announcements

Lecture slides

  1. Introduction

  2. Mathematics

  3. Data Structures

  4. Dynamic Programming (DP)

  5. Combinatorial Games

  6. Basic Graph Algorithms

  7. Shortest Path Algorithms

  8. Network Flow Problems

  9. Computational Geometry

  10. String Algorithms (Additional material: Suffix Arrays - A Programming Contest Approach)

Practice Problems

All the problems below are from Peking Online Judge (POJ). Submissions should be made directly to the automated judging system. Problems are classified into 10 different categories, and the lectures will cover essential algorithms and theoretical background for each particular category. The numbers in parentheses represent the difficulty of the problems (0: easiest, 10: hardest). The difficulty rating is subjective; you might find a 5-rated problem easier than a 4-rated one. But do not attempt the challenge problems unless you are sure that you can solve all the easier ones. If POJ is down, you can use the offline copies of the problems here.

Common coding mistakes

for(i = 0; i < n; i++);
  some code

for(i = 0; i < 1000; i++)
  for(i = 0; i < 10; i++)
    some code

#define min(a, b) a<b?a:b // incorrect
#define min(a, b) (((a)<(b))?(a):(b)) // correct

If you get stuck…