Qualification Problem Set 1 February 2324, 2004 Summary 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 ProblemsDiamondLogoUsed as: Division One  Level One:
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...
public String[] logo(int size, char background) { String[] ret = new String[size*21]; for (int i = 0; i < size; i++) { char[] row = new char[size*21]; Arrays.fill(row, ' '); row[size1i] = 'X'; row[size1+i] = 'X'; for (int j = 0; j < size1i; j++) { row[j] = background; row[size*22j] = background; } ret[i] = new String(row); ret[size*22i] = new String(row); } return ret; }Surveyor Used as: Division One  Level Two:
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_{1},y_{2},...,y_{n}, with y_{1} <= y_{2} <= ... <= y_{n}. Now, since y_{1} is the bottom edge, we know that the region between y_{1} and y_{2} is in the polygon, while the region between y_{2} and y_{3} 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; } 
