ACM International Collegiate Programming
This session focuses on greedy algorithms.
If you are not
familiar with the relevant concepts and algorithms, or you need a refresher,
you can use the resources below.
Dragon of Loowater
The Grand Dinner
Fill the Containers
Marbles on a tree
A PDF containing all the problems is available
Note: All problems expect I/O to be done using standard input and standard
output. The solution to problems must be written in a single file.
If you are programming in Java the application class should be called
Many computational problems can be cast in the following format: You are
given a system consisting of a number of components that each can be set
in various ways. Your goal is to set them in such a way that a given
objective is optimized. A greedy approach to such a problem iterates over
the components in a well-chosen order, and sets them in a way that is
locally optimal (according to a well-chosen metric), rather than
trying to figure out what will work long-term. Most objectives are too
complex for such a myopic approach to yield a global optimum. But if
it does, then the resulting algorithm is often very efficient.
Designing a greedy algorithm boils down to determining the order in which
to consider the components, and figuring out the right metric. In doing so,
it is important to verify that this combination leads to the correct
solution - ideally by reasoning about the algorithm, or else by developing
appropriate test cases.
Examples of problems for which a greedy approach works include: shortest
paths in graphs with nonnegative weights (Dijkstra's algorithm, which makes
its decisions based on minimum distance) and minimum spanning trees
(Prim's algorithm, which makes its decisions based on minimum edge weight).
More examples and info on greedy algorithms, can be found in this Topcoder tutorial.