Monday, May 23, 2005 Match summary In Division 1, the nottoohard but subtle problem set made the match quite exciting and unpredictable until the dust settled after the system test. Congratulations to misof for his victory with a wide margin, followed by Zis and Eryx. Partway through the match, Eryx made a stunning blitz of submitting all the problems in 25 minutes, but pitifully losing his lead by a resubmission of the 900point problem 25 minutes later. During the stirring challenge phase, the ranking list permutated frantically. Special mention goes to HardCoder in room 3 who raked in 300 points by 6 successful challenges on the ConnectFour problem. Division 2 was less eventful. Many coders finished the entire set well before the coding phase ended. The newcomer vlad89 took the first place, with abhiman and Seiz3r coming in a close second and third. The ProblemsGraderUsed as: Division Two  Level One:
The problem is fairly straightforward. First, we count the bias of each prediction in a single loop: vector<int> result(7); for(int i = 0; i < predictedGrades.size(); ++i) ++result[abs(predictedGrades[i]  actualGrades[i])];Then we convert the result into percentages and return it: for(int i = 0; i < 7; ++i) result[i] = result[i] * 100 / predictedGrades.size(); return result;PhonePad Used as: Division Two  Level Two:
Some coders hardcoded the distance matrix or the coordinates of keys for calculation, which is a doable approach. However, in a fastpaced SRM, it is usually better to save some typing by computing them at runtime: string pad = "123456789*0#"; int result = 0, x = 1, y = 1; for(int i = 0; i < phoneNumber.size(); ++i){ int index = pad.find(phoneNumber[i]); int row = index / 3; int col = index % 3; result += abs(x  col) + abs(y  row); y = row; x = col; } return result;CircleDance Used as: Division Two  Level Three: Used as: Division One  Level One:
It's quite obvious that trying out all the permutations of arrangement is infeasible. After playing around with small instances of this problem, you may soon discover the strategy that always gives the best result: first sort the array heights. Starting from any point on the circumference, line up all the dancers with odd indices of heights on one side, and the rest on the other side. For example: [5] [7] [3] [9] [1] [11] [0] [13] [2] [12] [4] [10] [6] [8] Why is this simple solution optimal for any number of dancers? Well, we may prove it using mathematical induction. Assume the array heights is already sorted in ascending order, and the greedy solution is optimal for the first k dancers with the minimum of maximum height difference f(k), and the kth and (k1)th dancers are adjacent. Now we add the (k+1)th dancer whose is taller than or as tall as any one among the first k previously considered. As this dancer must also have two neighbors in the circle, the lower bound of f(k+1) must be max(f(k), heights[k]heights[k2]), which can be achieved if we insert the (k+1)th between the kth and (k1)th. Notice that the tallest and second tallest dancers(i.e. the (k+1)th and kth) are still adjacent. So the solution holds optimal for (k+1) people. The simplest case with three dancers can be trivially proved, therefore the greedy solution is truly valid for any case with more dancers. Another compelling reason to convince yourself is that a SRM div 1 easy must be easy : ) Anyway, once you are convinced, the implementation can be really short: sort(heights.begin(), heights.end()); int result = 0; for(int i = 2; i < heights.size(); ++i) result = max(result, heights[i]  heights[i2]); return result;Polyline Used as: Division One  Level Two:
This problem is a bit tricky to figure out, but once you do, the coding is trivial. To figure out how to do it, imagine that you only had to hit one edge of the box, and then travel to the other point. It should be obvious that if we reflect the second point over that edge, it will be the same distance from whatever point on the edge we travel to first. Now, we all know that the shortest path between two points is a straight line, so it is best to draw a straight line from the starting point to the reflected point, and wherever that hits, that is where you should travel to on the edge. Now, since there are four edges, we just have to reflect the end point over all of them. For each parallel pair of edges, there are two ways to reflect the point (we can pick either edge for the first reflection). This gives us four possible positions for the final 4time reflected point. We simply pick the shortest one, and that's it. If you work it out on paper a bit, you'll see that reflecting twice either adds or subtracts twice the distance between the parallel edges, giving us the following solution: double ret = Double.POSITIVE_INFINITY; for (int i = 2; i <= 2; i+=4) for (int j = 2; j <= 2; j+=4) ret = Math.min(ret,dist(x0,y0,x1+i*a,y1+j*b)); return ret;ConnectFour Used as: Division One  Level Three:
The hard part of this problem is in determining if a game is valid or not. If
we know its valid, its easy to figure out which of the other return values is
correct. A lot of people tried to figure out if the game was valid by using
heuristics, but this is dangerous at best, and you are very likely to get it
wrong by doing this. boolean recurse(int[] columns, int turn){ if(cache.contains(columns))return false; if(columns is end board)return true; if(columns contains connect four)return false; cache.add(columns); for(int i = 0; i<7; i++){ if(columns[i]!=6 && board[i][5columns[i]] == marker(turn)){ columns[i]++; if(recurse(columns,1turn))return true; columns[i]; } } return false; }Since each column can have between 0 and 6 pieces in it, and there are 7 columns, the state space is 7^{7} = 823543. This is small enough that it can be fully explored without much trouble.
By logged 
