JOIN
 Match Editorial
2005 TopCoder Open
Qualification 1

August 16-17, 2005

Match summary

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

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

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

By brett1479
TopCoder Member