First Annual UVic Programming Competition

The First Annual UVic Programming Contest took place last Saturday, January 31st, 2009. The contest went extremely smooth. We didn’t have any problems with the PC^2 software and only a few minor issues with the problem set, but everything was caught right away. There were 12 competitors in all. You can check out the problem set, scoreboard, solutions, and judge’s inputs/outputs here.

There was some pretty exciting back and forth action between the top three competitors. Both Dan Sanders and Scott Porter jumped out to an early lead by solving the first problem at the 8 minute mark. Dan solved a second problem 12 minutes later and had the lead through the first three problems. John Hawthorn took the lead at 51 minutes by solving his fourth problem.

At this point, we were really worried that the top three competitors would solve all the problems in half the time meaning that we made the problem set too easy. We knew that the top competitors would probably solve the first three in the first hour, but they were going even faster than we anticipated.

Scott jumped into second place ahead of Dan by solving a 4th problem at the 86 minute mark, but Dan jumped back in front of Scott 15 minutes later by solving one of the hardest problems in the set. John beat everyone to a 5th problem by getting an accepted solution on the Gem Collector on his 4th attempt. Dan and Scott caught up, but with around 2 hours left in the competition John solved his 6th problem on his 8th attempt.

Dan caught up with over an hour left, but he needed to fix his Gem Collect problem in order to retake the lead. With approximately 50 minutes left, John submitted an attempt at G. I promptly took the scoreboard down for suspense and then went and judged his problem. He got a wrong answer, but 10 minutes later, he submitted again and had it accepted.

Both Dan and Scott attempted to get a 7th problem, but neither managed to get their solutions accepted. Everyone did extremely well. Only one person solved all the problems and everyone solved at least one. Most the competitors were in first year, so that’s a fantastic result.

Below is a brief description of how to solve each problem.

A. [**SPAM**] Congratulations, You’ve Won!!!
Once you read the story, the problem boils down to finding the largest prime number less than or equal to some value N. The maximum value of N is small enough that just about any solution would be acceptable. One simple way to solve the problem is read in N and then test primality for all values less than or equal to N. Something like the following.

int i;
for(i = N; i >= 2; i--) {
  if(isPrime(i)) break;
}

print(i);

bool isPrime(int t) {
  for(int i = 2; i*i <= t; i++) {
     if(!(t % 2)) return false;
  }
  return true;
}

B. The Love Guru
The Love Guru was of similar complexity to the first problem. All that was required was to read in two strings, count the number of shared letters between the two strings (case-insensitive) and divide that by the total number of unique letters. If that value was greater than or equal to 0.4, then print “Get hitched”, otherwise print “Part ways”.

string getRecommendation(string n1, string n2) {
    // use a vector to check if we've seen a letter before
    vector<int> u(26, 0);
    int shared = 0, total = 0;
    // total up unique letters in first name
    for(int i = 0; i < s1.length(); i++) {
      if(!u[s1[i]-'a']) total++;
      u[s1[i]-'a'] = 1;
    }
   
    // total up shared and unique letters from second name
    for(int i = 0; i < s2.length(); i++) {
      if(u[s2[i]-'a'] == 1) { shared++; }
      else if(!u[s2[i]-'a']) total++;
      u[s2[i]-'a'] = 2;
    }

    // compute percent with truncation
    int perc = (int)((double)shared/(double)total*100.0);

    return ((perc >= 40) ? "Get hitched" : "Part ways");
}

C. You Sunk My Battleship
This was the third easy problem in the set, which we expected most people to attempt or solve. The problem was originally a bit trickier, where there were more ships on the board of varying sizes, but we decided to make the parsing easier. You had to read the description carefully and implement a single player game simulation for Battleship.

The main problem people had was not realizing that a hit to the same location more than once should print “Hit” multiple times but not necessarily sink the ship. You have to hit the battleship in all four locations at least once to sink the ship.

D. Great Ocean Views!
This was the first problem in the set that required a bit more insight to easily solve. Everyone that solved this problem got it accepted on the first try, so provided you were lucky enough to see how to approach the problem, the algorithm was easy to implement. The first key is to realize you can ignore the Z dimension. The second key is that since everything is a rectangle defined in integer space and the size is a maximum 50×50, you can define a matrix to store the window locations of all buildings. You “paint” the building rectangle onto this matrix and afterwards sum up all the overlapping windows. Something like the following.

int matrix[51][51];
// initialize all values to -1
memset(matrix, -1, sizeof(int)*51*51);

int x, w, h, z;
// read in and process each building
for(int i = 0; i < N; i++) {
  cin >> x >> w >> h >> z;
  // paint the building onto the matrix
  for(int j = x; j < x + w; j++) 
     for(int k = 0; k < h; k++) matrix[j][k]++;
}

// sum the windows blocked
int windowsBlocked = 0;
for(int i = 0; i < 51; i++) {
  for(int j = 0; j <51; j++) 
     windowsBlocked += matrix[i][j];
}

print(windowsBlocked);

E. Gem Collector
This problem describes a game in which you collect gems from a matrix. The gems have different values, and you want to determine what is the maximum value of gems that you can collect given that you can start in any location and collect from any cell adjacent to a cell where you collected a gem previously.

Several people had problems with getting an accepted solution. A lot of solutions didn’t run under the time limit or gave run time errors. Also, some people seemed to misinterpret what was required to solve the problem. The gem matrix is a maximum 25×25, so it’s possibly to try all starting locations and recursively collect gems, keeping track of the maximum value you can collect. See my solution for more details.

F. Vegas Baby!
Only the top three people solved this problem. The solution requires dynamic programming. It’s a pretty standard dynamic programming problem, so if you were familiar with the concept, it was likely you would solve it. There was some ambiguity with the problem that caused people to get wrong answers. They weren’t sure which value for the number of people to return if there were multiple solutions that cost the same. We wanted the number of people to be as close to K as possible.

To solve the problem, you can make an array or vector where each index represents how many people you can bring, and in each entry you store the minimum cost to bring that many people. To fill this array, you can process each university and for each existing entry in the array, combine that entry with the current university you are processing. Also, update all index values that are a multiple of the number of people from the current university.

The solution is something like the following, where we have a vector called makes initialized with INT_MIN, and the people and cost for a university are stored in arrays p and c.

// loop through our participants
for(int i = 0; i < N; i++) {
    // loop through our current combinations
    for(int j = 0; j < makes.size(); j++) {
        // check if we have a combination for j, 
        // if so, use it to figure out j + p[i]        if(j + p[i] < makes.size() && makes[j] != INT_MAX) {
           makes[j+p[i]] = min(makes[j+p[i]], makes[j] + c[i]);
        }  // j is divisble by p[i], so we can make j
        else if(!(j % p[i])) { 
           makes[j] = min(makes[j], c[i] * j/p[i]);
        }
    }
}

G. Help Sean
The last problem, once deciphered, works out to be a pretty standard graph problem. Each city can be considered as a node in a graph, edges exist between cities provided the distance between the two cities is less than or equal to the distance you can travel with the car’s gas tank. Then you need to calculate the shortest path between the start city (i.e. Victoria) and the end city (i.e. St. Stephen). This can be done using Dijkstra’s algorithm or All-pairs Shortest Path or the Bellman Ford Algorithm.

There was also a bit of string parsing to read in the city names and you had to properly implement the given formulas for calculating the distance between latitude and longitude coordinates taking into account the spherical nature of the Earth.