Match Editorial

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

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)){
      if(i-next+1<=maxAdd)return i-next+1;
   }
   return -1;

   int ret = (goal-next+1)%(maxAdd+1);
   return ret==0?-1:ret;

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);
      }
   }

   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;
         }
      }
   }

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++){
            double rad = 0;
            for(int k = 0; k<x.length; k++){
               double dx = x[k]-i, dy = y[k]-j;;
               rad = max(rad,sqrt(dx*dx+dy*dy));
            }
            ret = min(ret,rad);
         }
      }
      return ret;

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];

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};
   }

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])
      pos3.word = adjustEndCharacters(word[1],pos3.word,word[N])
      return bestOf(pos1,pos2,pos3)
   }

   if(cache.containsKey(word,emptyOK))return cache.get(word,emptyOK);

   ret = bestOf(pos1,pos2,pos3)
   cache.put((word,emptyOK),ret)
   return ret