Match Editorial

This set's easy problem required a simple conversion from filesize to bitrate. On the contrary, this room probably had the most difficult hard problem. It didn't phase the top competitors, but many div 1 coders were unable to submit it. krijgertje, reid, and snewman, who all scored above 900, led the pack.

The Problems

Value	250
Submission Rate	322 / 350 (92.00%)
Success Rate	308 / 322 (95.65%)
High Score	PE for 247.60 points (2 mins 14 secs)
Average Score	199.26 (for 308 correct submissions)

Here we convert a time to kilobits per second so that the total video becomes a particular size. Using the supplied conversion rates, we convert the given size to bits. Next, we parse the given string to obtain the number of seconds required by the video. The number of bits over the number of seconds gives the required bits per second. Dividing by 1000 gives kilobits per second. Java code follows:

int S(String s) { return Integer.parseInt(s); }
public double bitrate(String length, int desiredSize) {
  String[] toks = length.split("[:]");
  long mbs = desiredSize*1048576L*8, 
       secs = S(toks[2]) + 60 * ( S(toks[1]) + 60 * S(toks[0]) );
  return mbs/1000.0/secs;
}

Value	750
Submission Rate	188 / 350 (53.71%)
Success Rate	153 / 188 (81.38%)
High Score	krijgertje for 705.02 points (5 mins 48 secs)
Average Score	435.92 (for 153 correct submissions)

Here we must count how many winning moves we have. This problem structure lends itself to a recursive solution: after making a move, we have won if the opponent has no winning moves. Thus, to compute the number of winning moves, we loop over all valid moves, and then see if the opponent has any winning moves from the updated position. Java code follows:

boolean canMove(boolean[][] mat, int r, int c) {
   if (mat[r][c]) return false;
   for (int x = -1; x <= 1; x++) for (int y = -1; y <= 1; y++) {
      if (x*y != 0 || x+y == 0) continue;
      if (r+y < 0 || r+y >= 4 || c+x < 0 || c+x >= 4) continue;
      if (mat[r+y][c+x]) return false;
   } return true;
}
int comp(boolean[][] mat, boolean first) {
   int wins = 0;
   for (int r = 0; r < 4; r++) for (int c = 0; c < 4; c++) {
      if (!canMove(mat,r,c)) continue;
      mat[r][c] = true;
      if (comp(mat,false) == 0) wins++;
      mat[r][c] = false;
   } 
   return wins;
}
public int winningMoves(String[] grid) {
   boolean[][] mat = new boolean[4][4];
   for (int r = 0; r < 4; r++) for (int c = 0; c < 4; c++) 
      if (grid[r].charAt(c) == 'X') mat[r][c] = true;
   return comp(mat,true);
}