2009/2010 ACM International Collegiate Programming Contest
University of Ulm Local Contest

# Judges' Comments on the Problems and their Solutions

Problem | Name | Rating | Method
A | Another lottery | easy | math, Euclidean algorithm
B | Ballot evaluation | easy | parsing
C | Cyclic antimonotonic permutations | medium - hard | pattern, dynamic programming
D | Dark roads | easy - medium | Kruskal algorithm, Prim algorithm
E | Elias gamma coding | medium - hard | dynamic programming
F | Food portion sizes | medium | brute force
G | Generate random numbers | easy | simulation
H | Hotel booking | medium | Dijkstra algorithm, breadth-first search

Problem A: Another lottery

The important observation to solve this problem is: only the winner of the last round m matters, since ∑i=1..m-1 2i = 2m - 1, so even if someone wins all previous rounds, he will have won less money than the winner of the last round. The probability for a participant to win the last round is the number of his tickets of round m divided by the total number of tickets sold for rou