JOIN
 Match Editorial
SRM 183
Wednesday, February 11, 2004

Match summary

Division 1 had a pretty hard set last night, with a slightly harder easy problem, and a tricky medium geometry problem that stumped most coders. Only 24 of them where able to successfully pass the medium, though many tried. The hard involved dynamic programming/memoization, and though it had a higher success rate, many fewer people submitted it. mathijs had the highest score from the coding phase, and 2 successful challenges secured a win for him. SnapDragon and John Dethridge were not far behind in second and third, respectively. In division 2, coders had a much easier time and boets narrowly edged out gigz and xmux for the win.

# The Problems

CountGame
Used as: Division Two - Level One:
 Value 350 Submission Rate 163 / 235 (69.36%) Success Rate 104 / 163 (63.80%) High Score Bilroy for 339.81 points (4 mins 56 secs) Average Score 249.61 (for 104 correct submissions)

You were asked to find an ideal strategy for a counting game, where two players take turns counting off up to maxAdd numbers. The first person to hit a certain goal number wins. Luckily, the winning strategy was outlined in the problem statement and all we had to do was implement it. No matter how many numbers our opponent counts off, we can always count off enough so that maxAdd+1 numbers were counted off. Thus, if we can end on goal-(maxAdd+1), then we can force a win. In fact, by induction, if we can end on goal-n*(maxAdd+1), for some n, we can force a win. Since the goal is relatively small, we could simply start counting backwards maxAdd+1 at a time:

```   for(int i = goal; i>=next; i-=(maxAdd+1)){
}
return -1;
```
Alternatively, we could use a bit of modular arithmetic to come up with the following:
```   int ret = (goal-next+1)%(maxAdd+1);
return ret==0?-1:ret;
```

BridgeSort
Used as: Division Two - Level Two:
 Value 550 Submission Rate 153 / 235 (65.11%) Success Rate 118 / 153 (77.12%) High Score boets for 512.33 points (7 mins 49 secs) Average Score 352.97 (for 118 correct submissions)

Sorting problems are pretty common, and everyone has there own favorite way of doing them. One way or another, you need two things: a way to compare two elements, and a sorting algorithm. Usually, when I solve these problems, I end up writing a slow, but simple bubble sort, which always looks more or less like this:

```   for(int i = 0; i<n; i++){
for(int j = 0; j<i; j++){
if(element[i] < element[j])
swap(i,j);
}
}
```
To compare then, we first compare the suit, and if that is not equal, we know right away which one comes earlier. If the suits are the same, then we have to compare the values. Rather than actually break the cards up in to their own array, and then sort that, and then put them back into a string, I did the whole thing in a single char array, comparing pairs of character, which I think ends up making your code a little shorter. Note that using the indexOf method in a String is a good, robust way of imposing an order on characters, be they cards, or hex digits, or whatever.
```   String cards = "CDHS23456789TJQKA";
for(int i=0; i<hand.length; i+=2){
for(int j = 0; j<i; j+=2){
if(suits.indexOf(hand[i]) < suits.indexOf(hand[j]) ||
suits.indexOf(hand[i]) == suits.indexOf(hand[j]) &&
suits.indexOf(hand[i+1]) < suits.indexOf(hand[j+1])){
char c = hand[i];
hand[i] = hand[j];
hand[j] = c;
c = hand[i+1];
hand[i+1] = hand[j+1];
hand[j+1] = c;
}
}
}
```

TVAntenna
Used as: Division Two - Level Three:
 Value 750 Submission Rate 98 / 235 (41.70%) Success Rate 55 / 98 (56.12%) High Score boets for 711.58 points (6 mins 40 secs) Average Score 573.54 (for 55 correct submissions)

This is a substantially easier version of the division 1 medium, where we only allow towers at integral coordinates, and there are only 160,801 such integral coordinates to consider. Basically, we can just iterate over all pairs of coordinates, and for each pair calculate the distance to each town using the pythagorean formula. The radius required for a tower at a given location is the maximum distance from that location to a town. Once we've calculated the radii from each location, we just return the minimum:

```      double ret = 100000;
for(int i = -200; i<=200; i++){
for(int j = -200; j<=200; j++){
for(int k = 0; k<x.length; k++){
double dx = x[k]-i, dy = y[k]-j;;
}
}
}
return ret;
```

TennisSet
Used as: Division One - Level One:
 Value 250 Submission Rate 185 / 186 (99.46%) Success Rate 144 / 185 (77.84%) High Score antimatter for 245.60 points (3 mins 48 secs) Average Score 205.34 (for 144 correct submissions)

To solve this, the first thing we need is a variable that tells us who is serving, turn, and a way to keep score. I think that the best way to keep score is to have both the score in the curent game, and the score in the set in two-element arrays, game and set. Then, the turn flips between 0 and 1, and is really an index into the game and set variables. With this initialization, we start iterating over all the points scored. If we see an 'S', we note that winner = turn, and other wise it is 1-turn. Then, we simply increment game[winner] and check to see if that point ended the current game. The current game has ended if game[winner] >= 4 and game[winner]-game[1-winner] >=2. If the game is over, we reset the game score, increment set[winner], and check to see if the set has just been won:

```   int set[] = new int[2], game[] = new int[2], turn = 0;
for(int i = 0; i<points.length; i++){
for(int j = 0; j<points[i].length(); j++){
int winner = points[i].charAt(j)=='S'?turn:1-turn;
game[winner]++;
if(game[winner] - game[1-winner] >= 2 && game[winner] >= 4){
game = new int[2];
set[winner]++;
if(set[winner] - set[1-winner] >= 2 && set[winner] >= 6)return set[0]+"-"+set[1];
turn = 1-turn;
}

}
}
return set[0]+"-"+set[1];
```

TVTower
Used as: Division One - Level Two:
 Value 675 Submission Rate 98 / 186 (52.69%) Success Rate 24 / 98 (24.49%) High Score Ruberik for 643.58 points (6 mins 20 secs) Average Score 435.11 (for 24 correct submissions)

Geometry problems are always a bit daunting, but if you know the right tricks, they are usually fairly simple. In this problem, the trick was to find the center of a circle that is defined by three points that are on it. To see how this helps, consider some circle enclosing all of the towns in the input. Unless there are two points directly opposite each other on the circle, or three points actually on the circle, then we can shrink the circle a little bit, and still enclose everything. Thus, we want to consider all circles that either have two points directly opposite each other (these ones are easy) and all circles that have three points on their edge. Now, to find the center of a circle, given three points, we first draw a line between each pair of points. Now, take the perpendicular bisector of that line, and you'll see that is passes through the center of the circle. Thus, to find the center, we simply need to intersect the perpendicular bisectors. The easiest way to do this is to consider lines to be defined by A, B and C, where Ax+By=C. This formula doesn't require any special cases for vertical lines (as the y=mx+b form does) and typically makes things easier. So, the first step is to find formulas for two of the perpendicular bisectors. If we were finding the formula for the line between two points (x1,y1) and (x2,y2), we would take A=y2-y1, B=x1-x2 and C=Ax1+By1. One can easily verify by substitution that the resulting A, B and C also gives C=Ax2+By2. So, we can find the line between two points, but we want the line that is perpendicular to that. Let's call the A and B values for the line between the two points A' and B'. Then all lines perpendicular to it can be defined by formulas of the above form using A=B' and B=-A'. In other words, our perpendicular bisector will have A=x2-x1 and B=y2-y1. To find C, we simply substitue the one (x,y) pair that we know lies along the line into the formula, the point halfway between (x1,y1) and (x2,y2): C=A(x1+x2)/2+B(y1+y2)/2. Now, once we two sets of (A,B,C) triples for two of the perpendicular bisectors, we have too intersect them. This can be done in a number of ways, the simplest of which involves a bit of linear algebra. I won't go into the details, but basically you are just solving two simulaneous equations with two unknowns. There will be some cases when there is no solution, in which case the perpendicular bisectors are parrallel and we can just ignore these cases. The code below shows one way to do the last step, finding the values of x and y from the (A,B,C) triples. Note that d==0 indictes there is no solution.

```   double[] center(int x1, int y1, int x2, int y2, int x3, int y3){
double A1 = x1-x2;
double A2 = x2-x3;
double B1 = y1-y2;
double B2 = y2-y3;
double C1 = (A1*(x1+x2) + B1*(y1+y2))/2;
double C2 = (A2*(x2+x3) + B2*(y2+y3))/2;
double d = A1*B2-A2*B1;
if(d==0)return new double[]{0,0};
double y = (A1*C2-A2*C1)/d;
double x = -(B1*C2-B2*C1)/d;
return new double[]{x,y};
}
```

Ambigram
Used as: Division One - Level Three:
 Value 900 Submission Rate 23 / 186 (12.37%) Success Rate 11 / 23 (47.83%) High Score po for 500.40 points (31 mins 14 secs) Average Score 445.87 (for 11 correct submissions)

Dynamic programming or memoization, take your pick. Either way, to solve this problem you reuse your computations in order to make your code run fast enough. I'll go into the memoization solution, since I think its a bit easier to understand. The first step to writing any memoized solution is to write a recursive function that solves the problem, ignoring runtime speed issues. In this case, our recursive function has two parameters: a word to turn into an ambigram, and a boolean that tells us if we need to return an ambigram with at least one letter, of if the empty string will do when that is cheapest. Our base case is when the length of the word to be made into an ambigram is 0 or 1. If it is 0, then we return "", with a cost of 0. If it is 1, then we check to see if its ok to return the empty string. If it is, then we return either the empty string, or a one character ambigram, whichever is cheaper. If it is not ok to return the empty string, then we just return the cheapest one character ambigram. Now, the recursive step is to either remove a character from the left, remove a character from the right, or else make the left and right most characters so that rotating one yields the other. I'd recommend writing a separate method for the last part, to determine which pair of letters is cheapest. So, we recursively call our method, trimming the left, right, or both characters from the current word. Each recursive call returns a word, and a cost to us, and we do a few elementary calculations to determine which of the three resulting words to use, by comparing cost, length, and finally lexicographically. The one things to note about the recursive call is that if we remove a letter, the status of the empty string boolean remains unchanged, but if we make two letters look the same after rotation, then it becomes ok for the recursive call to return the empty string, since we already have 2 characters. So, lets put this all into pseudocode, assuming that we have methods to find the cheapest pair of letters, and to determine which of two strings are best:

```   (string,int) recurse (string word, boolean emptyOK){
int N = word.length();
if(N==0)return ("",0);
if(N==1){
find best (word,cost) pair where word has a single character
if(emptyOK{
consider returning ("",cost)
}
return best (word,cost) pair found
}
pos1 = recurse(word[2..N],emptyOK)
pos1.cost += costToRemove(word[1])
pos2 = recurse(word[1..N-1],emptyOK)
pos2.cost += costToRemove(word[N])
pos3 = recurse(word[2..N-1],true)
pos3.cost += costToMakeRotations(word[1],word[N])
return bestOf(pos1,pos2,pos3)
}
```
Thats pretty much it. The last thing we have to do is get it to run fast enough, which requires us to add memoization, and cache results. There are different ways to do this, but each way involves a key, based on the parameters to the function, and a cached result that is matched to that key. In this case, we would add something like this to the beginning of the function:
```   if(cache.containsKey(word,emptyOK))return cache.get(word,emptyOK);
```
And we would make this change at the end:
```   ret = bestOf(pos1,pos2,pos3)
cache.put((word,emptyOK),ret)
return ret
```
As you can see, the memoization part of it is really quite trivial, and the hardest part is writing the recursive function, not making it fast enough.

By lbackstrom
TopCoder Member