Match Editorial

With the TopCoder Open only a few weeks off, familiar faces are beginning to resurface in order to regain their competition form. snewman, who only started competing again recently, doesn't seem to need much practice. He placed second in a relatively tight race. kalinov, the eventual winner, earned 300 points during one of the most vicious challenge phases in recent history. 38 competitors submitted the Div 1 Hard, but only 12 were correct. In Division 2, newcomers rem and martinp534 came out on top, besting all of the Div 2 veterans. We wish them good luck in Division 1.

The Problems

Value	250
Submission Rate	174 / 199 (87.44%)
Success Rate	169 / 174 (97.13%)
High Score	ahri for 249.59 points (1 mins 9 secs)
Average Score	213.30 (for 169 correct submissions)

In this problem we must count how many times the characters in a given string occur in a collection of strings. To accomplish this, we loop over each character of the collection and test for membership in the given string. Java code follows:

int count(String dithered, String[] screen) {
   int n = 0;
   for(int i = 0; i < screen.length; i++)
   for(int j = 0; j < screen[i].length(); j++)
      if(dithered.indexOf(screen[i].charAt(j)) != -1)  n++;
   return n;
}

Value	600
Submission Rate	115 / 199 (57.79%)
Success Rate	94 / 115 (81.74%)
High Score	rem for 562.90 points (7 mins 23 secs)
Average Score	373.56 (for 94 correct submissions)

The concepts outlined in this problem play a key role in the Miller-Rabin algorithm used in algorithmic number theory and cryptography. The major difficulty here was figuring out how to exponentiate in a timely fashion. More precisely, we need a function

 int ModularExponentiation(int base, int exponent, int mod) 

int ModularExponentiationSlow(int base, int exponent, int mod) {
   int ret = 1;
   for (int i = 0; i < exponent; i++) 
      ret = (ret * base) % mod;
   return ret;
}

int ModularExponentiation(int base, int exponent, int mod) {
   if (exponent == 0) return 1;
   if (exponent % 2 == 0) { //exponent is even
      int temp = ModularExponentiation(base,exponent/2,mod);
   return (temp * temp) % mod;
   } else { //exponent is odd
   return (base * ModularExponentiation(base,exponent-1,mod)) % mod;
   }
}

int ModularExponentiationIter(int base, int exponent, int mod) {
   int ret = 1;
   for ( ; exponent > 0 ; exponent /= 2) {
   if (exponent % 2 == 1) ret = (ret * base) % mod;
   base = (base * base) % mod;
   }
   return ret;
}

Value	1000
Submission Rate	12 / 199 (6.03%)
Success Rate	9 / 12 (75.00%)
High Score	bwpow for 560.74 points (30 mins 47 secs)
Average Score	482.42 (for 9 correct submissions)

Value	500
Submission Rate	105 / 177 (59.32%)
Success Rate	96 / 105 (91.43%)
High Score	venco for 392.20 points (15 mins 49 secs)
Average Score	246.77 (for 96 correct submissions)

This problem consisted of transforming the stated algorithm into runnable code. After reading the statement, certain things still needed to be figured out: how to compute the number of queens that could reach each other and select one for movement; how to compute the number of queens that could reach each spot in a column and select one spot for movement; and how to determine if the process is done. The first and last of these are closely tied since the process is done when 0 queens can reach one another. To solve these problems, I used an n x n array of integers that stored how many queens could reach each position. In addition, I store a separate n-element array of integers, storing where each queen was located. I had a helper function that modified these structures, as needed by the algorithm.

Value	250
Submission Rate	176 / 177 (99.44%)
Success Rate	167 / 176 (94.89%)
High Score	ZorbaTHut for 246.83 points (3 mins 13 secs)
Average Score	216.47 (for 167 correct submissions)

The two most popular solutions involved sorting or simply looping. Using the sorting method, we take the given array and its transpose and sort each row. We build new lists using these row-sorted arrays, and then sort the new lists to find the solution. In the looping method we never sort, but always loop through to find minima or maxima.

Value	1000
Submission Rate	38 / 177 (21.47%)
Success Rate	12 / 38 (31.58%)
High Score	snewman for 791.53 points (15 mins 27 secs)
Average Score	608.21 (for 12 correct submissions)

In nearly all applicable problems, I favor memoization over dynamic programming since I find it easier to code. Here I decided to try dynamic programming, but memoization would have worked too. I broke the problem into 2 cases, in order to make the coding simpler. The first case occurs when there are only 2 rows, in which case every spot is reachable, and we simply return a sum taken over the entire input (this could be done in the 3 row case as well).

The second case is the bulk of the code. The first important thing to realize is that we can assume all paths begin in the upper left and finish in the lower right corner of the map. This way our solution will model 3 paths leaving the upper left corner. Next we can assume, without loss of generality, that the 3 paths will proceed horizontally along different rows, never crossing. In other words, the 3 paths will only ever meet in the leftmost column and the rightmost column. During the majority of the trip, one path will always be on top, another path on the bottom, and a final path strictly in between. Focusing on such a setup allows us to considerably optimize our algorithm.

The dp algorithm outlined here proceeds rightward across the board, considering one column at a time. The leftmost column is setup with values based on how low the lowest path begins. During each iteration of the algorithm we proceed rightward one column, assuming each path moves rightward one step. Upon arriving at a column, the paths can move downward as they please, but will never cross. We are done when we reach the rightmost column.

In order to guarantee we do not cross paths during the algorithm, me must handle each column carefully. To accomplish this, first handle all possible cases where you can move the highest path downward without crossing the middle path. Secondly, once the top path is done, do the same for the middle path. Finally move the lowest path. To see code that implements this algorithm, look at my solution in the practice room.