ACM International Collegiate Programming
Contest

Greedy Algorithms
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.
Problem Set

Dragon of Loowater

Advertisement

The Grand Dinner

Fill the Containers

Marbles on a tree
A PDF containing all the problems is available
here.
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
"Main".
Greedy Algorithms
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 wellchosen order, and sets them in a way that is
locally optimal (according to a wellchosen metric), rather than
trying to figure out what will work longterm. 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.
