JOIN
 Match Editorial
SRM 208
Wednesday, August 18, 2004

Match summary

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

ImageDithering
Used as: Division Two - Level One:
 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;
}
```

PseudoPrimeTest
Used as: Division Two - Level Two:
 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) `
that computes baseexponent % mod. The following code does this inefficiently:
```int ModularExponentiationSlow(int base, int exponent, int mod) {
int ret = 1;
for (int i = 0; i < exponent; i++)
ret = (ret * base) % mod;
return ret;
}
```
Notice how we use % mod after each multiplication to keep the size of the values manageable. Even though the code above is correct, the number of iterations of the loop is linear in the value of exponent. Taking advantage of repeated squaring, we can get the following optimized version:
```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;
}
}
```
The recursive code given above checks to see if the exponent is even. If so, we can halve the exponent, and square the result. This check dramatically increases the speed of our function, achieving asymptotic performance logarithmic in the value of the exponent (considering mults,divs, and mods as constant time operations). As a short exercise, you can check to see why the following iterative code correctly computes the same function:
```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;
}
```

QueenInterference
Used as: Division Two - Level Three:
 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)
Used as: Division One - Level Two:
 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.

TallPeople
Used as: Division One - Level One:
 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.

Used as: Division One - Level Three:
 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.

By brett1479
TopCoder Member