Match Editorial

Last year's Collegiate Challenge winner, dgarthur was assigned to this room, but only got 5^th, 35 points behind winner Eryx. antimatter and WishingBone took 2^nd and 3^rd, respectively, and were separated by less than 2 points. Fleur, in 8^th place, was the most notable new comer, less than 50 points behind the top spot.

The Problems

Value	300
Submission Rate	110 / 132 (83.33%)
Success Rate	93 / 110 (84.55%)
High Score	WishingBone for 287.38 points (4 mins 48 secs)
Average Score	204.93 (for 93 correct submissions)

While this problem was a little bit more involved than some of the other Qualification Round easy problems, passing the example cases all but guaranteed a correct solution (I looked at a few failed solutions, and didn't find one that passed the examples). I think that a big part of many of the failures was that it was a bit tricky to compare your solution to the reference because there were so many repeated characters. If you aren't using an automatic validator (check out the plugins link from the home page), you should really copy and paste both answers to make sure everything lines up. Anyhow, to the solution...

First off, the return is square with size*2-1 rows and columns. So, if we loop over the rows, our outer loop should go from 0 to size*2-2. In each row, we first add some background characters, then an 'X', some spaces, another 'X' and some more background characters. The meat of the problem is figuring out how many spaces and how many backgroud characters to add. In my solution, I dispensed with the bottom half of the image by using the symmetry to copy the top half. This makes it a little bit easier to figure out how many spaces and background characters to use, since you would otherwise have to deal with two different cases. So, for row i, with i <= size, there are max(0,i*2-1) spaces. There are also size-i-1 background characters on each side of the diamond. Both of these equations can be easily derived simply by looking at the examples, and if you can come up with equations that work for the examples, you can be pretty confident (for this problem) that your equations are generally correct.

    public String[] logo(int size, char background)
    {
        String[] ret = new String[size*2-1];
        for (int i = 0; i < size; i++) {
            char[] row = new char[size*2-1];
            Arrays.fill(row, ' ');
            row[size-1-i] = 'X';
            row[size-1+i] = 'X';
            for (int j = 0; j < size-1-i; j++) {
                row[j] = background;
                row[size*2-2-j] = background;
            }
            ret[i] = new String(row);
            ret[size*2-2-i] = new String(row);
        }
        return ret;
    }

Value	550
Submission Rate	57 / 132 (43.18%)
Success Rate	46 / 57 (80.70%)
High Score	Eryx for 537.01 points (3 mins 33 secs)
Average Score	433.27 (for 46 correct submissions)

This problem can be solved by using the polygon area algorithm that has been described in previous writeups. You can read about this on MathWorld. But here you didn't need to know this general formula to find the area, as all the angles were 90 or 270 degrees. Since there are at most 50 edges, there are at most 50 distinct x coordinates. Similarly, there at most 50 distinct y coordinates. So, we can use coordinate compression to solve this problem. We look at each interval, between two adjacent x coordinates, then we go through and look at all of the horizontal edges that span the current interval. If we sort these horizontal lines by y coordinate, we get a series y₁,y₂,...,y_n, with y₁ <= y₂ <= ... <= y_n. Now, since y₁ is the bottom edge, we know that the region between y₁ and y₂ is in the polygon, while the region between y₂ and y₃ is not and so on. Hence, we can find all the regions within the interval that are in the polygon and add them up.

    public int area(String direction, int[] length){
    int[] x = new int[length.length];
    int[] y = new int[length.length];
    String dirs = "SENW";
    int[] dx = {0,1,0,-1};
    int[] dy = {1,0,-1,0};
    int xx = 0, yy = 0;
    for(int i = 0; i<length.length; i++){
        x[i] = xx;
        y[i] = yy;
        xx += length[i]*dx[dirs.indexOf(direction.charAt(i))];
        yy += length[i]*dy[dirs.indexOf(direction.charAt(i))];
    }
    int[] xs = (int[])x.clone();
    Arrays.sort(xs);
    int[] ys = new int[x.length];
    int ptr;
    int ret = 0;
    for(int i = 0; i+1<xs.length; i++){
        if(xs[i]==xs[i+1])continue;
        ptr = 0;
        for(int j = 0; j<y.length; j++){
            if(x[j] <= xs[i] && x[(j+1)%x.length] >= xs[i+1] || 
               x[(j+1)%x.length] <= xs[i] && x[j] >= xs[i+1]){
                ys[ptr++] = y[j];
            }
        }
        Arrays.sort(ys,0,ptr);
        for(int j = 0; j<ptr; j+=2){
            ret += (xs[i+1]-xs[i])*(ys[j+1]-ys[j]);
        }
    }
    return ret;
}