2008 UM-D Programming Contest - Notes and Hints
- Judges wanted you to simply traverse the maze, while noting the length
of the path. The easiest way to do this is to use recursion with a
hint of backtracking.
- Judges tweaked the input to ensure that any valid program, even one that
explores every possible path till the end will not get "Time Limit
Exceeded". Turns out they didn't need to do that -- every successful
solutions ran fast even on the largest, most evil input that judges could
- Watch out for assumptions -- two or more ways through the maze may share
the same path at some point. If you are exploring a longer way and
mark it permanently as visited, you may miss out on a shorter way that
shares the same path at some point.
- Sample Code Skeleton:
int findShortestPath(int row, int col, int path,
if (out of bounds, hit a wall,
or path is longer than the shortest one found so far)
minimum path length;
if (reached the end of maze)
compare path length and min path
length, return one whichever's smaller;
mark path as visited by i.e.
assigning a number to it, like path length so far;
There are a few ways to solve this problem. The notable ones are:
- O(n log n) - sort names alphabetically, then go through the list once,
noting which name "run" is the longest one so far. At the end output
the name and the run.
- O(n2) - for each name A in the list, compare it to every
other name B in the list. Keep a counter table of how many names B
show up for name A. At the end find max value in the counter table and
print out the results.
- Watch out for case with only one name, depending on how you code things,
it may mess things up.
- Judges were nice this time and accepted O(n2) solutions.
- The judges were evil and have hand-selected sample input to trick you
into a simpler but incorrect solution (sum or speeds divided by sum of
times). Note that if you divide speed by time, you get acceleration
for your result, when problem specs asked for speed.
- Correct solution was for each interval to multiply v*t to get the
distance travelled for that interval. Then, to take the sum of all
distances travelled and divide it by the sum of times to get the average
speed, which is the answer.
- Judges got output-tricky by requesting you to output two
significant figures after the dot. One way to do it in C++ is:
using namespace std;
- Just for the record, you could also write a rounding function, such as
below, but then you'd have to write extra code to print dots and 0s at the
end when needed, i.e. for "3.00".
double round(double x)
- Judges' trick: a few people have missed that in problem statement
v and t were to be real numbers, not integers. Judges have used only
integers in the sample input to throw you off. Just another example of
evilness and things to watch out for.
- This was an easy yet somewhat tedious program to implement.
Originally judges allowed for input from 0 to 100, but later changed it to 0
to 99, which made for a slightly smaller number of cases to consider.
- Special cases to watch out for in output -- Zero, One hundred
- Recall that you can call toupper(), tolower() functions to change letter
case. You can also subtract 32 from small letter to get its capital
letter and add 32 to capital to get its smaller case.
- Nobody solved E during the contest.
- Dennis originally tried to think up the easiest problem possible.
For example, how about comparing three values together and then reporting
results of comparison ? Well, to make it more interesting, boxes were
invented. Originally no box rotations were allowed. But later an instructor
suggested to allow for box rotations, and so that's how the problem came to
life. That's also how it became to look more difficult than it meant to be.
- To solve this, first find box's width, length, and height. One way
to do this is to compute the difference of appropriate points, like (A-D),
(B-A), (E-A). Another to do this is to "move" the box so that point D
is at the origin, by subtracting appropriate values from all points, and
then take values A, C and H for width, length and height.
- Now, you can compare two boxes directly. To account for box
rotations, try all possible permutations of box dimensions for one of the
boxes, while keeping the other one static. There are total of 6
permutations to try. Care should be taken to report final results
correctly, as you'll have 6 answers, one for each rotation.
- Another way is to first sort the sides so that they are in order
smallest to largest, and then compare the boxes directly.
- Tricks to watch out for: for a box to fit inside its dimensions
had to be strictly less than the corresponding dimensions for the other box.
Otherwise the box edges would clash.
- Tricks to watch out for: judges wanted to separate cases by a
blank line. This means printing a blank line between cases, but making
sure there are no blank lines before the first case or after the last case.
Think about that!
- Make sure you number cases correctly, this can be a bit tricky to code