Competition Programming -- 15-195 -- Spring 2011

Danny Sleator
Eugene Fink
Richard Peng

This course is intended as a systematic introduction to the approaches and techniques required in programming competitions. Common types of problems will be covered on a topic-by-topic basis with minimal background assumptions. The students will learn a suite of implementational, algorithmic and mathematical techniques, and acquire skills in solving problems that require creative usage of various techniques.

Class Meetings: Monday 4:30 -- 5:50 GHC 4301

Grading in this 3-unit class will be based on class attendance and homework problems. Each week attendance will be taken in class, and each week there will be a homework problem assigned from the Timus on-line judge. An A will be awarded for 80% attendence and solving 80% of the problems.

Homework

To get credit for your these homework problems, you must get them accepted by the on-line judge before the start of class. Please also email your code to compprog195@gmail.com.

• Due April 18th, At least one of the following two problems:
  K-based Numbers (1009) , Square Country (1073)

  AND one of the following two problems: Folding (1238) , Binary Apple Tree (1018)

• Due April 11th, At least one of these problems:
  Duties (1641) , Pass Licenses (1500)
• Due April 4th, At least two of these problems:
  Two Rounds (1156) , Legendary Teams Contest (1208) , Penguin-Avia (1709) , Chase in Subway (1314)
• Due February 28th, At least one of these problems:
  Sightseeing Trip (1004) , Two Teams (1106) , Kind Spirits (1210)
• Due February 21st, At least one of these problems:
  Goat in the Garden 2 (1348) , Points on a Parallelepiped (1489) , Circle of Winter (1640) , Bookshelf (1753)
• Due February 14th, At least one of these problems:
  Metro (1119) , Mnemonics and Palindromes (1635)
• Due Feburary 7th, At least one of these problems:
  Bicolored Horses (1167) (solution), Brackets Sequence (1183) (solution) (solution in C++), Sum of Digits (1658) (solution), False Mirrors (1152) (solution)
• Due January 31st, At least one of these problems:
  Railway Tickets (1031) (solution) , Lucky Tickets (1036) (solution)

Addititional Problems Discussed

• Graph Problems Discussed March 28th:
  • Network (1160)
  • Team Them Up! (1182)
  • Evacuation Plan (1237)

• Problems Discussed March 21st:
  • Classmates 2(1362)
  • Archer's Travel (1459)
  • Lost in Space (1171)

• Geometry Problems Discussed March 14th:
  • Exactness of Projectile Hit (1215)
  • Tethered Dog (1246)
  • River Basin (1281)
  • Pool (1258)
  • Cemetery Guard (1256)

• Geometry Problems Discussed February 14th:
  • Goat in the Garden (1084) (solution)
  • Rabbit Hunt (1052) (solution)
  • Median on the Plane (1207) (solution)

• Towers of Hay
• Lenny's Lucky Lotto Lists
• Finding Seats
• Transversal
• Finding a Multiple

Topic List

• Dynamic Programming
• Graphs
• 2-D Geometry problems
• Strings/Stacks/Queues
• Search Trees and other data structures
• "non-trivial-for-loops"
• Strategies for writing long code

Resources

• Hints for Solving contest problems from U. Waterloo
• Timus online judge
• Sphere Online Judge a LOT of problems, and support for MANY languages
• Saratov State University Online Judge 400 VERY high quality problems
• Universidad de Valladolid Online Judge Comprehensive Archive of Past ACM problems
• PEG Online Judge Supports discussion, and a number of lanuages
• Click for Permenant Brain Damage