Contest format
5 hours, around 8-12 problems
One computer running (likely)Linux, plus printer
3 people on one machine
No cell phones, calculators, USB drives, Internet
(C++ STL available, and java api’s
are available)
• All the paper resources you want, including
books, print outs of code, anything!
– If it fits in the van, bring it!
• Sorted first by number of problems solved
• Then sorted by time
– If you submit a problem at :30 and one at 1:30,
your total time is 120 minutes
– Find the easy problems and do them first!!!
– Watch the standings and see what other teams
are doing!
– 20 minute penalty for wrong answer on a single
submission, but it’s only counted if you eventually
solve that problem
• You will receive one of several responses:
– Format error
– Time limit reached
– Runtime error (division by 0, out of memory,
exception thrown, etc.)
– Compile error
– Wrong answer
– Correct!
• The judges only give you one at a time
– If you have two or more problems, you’ll usually only
get the more embarrassing of them
Always have someone typing
• Typing and compiling is time intensive, and
there’s only one keyboard
– If your program isn’t working, print it and debug it by
– Let someone else sit and type!
• If you’re waiting for the computer, write some
code out by hand or ask a neighbor for their
opinion on your algorithm
• If it has you read until end of input, use:
while (cin >> x)
• You can submit questions to the judges about
• Updates will be given to everyone if there is a
typo or other error
• You will get one of two responses:
– A clarification
– No answer (i.e. read the problem more closely)
Test the judge’s input
• They give you 1 or 2 sample inputs and
solutions; test them!
– There will normally be simple cases.
• Make sure your format exactly matches the
judge’s sample output!
– They use a file compare (via a script) so it must be
very close
End cases
• The judges are very tricky with their tests
• If the problem says inputs will be between A
and B, you can almost bet that inputs of size A
and B will be tested
• Be wary of carefully worded questions!
Tree or not a tree
A tree is a well-known data structure
that is either empty (null, void,
nothing) or is a set of one or more
nodes connected by directed edges
between nodes satisfying the
following properties:
– There is exactly one node, called
the root, to which no directed
edges point.
– Every node except the root has
exactly one edge pointing to it.
– There is a unique sequence of
directed edges from the root to
each node.
Counting characters in a range
• Input will consist of two
integers, 0 < N < 100
• For each of the numbers
in between these two
numbers (inclusive),
count the occurrences of
each digit
• Example: 17 21
– 17 18 19 20 21
– 0=>1
• cin >> a >> b;
for (i = a; i <= b; ++i)
++arr[i / 10];
++arr[i % 10];
• 17 21 ?
• 21 17 ?
Be generous with your memory!
• Make your arrays twice as big as necessary
– Off by one error are difficult to find!
• Use the STL (strings, vectors, everything!)
• Use long long instead of int
• Use double instead of float
Code quickly at the cost of efficiency
• The faster you type, the faster you submit!
• Use the STL if it makes it easier for you
– If you can’t remember how to use the STL sort,
write a simple (bubble?)sort. Who cares!
• Generally, if you get a “time limit reached”,
your algorithm needs to be changed, not just
little things in your code
Helpful suggestion
• Bring printed code, such as the algorithms
we’ll talk about.
• You won’t have to remember them and know you have
a working/correct version too.
– If someone is not typing in an answer, type in the
algorithm so the template is ready to use.
– Also data structures you may want to use (trees
for example).
– Including a “read a file” code. You know it works,
then one least thing to think about.
• Number theory
– Very popular in the program contests
– For ICPC, you need a rather small but useful set
• Prime table generation, primality testing, greatest
common divisor, modular arithmetic and congruence
(solving linear congruences), and Euler’s
– A Note, Java’s BigInteger class has a number of
number-theoretic functions, like gcd, modular
exponentiation, primality testing, etc.
String manipulation
• There have been a number of string
manipulation questions over the years.
• Learn the string library
– At the least substring, replace, find etc.
– Regex maybe really helpful.
• Brute force algorithms
– From nested loop algorithms to backtracking (easier
with recursion).
• Breath first search.
• Depth first search is recursive and has nice bracktracking
• Dynamic Programming
– Recursive algorithm that is composed of subproblems
• Coin flipping and fibonacci are simple examples
• Longest Common Subsequence (LCS), Longest Increasing
Subsequence (LIS), Optimal Binary Search tree (OBST), 0-1
knapsack, edit distance, Matrix Chain Product are increasing
harder examples.
• Trees and priority queues, not necessary an
algorithms, but can speed things up.
• Graph theory
– How to represent things and then use BFS and
DFS, and topological sorting.
• Does the graph have cycles?
Classic Problems algorithms
Shortest paths (Dijkstra for example)
Spanning trees (Prim or Kruskal)
Eulerain paths and circuits
Matchings in bipartite graphs
Network flow (max flow, min cost flows)
• Geometry.
STL: Deque
• #include <deque>
• deque<int> x;
• x.push_back(20); x.pop_back(); x.back();
x.push_front(20); x.pop_front(); x.front();
• x.resize(100);
• x[10] OR;
• x.clear();
STL: Strings
#include <string>
string str; string str(“foo”); string str(10, ‘c’);
str += “bar”;
str.find(“aaba”); str.rfind(“aaba”);
str.find_last_not_of(“AEIOU”, 5);
Returns an int, or string::npos if none found
• str.substr(int position, int length)
STL: Algorithms
• #include <algorithm>
• swap(a, b); // Any type that has = can go here!
• reverse(arr, arr + 10);
reverse(deq.begin(), deq.end());
• Sorting
– sort(arr, arr + 10); sort(deq.begin(), deq.end());
– sort(arr, arr + 10, lessThanFunction);
bool lessThanFunction(const Type& t1, const Type& t2)
if (t1 < t2)
return true;
return false;
STL: Algorithms
• #include <algorithm>
• Permutations
int x[] = {3, 5, 4, 1, 2};
sort(x, x + 5);
do {
// stuff
} while (next_permutation(x, x + 5));
STL: formatting
• #include <iomanip>
double d = 12345.6789;
cout << d << endl;
cout << setprecision(3) << d << endl;
cout << setprecision(3) << fixed << d << endl;
cout << setprecision(1) << fixed << 0.55 << endl;
int i = 42;
cout << hex << i << endl;
cout << hex << uppercase << i << endl;
cout << i << endl;
cout << dec << i << endl;
• Brush up on
– depth-first search, breadth-first search (or just use
iterative deepening DFS)
• N-Trees, but lots of other uses as well.
• minimum spanning trees
– Lots of varying algorithms
listed at the bottom of the page
Algorithms (2)
• shortest path, like Dijkstra’s algorithm
• (Max) flow problems
• Good demo of max flow and min cut algorithms.
• Also links to some other versions of spanning tree
Algorithms (3)
• Greatest common divisor is a fun one to
remember too
– And remember, if gcd(a, b) == 1, then a and b are
relatively prime!
Dynamic programming/memoization
• Recursive algorithm that is composed of
– You keep recomputing the subproblems!
– Save them in an array and look them up
– Start with the recursive version first, then modify
it to save work
• Examples
– Fibonacci
– Coin problem
Geometric algorithms
Geometric algorithms
• Intersection
– Four points: a1, a2, b1, b2
– Compute:
dir1 = direction(b1, b2, a1)
dir2 = direction(b1, b2, a2)
dir3 = direction(a1, a2, b1)
dir4 = direction(a1, a2, b2)
– If dir1/dir2 are opposite signs, and dir3/dir4 are
opposite signs, they intersect

similar documents