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 ProblemsImageDitheringUsed as: Division Two  Level One:
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:
The concepts outlined in this problem play a key role in the MillerRabin 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 base^{exponent} % 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,exponent1,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: Used as: Division One  Level Two:
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 nelement array of integers, storing where each queen was located. I had a helper function that modified these structures, as needed by the algorithm. TallPeopleUsed as: Division One  Level One:
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 rowsorted 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. StarAdventureUsed as: Division One  Level Three:
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). 
