Match Editorial

In Division 1, the not-too-hard 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 900-point 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 Problems

Value	250
Submission Rate	212 / 235 (90.21%)
Success Rate	197 / 212 (92.92%)
High Score	Fabi for 248.95 points (1 mins 50 secs)
Average Score	205.49 (for 197 correct submissions)

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])]; 

   for(int i = 0; i < 7; ++i)
      result[i] = result[i] * 100 / predictedGrades.size();
   return result;

Value	400
Submission Rate	196 / 235 (83.40%)
Success Rate	175 / 196 (89.29%)
High Score	teminator for 389.33 points (4 mins 43 secs)
Average Score	277.51 (for 175 correct submissions)

Some coders hard-coded the distance matrix or the coordinates of keys for calculation, which is a doable approach. However, in a fast-paced SRM, it is usually better to save some typing by computing them at run-time:

   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;

Value	900
Submission Rate	82 / 235 (34.89%)
Success Rate	59 / 82 (71.95%)
High Score	limun1 for 833.31 points (8 mins 10 secs)
Average Score	603.38 (for 59 correct submissions)

Value	300
Submission Rate	170 / 207 (82.13%)
Success Rate	135 / 170 (79.41%)
High Score	kats for 295.44 points (3 mins 32 secs)
Average Score	226.85 (for 135 correct submissions)

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 (k-1)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[k-2]), which can be achieved if we insert the (k+1)th between the kth and (k-1)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[i-2]);
   return result;

Value	450
Submission Rate	103 / 207 (49.76%)
Success Rate	99 / 103 (96.12%)
High Score	Eryx for 439.45 points (4 mins 25 secs)
Average Score	349.18 (for 99 correct submissions)

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 4-time 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;

Value	900
Submission Rate	58 / 207 (28.02%)
Success Rate	7 / 58 (12.07%)
High Score	misof for 483.30 points (33 mins 9 secs)
Average Score	415.38 (for 7 correct submissions)

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.

A safer solution is to reconstruct a game that could give the input board state. You can do this either forward or backwards, and neither is much harder than the other. Let's consider the forward approach. We start with an empty board, which we represent by {0,0,0,0,0,0,0}, the number of pieces in each column. Now, we check the board, and see which of the columns could have been 'X's first move. Lets say that there is an 'X' in the bottom of the first and third columns, then we recurse with {1,0,0,0,0,0,0} and {0,0,1,0,0,0,0}, the two possibilities for the number of filled rows after one move. We continue branching like this on all possible moves, modifying the number of pieces in a column by 1 such that the moves match the board we are given. Eventually we will either try all possibilities without success (in which case the board is invalid), or else we will find a valid way to get to the given board position. Of course, along the way, we have to be careful that we don't create four in a row on a non-final move, but that's easy to do. Finally, you have to memoize so that you don't expand a board position more than once. To do this, just cache each board position as you expand them, and if you reach a position that has already been expanded, just immediately return false.

    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][5-columns[i]] == marker(turn)){
                columns[i]++;
                if(recurse(columns,1-turn))return true;
                columns[i]--;
            }
        }
        return false;
    }

By logged
TopCoder Member