Programming Contest Resources
Table of Contents
Please see the
main website for our Mid-Central
Region for rules of the contest and other valuable information. The "Acrhives"
link on this page contains many years worth of past problems,
including access to the input and output used by the judges that
year, and even sample solutions written by the judges.
For most of the problems that we discuss in our practices here
at SLU, I will be placing the associated judges input/output
on our system so that you can have your submitted solutions
judged against that data in an automated fashion. This system
also tracks your submissions so that I can see your attempts and
examine your source code.
To submit a solution, you must be logged into turing or
one of the Linux Lab machines, and execute a command such as
/Public/goldwasser/icpc/submit sample.cpp
where sample.cpp is the appropriate source code for the
problem. Our system is willing to accept code in C++, Java, or Python
(although only C++/Java are allowed for the real ACM-ICPC contest).
Also, the filename (e.g., sample) must precisely match
the expectiations outlined in a problem statement, as we use
that choice of name to determine which problem you are
attempting.
Note:
Input/Output conventions on our system are the following. Input
will always be read from a file having a name such as
sample.in, where sample was the identifier for
the problem. Output should always be directed to standard
out. These are the conventions currently used for our
Region, so we use them for all practice problems (even if the
problem statement says otherwise).
Please see the complete list of
available problems for our online system.
The ACM-ICPC Live Archive
contains many years worth of past problems for
regionals and world finals, and it has an online submissions
system allowing you to upload source code to attempt to solve
problems using a feedback system similar to the contest.
The
UVa Online Judge is another site allowing you to submit attempted solutions
for a variety of programming problems. Much of its content has
been taken over by the new ACM-ICPC Live Archive, but there are
some additional problems on this site that were not from the ICPC
competitions. I'd recommend sticking with the Live Archive, but
if you run out of problems and need more...
The standard libraries for algorithms and data structures are
great assets for these contests, as many commonly needed
concepts are already coded and ready for you to use. Please
make sure that you familiarize yourself with them. Most notably:
- C++
For the Standard Template Library (STL), I prefer the
documentation from cplusplus.com, in particular
or else the corresponding
documentation from SGI's website.
- Java
For Java, the standard documentation is now located on
Oracle's
site. Of particular interest to this contest should
be the
Collections Library, which includes not only data structres for
common container types, but also general algorithms for sorting,
searching, min, max, etc.
Since we are allowed to bring books into the contest, its good
to consider what to bring. Here are some top choices of mine:
- Your Favorite Language Reference
Although some general documentation for the standard
libraries should be provided online during the contest,
better to not count on that. Bring your favorite quick
reference to the standard libraries (e.g., Nutshell
series). You want something that will help you quickly find that
library that you need, or to remind you of the interface for the functions.
- Introduction to Algorithms by Cormen, Leiserson, Rivest,
and Stein
This is the premier undergraduate and graduate textbook
and can be used quite well as a reference. It does not go
so far as to give you working code, but it describes high
level approaches for algorithms you might need (e.g.,
dynamic programming, common graph algorithms).
- Programming Challenges: The Programming Contest
Training Manual, by Skiena and Revilla
This is a book that is clearly marketed to programming
contestants. It is designed a bit better for advanced
preparation rather than as a desk reference for use during
the contest, but there are some useful pieces of code
there for some common tasks.
- Computational Geometry in C, by Joseph O'Rourke
This is a specialized book for problems that involve
geometric data. We usually see at least one of these
types of problems each year in our region, and this book
gives you code for many common geometric primitives that
you might not want to re-derive under time pressure:
do two line segments intersect, and if so, where; what is
the area of a triangle that is specified by its three
vertices, is a point within a circle, what is the tangent
line between a point and a circle. This book also has
thorough discussion of more advanced computational
geometry algorithms (e.g., computing a convex hull,
triangulating a polygon) that may be helpful in some cases.
In addition to books, we can bring in paper copies of any other
information that we wish to prepare, including complete source
code for many common tasks. In the long run, I envision a
comprehensive document covering everything you'd ever want to
know during a programming contest, with a thorough table of
contents for using this document. But for now, we'll have to
start writing some materials as we prepare. I'll manage
keeping all of this in a single document for the contest, but I
ask you to think about what sort of code you may have written
for one problem that seems reusable for other related problems.
Please see our current draft of such
a sheet (password required).
Michael Goldwasser
Last modified: Tuesday, 12 October 2010