Match Editorials

Match summary

This match proved to be fairly simple, especially on the first two problems, which most coders solved very quickly. The third, a classic TC-style DP problem, required a bit more thinking and planning, and as such had less submissions.

Top honors go to Burunduk3, who won in part due to some success in the challenge phase. In second was tomekkulczynski, who offered solid scores on all three problems. After some tough luck in the challenge phase, would-be winner MB__ finished third. gurugan1 and fpavetic rounded out the top five. Congratulations to all 18 competitors who correctly solved all three problems.

The Problems

Value	250
Submission Rate	111 / 122 (90.98%)
Success Rate	89 / 111 (80.18%)
High Score	sluga for 248.94 points (1 mins 51 secs)
Average Score	227.38 (for 89 correct submissions)

The big thing to see here is that on a maximum (50x50) sized grid, even a brute force solution checking all possible starting and ending points will run in time. The basic thrust of the solution: For each possible pair of points, if both are a bus stop, see if that distance is longer than the greatest distance found so far:

public int maximumFare (String[] blocks) {
   int best = 0;
   for (int i = 0; i < blocks.length; i++) for (int j = 0; j < blocks[i].length(); j++)
      for (int x = 0; x < blocks.length; x++) for (int y = 0; y < blocks[x].length(); y++)
         if (blocks[i].charAt(j) == 'B' && blocks[x].charAt(y) == 'B')
            best = Math.max(best, Math.abs(x - i) + Math.abs(y - j));
   return best;
}

Value	500
Submission Rate	99 / 122 (81.15%)
Success Rate	69 / 99 (69.70%)
High Score	mateuszek for 486.40 points (4 mins 46 secs)
Average Score	383.08 (for 69 correct submissions)

Similar to the first problem, we can again note that on a 50x50 board, a brute force solution, checking all possible (legal) positions for placing your rook, is feasible to run in time. The first thing to do is to determine where the potential legal moves are. A two-dimensional boolean array works well.

Then, we can loop through all positions on the board and, for each legal position, determine how many legal positions would remain if we made our move on that square. Keeping track of the move that leaves the fewest number of legal squares, we have a solution that looks like this:

public int bestPosition (String[] board) {
   int best = 2501;
   boolean[][] unsafe = new boolean[board.length][board[0].length()];
   for (int i = 0; i < board.length; i++) for (int j = 0; j < board[i].length(); j++)
      if (board[i].charAt(j) == 'X')
         for (int x = 0; x < board.length; x++) for (int y = 0; y < board[x].length(); y++)
            if (i == x || j == y)
               unsafe[x][y] = true;
   for (int i = 0; i < board.length; i++) for (int j = 0; j < board[i].length(); j++)
      if (!unsafe[i][j]) {
         int test = 0;
         for (int x = 0; x < board.length; x++) for (int y = 0; y < board[x].length(); y++)
            if (i != x && j != y && !unsafe[x][y])
               test++;
         best = Math.min(best, test);
      }
   if (best > 2500) return -1;
   return best;
}

The above solution was fairly simple to think up. However, a few key observations can lead to a simpler solution. An interesting fact about this problem is that it doesn't matter where you place your rook. If there are any legal moves available to you, the number of remaining moves will be the same no matter which one you choose. Remember that a legal move is a square where there are no other rooks in that column, and no other rooks in that row. Let row = the # of rows that don't have a rook, and col = the # of columns that don't have a rook. Then, if either is 0, there are no moves available, so we should return -1. Otherwise, we know that after we place our rook, there will be row-1 rows and col-1 columns available, thus there will be (row-1)*(col-1) squares available. The following was written by OlexiyO:

public int bestPosition(String[] board) {
   int N = board.length;
   int W = board[0].length();
   boolean[] rok = new boolean[N]; Arrays.fill(rok, true);
   boolean[] cok = new boolean[W]; Arrays.fill(cok, true);
   for (int i = 0; i < N; i++) for (int j = 0; j < W; j++) {
      rok[i] &= (board[i].charAt(j) == '.');
      cok[j] &= (board[i].charAt(j) == '.');
   }
   int r = 0;
   for (int i = 0; i < N; i++) if (rok[i]) r++;
   int c = 0;
   for (int i = 0; i < W; i++) if (cok[i]) c++;
   return (r * c == 0) ? -1 : (r - 1) * (c - 1);
}

Value	1000
Submission Rate	40 / 122 (32.79%)
Success Rate	19 / 40 (47.50%)
High Score	MB__ for 929.66 points (7 mins 56 secs)
Average Score	596.35 (for 19 correct submissions)

In a TopCoder sense, this problem is classic Dynamic Programming. First, imagine we are physically stringing the beads. Any time we go to place a bead, we need to look at our string to see which two beads we last placed, and make sure that whatever we place next is a different color than either of those two. This lends itself to a good definition of our state space: the number of each color bead remaining to be strung, and the colors of the last two beads.

Coders mostly used either a straight DP approach with an array to store the values of the subproblems, or a recursive (memoized, of course!) solution that utilized some type of hashtable to store the partial results. For the straight DP approach, it may be helpful to think of every case as having five different color beads, with the possibility that there are 0 beads of the last two colors. My solution below uses this approach.

As a side note, the constraint about there being a total of no more than 35 beads may have seemed odd at first glance. In fact, this was to ensure that the return value could fit (with room to spare) into a 64-bit integer.

There are several interesting things one might notice about this problem. One is that, for cases with three colors, the largest and smallest quantity of any single color can differ by at most one, or else there is no way to string the beads (fairly simple to demonstrate, but left as an exercise to the reader).

public long numWays (int[] beads) {
   int[] b = new int[5];
   for (int i = 0; i < beads.length; i++) b[i] = beads[i];
   for (int i = beads.length; i < 5; i++) b[i] = 0;
   long[][][][][][][] dp = new long[b[0] + 1][b[1] + 1][b[2] + 1][b[3] + 1][b[4] + 1][5][5];
   dp[1][1][0][0][0][0][1] = 1;
   dp[1][1][0][0][0][1][0] = 1;
   dp[1][0][1][0][0][0][2] = 1;
   dp[1][0][1][0][0][2][0] = 1;
   dp[0][1][1][0][0][2][1] = 1;
   dp[0][1][1][0][0][1][2] = 1;
   if (beads.length > 3) {
      dp[1][0][0][1][0][0][3] = 1;
      dp[1][0][0][1][0][3][0] = 1;
      dp[0][1][0][1][0][1][3] = 1;
      dp[0][1][0][1][0][3][1] = 1;
      dp[0][0][1][1][0][2][3] = 1;
      dp[0][0][1][1][0][3][2] = 1;
   }
   if (beads.length > 4) {
      dp[1][0][0][0][1][0][4] = 1;
      dp[1][0][0][0][1][4][0] = 1;
      dp[0][1][0][0][1][1][4] = 1;
      dp[0][1][0][0][1][4][1] = 1;
      dp[0][0][1][0][1][2][4] = 1;
      dp[0][0][1][0][1][4][2] = 1;
      dp[0][0][0][1][1][3][4] = 1;
      dp[0][0][0][1][1][4][3] = 1;
   }
   for (int v = 0; v <= b[0]; v++) for (int w = 0; w <= b[1]; w++) for (int x = 0; x <= b[2]; x++)
      for (int y = 0; y <= b[3]; y++) for (int z = 0; z <= b[4]; z++) {
         for (int i = 0; i < 5; i++) for (int j = 0; j < 5; j++) {
            if (v > 0 && i != 0 && j != 0) dp[v][w][x][y][z][j][0] += dp[v - 1][w][x][y][z][i][j];
            if (w > 0 && i != 1 && j != 1) dp[v][w][x][y][z][j][1] += dp[v][w - 1][x][y][z][i][j];
            if (x > 0 && i != 2 && j != 2) dp[v][w][x][y][z][j][2] += dp[v][w][x - 1][y][z][i][j];
            if (y > 0 && i != 3 && j != 3) dp[v][w][x][y][z][j][3] += dp[v][w][x][y - 1][z][i][j];
            if (z > 0 && i != 4 && j != 4) dp[v][w][x][y][z][j][4] += dp[v][w][x][y][z - 1][i][j];
         }
      }
   long ret = 0;
   for (int i = 0; i < 5; i++) for (int j = 0; j < 5; j++)
      ret += dp[b[0]][b[1]][b[2]][b[3]][b[4]][i][j];
   return ret;
}