2008 UM-D Programming Contest - Notes and Hints

Problem A

• 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 think up.
• 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, int minpath) {     if (out of bounds, hit a wall, or path is longer than the shortest one found so far)         return 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;     findShortestPath(row,col+1,path+1,minpath);//go right;     findShortestPath(row+1,col,path+1,minpath);//go down;     findShortestPath(row,col-1,path+1,minpath);//go left;     findShortestPath(row-1,col,path+1,minpath);//go up;     return minpath; }

Problem B

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(n²) - 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(n²) solutions.

Problem C

• 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:
  
  

  #include <iomanip> using namespace std; cout<<fixed<<setprecision(2)<<answer<<endl;

  
  
• 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".
  
  

  #include <cmath> double round(double x) {     return floor(100*x+0.5)/100; }

  
  
• 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.

Problem D

• 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.
  
  

  char chr='B'; chr+=32; cout<<chr;//'b'

Problem E

• 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 at first.