JOIN
 Match Editorial
2004 TopCoder Collegiate Challenge
Qualification Problem Set 1

February 23-24, 2004

Summary

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

# The Problems

DiamondLogo
Used as: Division One - Level One:
 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;
}
```

Surveyor
Used as: Division One - Level Two:
 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 y1,y2,...,yn, with y1 <= y2 <= ... <= yn. Now, since y1 is the bottom edge, we know that the region between y1 and y2 is in the polygon, while the region between y2 and y3 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;
}
```

By lbackstrom
TopCoder Member