Match Editorials

Match summary

The easy problem proved to be fairly straightforward for most coders. The medium posed a little more difficulty, although noticing a few tricks made the problem simpler. Though there were a handful of submissions, it turned out the hard was just a bit complicated, and none of the five submissions survived.

In the end, good times on the first two problems, and a handful of challenges were the secret to doing well this match. mirosuaf, Quelloquialism, and gaoyihan took the top three slots.

The Problems

Value	250
Submission Rate	49 / 53 (92.45%)
Success Rate	35 / 49 (71.43%)
High Score	mirosuaf for 248.61 points (2 mins 7 secs)
Average Score	214.47 (for 35 correct submissions)

This is a fairly straightforward task of just looking at the k-th character of each name (among those that have at least k characters), and keeping track of how many times each letter appears. Then, return the one that appears the most times.

public String popularInitial(String[] names, int k) {
    int[] count = new int[256];
    for (int i = 0; i < names.length; i++)
        if (names[i].length() >= k)
            count[names[i].charAt(k - 1)]++;
    int best = 0;
    String res = "";
    for (char c = 'A'; c <= 'Z'; c++)
        if (count[c] > best) {
            best = count[c];
            res = "" + c;
        }
    return res;
}

Value	500
Submission Rate	27 / 53 (50.94%)
Success Rate	17 / 27 (62.96%)
High Score	mirosuaf for 479.55 points (5 mins 55 secs)
Average Score	339.17 (for 17 correct submissions)

Several coders quickly jumped at this problem using Dynamic Programming, or recursion with memoization. The idea is to try dividing the paper at each possible location, and then count the maximum number of moves that could be made on either resulting piece. Indeed, this works, but there's a simpler solution, although it requires a bit of insight on the problem.

First, it's useful to check if we're in a forbidden state at the beginning. If we are, then there's nothing we can do. Also, if the forbidden size is 2, then (except for a 1x1 paper) it's impossible to divide the paper without eventually having a piece with a side length of 2. Now that we've taken care of those "special" cases, let's consider the more general case.

Notice, first and foremost, that the most moves we can make is 1 plus the most moves we can make on either resulting piece (after whatever cut we decided to make). So, we only ever need to consider the piece that has more remaining moves, namely, the larger of the two pieces. In other words, after each move, we want one of the remaining pieces to be as large as possible.

So, the best thing to do is to cut off 1-unit wide strips, then when we're down to a single strip, cut off 1x1 squares one at a time. The only thing to check is that if we're about to cut off a single strip, and that would leave us a forbidden size, then we instead have to cut of a 2-unit wide strip. With this in mind, we can calculate the number of moves in closed form, with no DP required.

public int mostMoves (int width, int height, int forbidden) {
    if (width == 1 && height == 1)
        return 0;
    if (forbidden == 2 || forbidden == height || forbidden == width)
        return -1;
    int ret = 0;
    if (height > 1) {
        ret += height - 2;
        if (height < forbidden) ret++;
    }
    if (width > 1) {
        ret += width - 2;
        if (width < forbidden) ret++;
    }
    return ret;
}

Value	1000
Submission Rate	5 / 53 (9.43%)
Success Rate	0 / 5 (0.00%)
High Score	null for null points (NONE)
Average Score	No correct submissions

Apparently this one was troublesome for coders. In reality, all that was required was a brute force approach. But what exactly did we have to brute force through? Well, we have two pieces of paper, and each can be flipped or rotated, meaning there are 8 possible orientations for each paper.

Then, we know that they can be adjacent, or partially/fully overlapping. If we fix the location of the first piece on a grid at (0,0), and allow the second piece to be at any location from (0,0) to (5,5), that covers all possible full/partial overlaps and adjacencies.

So, we have 8 orientiations of each piece, and 36 placements, so there are 8 * 8 * 36 = 2304 possible resulting grids. For each of those, we find the largest rectangle, and return the largest of those. This last part requires either a bit of pruning/optimization, or some minor algorithmic trickery, but is a fairly well known problem.

boolean[][][][] paper = new boolean[2][8][5][5];

public int biggestRectangle(String[] paper1, String[] paper2) {
  
  // Represent our two scraps of paper
  for (int i = 0; i < paper1.length; i++)
    for (int j = 0; j < paper1[i].length(); j++)
      paper[0][0][i][j] = paper1[i].charAt(j) == 'X';
  for (int i = 0; i < paper2.length; i++)
    for (int j = 0; j < paper2[i].length(); j++)
      paper[1][0][i][j] = paper2[i].charAt(j) == 'X';
  
  // Represent the rotations
  for (int k = 0; k <= 1; k++)
    for (int r = 1; r <= 3; r++)
      for (int i = 0; i < 5; i++)
        for (int j = 0; j < 5; j++)
          paper[k][r][i][j] = paper[k][r - 1][j][4 - i];
  
  // Represent the flips
  for (int k = 0; k <= 1; k++)
    for (int r = 0; r <= 3; r++)
      for (int i = 0; i < 5; i++)
        for (int j = 0; j < 5; j++)
          paper[k][r + 4][i][j] = paper[k][r][4 - i][j];  
  
  // Try each possible arrangement, and find the biggest area it yields
  int best = 0;
  for (int r1 = 0; r1 <= 7; r1++) for (int r2 = 0; r2 <= 7; r2++)
    for (int x = 0; x <= 5; x++) for (int y = 0; y <= 5; y++) {
      boolean[][] grid = new boolean[10][10];
      for (int i = 0; i < 5; i++) for (int j = 0; j < 5; j++) {
        grid[i][j] |= paper[0][r1][i][j];      
        grid[x + i][y + j] |= paper[1][r2][i][j];
      }
      for (int xx = 0; xx < 10; xx++) for (int yy = 0; yy < 10; yy++)
        if (grid[xx][yy]) {
          boolean[][] fill = new boolean[10 - xx][10 - yy];
          fill[0][0] = true;
          int test = 1;
          for (int i = 1; i < 10 - xx; i++)
            if (fill[i - 1][0] && grid[xx + i][yy]) {
              fill[i][0] = true;
              test = Math.max(test, i + 1);
            }
          for (int j = 1; j < 10 - yy; j++)
            if (fill[0][j - 1] && grid[xx][yy + j]) {
              fill[0][j] = true;
              test = Math.max(test, j + 1);
            }
          for (int i = 1; i < 10 - xx; i++) for (int j = 1; j < 10 - yy; j++)
            if (fill[i - 1][j] && fill[i][j - 1] && grid[xx + i][yy + j]) {
              fill[i][j] = true;
              test = Math.max(test, (i + 1) * (j + 1));
            }
          if (test > best) best = test;
        }
    }
  return best;
}