Match Editorial

Tonight's set was pretty standard, with lots of successful submissions and few challenges in both divisions. In an unusual turn of events, SRM 160 was not won by a member with a target, nor even by a red member. Instead, it was a yellow member, PMH, who had the highest score, unaided by any challenges. This win, the first by a yellow member in a long time, propelled PMH up 215 rating points, to 2066. Less than 50 points behind was the TCCC champion dgarthur. Rounding out the top 3 was bladerunner, only 8 points behind dgarthur.

In division 2, newcomer hagman was dominant, beating second place (and also a first time competitor) Jiggly by over 200 points. His impressive win gave hagman a debut rating of 1809, and making him a member to watch.

The Problems

Value	250
Submission Rate	141 / 146 (96.58%)
Success Rate	135 / 141 (95.74%)
High Score	Jiggly for 246.77 points (3 mins 15 secs)
Average Score	211.54 (for 135 correct submissions)

The simplest way to solve this problem was to look at each character in the code, starting from the first character, in order. As you go along, you keep an integer representing the value so far. If the character in the code is not in the key, you simply ignore it. Otherwise, you multiply the integer by 10, and add the number represented by the character. This is the standard way to parse numbers in any base: look at each character one at a time, multiplying by the base (10 in this case) and then adding each time.

Value	500
Submission Rate	81 / 146 (55.48%)
Success Rate	63 / 81 (77.78%)
High Score	hagman for 477.43 points (6 mins 14 secs)
Average Score	298.56 (for 63 correct submissions)

Computational geometry problems often trip people up, but this one wasn't too bad. There are a couple of ways to do this, and the simplest solution (in Java) makes use of the java.awt.Rectangle class. However, even without that class, the problem was quite doable. The first thing to do is initialize 4 integer to represent the rectangle that is in common to all of the rectangles in the input. We'll label these 4 integers lx, ly, hx, and hy, and initialize lx and ly to -1,000,000 and hx and hy to 1,000,000. This ensures that all of the rectangles in the input are smaller than the rectangle represented by lx, ly, hx, and hy. Now, we process each rectangle one at a time. First, we sort the x and y coordinates to find minx, miny, maxx, and maxy, for each rectangle. Next, we shrink the rectangle represented by lx, ly, hx, and hy to be only the area where it overlaps with rectangle represented by minx, miny, maxx, and maxy. To do this, we simply set lx = max(lx, minx), and hx = min(hx,maxx), and similarly for y. After we have done this for all rectangles, we need to check and see if lx, ly, hx, and hy represent a rectangle with positive area. If lx >= hx, or ly >= hy, then return 0. Otherwise, return (hx-lx)*(hy-ly).

Value	1000
Submission Rate	11 / 146 (7.53%)
Success Rate	6 / 11 (54.55%)
High Score	hagman for 644.05 points (24 mins 7 secs)
Average Score	516.43 (for 6 correct submissions)

Value	500
Submission Rate	71 / 125 (56.80%)
Success Rate	53 / 71 (74.65%)
High Score	LunaticFringe for 415.12 points (13 mins 25 secs)
Average Score	273.33 (for 53 correct submissions)

The tricky part about this problem was figuring out exactly how to spiral out. Once you had that down, the rest was pretty simple. First, you start with a big 2-D char array, say 200 x 200. Initialize them all to something that won't be in the return, like 0. Then, start with x and y at 100. Now, you'll want to have two arrays, lets call them dx, and dy, each with 4 elements, each of which represents how to move in each direction. For example, in java, you'd have:

   int[] dx = {0,-1,0,1};
   int[] dy = {-1,0,1,0};

   char quilt[200][200];
   int x = 100, y = 100, dir = 0, gone = 0, toGo = 1;
   for(int i = 0; i < length*width; i++){
      place a section of quilt at x,y.
      x = x + dx[dir];
      y = y + dy[dir];
      gone = gone + 1;
      if(gone == toGo){
         dir = (dir + 1)%4;
         if(dir==2 || dir == 0){
            toGo = toGo + 1;
         }
         gone = 0;
      }
   }

Value	250
Submission Rate	125 / 125 (100.00%)
Success Rate	113 / 125 (90.40%)
High Score	bsdude for 241.36 points (5 mins 24 secs)
Average Score	197.80 (for 113 correct submissions)

Clearly very few people had trouble with this problem, since over 90% of competitors submitted it correctly. This is pretty standard string parsing, and since the characters were always in the same positions, you could just parse substrings into integers, and with a little bit of simple math, you were done. Handling the 12 AM/PM bit was the only real caveot here, but that was clearly illustrated in the examples.

Value	1000
Submission Rate	16 / 125 (12.80%)
Success Rate	7 / 16 (43.75%)
High Score	PMH for 739.97 points (18 mins 14 secs)
Average Score	551.75 (for 7 correct submissions)

The key to this problem was to realize that everything about lexicographic strings was really more of a smoke screen than anything else. Finding the lexicographically first string is pretty simple, once you understand the structure of the cycles in the problem.

First, lets look at another way to find the cycle length of a string, other than actually going through and applying the permutation over and over again. Each letter is permutated to some other letter (or itself), and that other letter is permuted to yet another letter, and so on. Eventually, if you follow this chain of permutations, you'll get back to the letter you started at. So, we can see that there are going to be a number of independent cycles in the permutation. For example, the permutation "BADEC" has two cycles in it: A->B->A, and D->E->C->D. These two cycles have length 2 and 3, respectively. Therefore, every 2 times that we apply the permutation to the first cycle we get back where he started. Similarly, every three times we apply the permutation to the second cycle, we get back to where we started. Now, you should be familiar with the concept of a least common multiple (LCM). In this case, the least common multiple of 2 and 3 is 6, and 6 permutations is the first time that both cycles are back where they started (the one of length 2 has gone around 3 times, and the one of length 3 has gone around 2 times). So, the length of any permutation's cycle is the LCM of the lengths of all the smaller cycles that the permutation contains. This implies that we want to find a set of numbers whose LCM is maximized, and whose sum (remember that the sum of the lengths of the cycles will be the total number of characters) is less than or equal to the input, n. There are a few ways to do this. You can do some recursive search, adding in factors, or perhaps even brute force if you realize that the potential factors come from a relatively small set of possibilities. The way I did it was to try every possible LCM up to a certain large number. For each potential LCM, I took the prime factorization of that number, which gave me all of the factors that had to be cycle lengths. If the sum of the factors was sufficiently small, I considered it as a potential set of smaller cycle lengths for my permutation.

So, once you have the cycle lengths (factors), the question is how to get the lexicographically first string with those cycles. It turns out that the best way to do this is to have all of the smaller cycles first, and to make each cycle be the letters, in order, but shifted left 1. For example, if your cycle lengths where 2 and 3, the first string would be "BADEC". Its a little hard to explain, but if you play with it a little on paper, you should be able to convince yourself.

import java.util.*;
public class Permutation{
   String ch = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
   public String best(int n){
      int max = 1;
      for(int i = 1; i<200000 ; i++){
         if(sum(pf(i)) <= n)max = i;
      }
      int[] p = pf(max);
      int s = sum(p);
      Arrays.sort(p);
      String ret = "";
      for(int i = 0; i<n-s; i++){
         ret+=ch.charAt(0);
         ch = ch.substring(1);
      }
      for(int i = 0; i<p.length; i++){
         String st = ch.substring(0,p[i]);
         ch = ch.substring(p[i]);
         ret += st.substring(1)+st.charAt(0);
      }
      return ret;
   }
   /**
    * returns the prime factorization of n
    */
   int[] pf(int n){
      ArrayList al = new ArrayList(10);
      for(int i = 2; i*i<=n; i++){
         int push = 1;
         while(n%i==0){
            n/=i;
            push*=i;
         }
         if(push>1)
            al.add(new Integer(push));
      }
      if(n>1)al.add(new Integer(n));
      int[] ret = new int[al.size()];
   for(int i = 0; i<ret.length; i++)ret[i]=((Integer)al.get(i)).intValue();
      return ret;
   }
   int sum(int[] n){
      int ret = 0;
      for(int i = 0; i<n.length; i++)
         ret+=n[i];
      return ret;
   }
}