Practice Sessions – Week 4

Last night was the last practice session before the UVic undergraduate programming competition on Saturday. We had a decent turn out of 11 people and I heard from a few people that are coming to the competition but couldn’t make it last night. I’m guessing we’ll have about 15 people on the weekend.

I had the students do some old contest problems that Nathan Scott and I wrote back at UNB. There were five problems in total, both Dan and Scott solved three, a few solved two and everyone solved at least one. Dan got a fourth problem completed after the end of the practice.

The first three problems were pretty easy, but trickier than the easiest problems I’ve had the students do in the past. In the first, you have to simulate the process of determining who won a programming contest. This involved reading in people’s names, the time it took them to solve a given problem and how many submissions it took. Then you needed a little logic to calculate their total problems solved plus time taken.

We had some unforeseen issues with this problem. It turned out there was a mistake in the judge’s input where one case was larger than what was specified in the problem. This was causing a lot of people’s code to either crash or run forever. Unfortunately, we didn’t realize this until an hour or so of the student’s spinning their heels trying to debug something that wasn’t a bug.

The second problem was actually probably the easiest to code in the bunch. It had several scary math formulas in the description, which scared most people off. However, if you take the time to read the problem carefully, all you need to do is implement the last formula that is described. This involved reading in a bunch of numbers, multiplying them together, seeing which one was largest, and printing it out with 5 decimal places. Eventually, several of the students realized this and solved it quickly.

The third problem was a simulation problem. You had to read in a list of book inventory and then process orders on a first come first serve basis and print how much the store made through the sales or a line indicating that they could not fulfill the orders. Understanding what is required in this problem is reasonably straight-forward, but the problem requires some delicate string parsing to read in the book titles. Also, the inventory list has to be read into some kind of data structure and stored for look up during the ordering phase.

A simple way to do this is to create a Book struct or class that contains the name, current quantity and price of a given book then store these in a vector or perhaps a map.

struct Book {
 string title;
 int q, p;
 Book(string title, int q, int p) : title(title), q(q), p(p) {}
};

vector<Book> books;

The number of books is small, so all books can be stored in a vector and look-up can be an O(n) call. In my opinion, the solution to this problem is much easier to code in C++ or Java, as both have dynamic data structures built into the language like lists, vectors, maps, etc. Also, I think the input parsing is easier in those languages.

The next problem was about magic squares. A magic square is an arrangement of numbers from 1 to n^2 in an n*n matrix, with each number occurring exactly once, and such that the sum of the entries of any row, column, or main diagonal is the same. Here is an example of one:

Other magic squares exist for larger numbers, although the numbers are still consecutive within the square. In the problem, you have to attempt to complete a square given a partial configuration. For example:

There is more than one way to go about this problem. The completely bruteforce way is to realize that you can try all possible sequences of 9 consecutive numbers that fit within the given numbers in the square and all permutations of these. This is going to be proportional to 9! = 362,880, which will get under the time limit.

A less bruteforce approach is to observe that all larger magic squares can be computed based on the 1 to n^2 example. Consider the following magic square:

All values (i,j) in this square are equivalent to the original square cell values (i,j) + 11. This is true for all magic squares, they all can be derived from the first by adding some constant factor. Also, the original square has multiple configurations, which can be generated by rotations or flips of the original matrix.

Thus, to solve this problem, you can try all rotations and flips of the original matrix, check that the given values minus the original matrix values are equal, add this difference to all unknown cells and check if the matrix is a magic square. The easiest way to do the rotations and flips to compute all permutations of the array 1 through 9. We can easily do this in C++ in a few lines. The solution for magic squares would look something like the following.

Assume the unknown matrix is stored in an array of chars called matrix[]. Also, assume we have a function called isMagicSquare that will check whether a given array is a valid magic square configuration.

char matrix[];
int v[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
do {
 if(isMagicSquare(v)) {
   int diff = (matrix[0] - '0') - v[0];
   int i = 1;
   for(; i < 9; i++) {
     if(matrix[i] != 'X' && diff != (matrix[i] - '0') - v[i]) {
       break;
     }
   }

   if(i == 9) {
      printSolution(v, matrix);
      break;
   }
} while(next_permutation(v, v+9));

The last problem was called “Building teams”. Dan eventually solved this problem after the practice session was complete. After you decipher the problem, it boils down to graph coloring with at most four colors. Each clique of students is a node and a node is adjacent to another node if the clique’s dislike each other. You have to attempt to color the nodes such that adjacent nodes do not have the same color. Since graph coloring with more than two colors is NP-Complete, this should give you a hint that an inefficient backtracking algorithm should work. Even though there are at most 30 nodes, the colorings prune quite quickly as many of the 4^30 possibilities are equivalent.

Assume we have an array called nodeColors, which we will store all our colors in. Also assume we have a function called validColoring, which makes sure a given color assignment is valid, that is no adjacent nodes have the given color. Then we can color the nodes recursively doing something like the following.

// our node colors
int nodeColors[30];

// recursive function to assign colors, currentIndex is the current node
// maxColors is the max colors we are going to try
bool assignColors(int currentIndex, int maxColors) {
 if(currentIndex > N) return true;

 // try assigning all colors
 for(int i = 0; i < maxColors; i++) {
    // make sure this is a valid coloring for this node
    if(validColoring(currentIndex, i)) {
       nodeColors[currentIndex] = i;
       if(assignColors(currentIndex+1, maxColors)) {
          return true;
       }
       nodeColors[currentIndex] = -1;
    }
 }

 return false;
}

Next, call this function with maxColors equal to 1, 2, 3, and 4. The first one that returns true is the number of teams, if none return true, then you can’t build the teams.