Match Editorial

In Division 1, coders were faced with a fairly easy set, with 30 individuals solving the hard correctly. Unfortunately, precision issues on the easy caused several of the 250s to fail. In the end, misof, ploh, AdrianKuegel, tjq, and John Dethridge took the top five spots.

In Division 2, nearly all submissions passed on the easy. The medium, identical to the Division 1 easy, was a slaughterhouse during systesting, for many of the same precision issues. Ultimately, only 3 coders got the hard, which proved to be very challenging! Newbie superzn won the division, with another newbie, Michael_Rybak, in a fairly distant second. hungson175 took third.

The Problems

Value	250
Submission Rate	307 / 324 (94.75%)
Success Rate	301 / 307 (98.05%)
High Score	Galeon for 249.41 points (1 mins 23 secs)
Average Score	223.02 (for 301 correct submissions)

This problem was very straightforward. You know the starting balance. You then simply process each transaction given (the order in which you do it doesn't even matter, really). If it's a credit, add the money to the account; for a debit, take the money out.

public int processTransactions (int startingBalance, String[] transactions) {
  int balance = startingBalance;
  for (int i = 0; i < transactions.length; i++) {
    String[] s = transactions[i].split(" ");
    int n = Integer.parseInt(s[1]);
    if (s[0].equals("C"))
      balance += n;
    else
      balance -= n;
  }
  return balance;
}

Value	500
Submission Rate	163 / 324 (50.31%)
Success Rate	28 / 163 (17.18%)
High Score	xander for 391.98 points (15 mins 51 secs)
Average Score	272.24 (for 28 correct submissions)

Value	250
Submission Rate	261 / 284 (91.90%)
Success Rate	92 / 261 (35.25%)
High Score	misof for 243.10 points (4 mins 48 secs)
Average Score	171.06 (for 92 correct submissions)

When you see a problem that involves area of triangles, the first thought is usually "Heron's formula", and in general, this is a good line of thinking. However, floating point precision becomes an issue here. First, we recall Heron's formula (which comes in many slight variations):
A = 1/4 * Sqrt((a + b + c) * (a + b - c) * (a + c - b) * (b + c - a))

For this particular problem, one of the easiest cases to catch the bug is when all three points are colinear. A triangle formed by three colinear points has the area of zero, but double imprecision may make your solution to return non-zero values.

One way to avoid this is to check for colinear points before even considering them as a potential largest triangle. A downside is that this requires a moderate amount of coding. Another (and much safer) option, is to use more precise formula. As shown here, the area of a triangle can be computed as a cross-product of its two sides divided by 2. To compute the cross-product, find the vectors representing two sides of the triangle and use this formula

The only other thing to deal with here was making sure that the points were all the same color, or all different. There's any number of ways to do this. Here, I've given each color a point value of 0, 1 and 2. Summing up the point values of the three points gives us something to go with... If the sum is divisible by 3, we are all set.

/// Parse the input first, saving coordinates to x, y and z, and saving the color to c.
  long best = 0;
  for (int i = 0; i < x.length; i++) 
   for (int j = 0; j < i; j++) 
     for (int k = 0; k < j; k++) 
       if ((c[i] + c[j] + c[k]) % 3 == 0) {
         long dx1 = x[i] - x[j];
         long dy1 = y[i] - y[j];
         long dz1 = z[i] - z[j];
         long dx2 = x[k] - x[j];
         long dy2 = y[k] - y[j];
         long dz2 = z[k] - z[j];            
         long len = (dx1 * dy2 - dx2 * dy1) * (dx1 * dy2 - dx2 * dy1);
         len += (dx1 * dz2 - dx2 * dz1) * (dx1 * dz2 - dx2 * dz1);
         len += (dz1 * dy2 - dz2 * dy1) * (dz1 * dy2 - dz2 * dy1);
         best = Math.max(best, len);
  }
  return Math.sqrt((double)best) / 2.;

Value	1000
Submission Rate	49 / 324 (15.12%)
Success Rate	3 / 49 (6.12%)
High Score	Michael_Rybak for 722.07 points (19 mins 15 secs)
Average Score	616.72 (for 3 correct submissions)

There are a few initial observations that make this problem much simpler to understand and solve. The first, is that since each light is either on or off, we can represent the state of the board as a bitmask, namely, the board has exactly 65,536 different states. Next, note that each button press operation "changes the state" of one or more buttons. In bit manipulation world, this means we're dealing with XOR operations.

Now, notice that since we're looking for the fewest number of moves, that should immediately suggest a breadth first search. Typically, we implement one using a queue, and exploring each board state as we find more efficient ways of getting there:

/* Bitmask XOR values for the moves that change all surrounding lights */
int[] moves = new int[16]; 

/* As we process different sequences, keep track of the fewest moves to get to each state */
int[] best = new int[65536];

/* A simple queue to keep track of which board states we still need to explore */
int[] next = new int[1000000];
int pos = 0;
int end = 0;

/* Process the board state given by the bitmask n */
public void process(int n)
{
  /* For each button, see what happens if we do the 1-point or 2-point move */
  for (int i = 0; i < 16; i++) {
    int new1 = n ^ moves[i];
    int new2 = n ^ (1 << i);
    /* If this gets us to the next state in fewer moves than we already know how to do,
       then update, and we'll explore that state again later */
    if (best[n] + 1 < best[new1]) {
      best[new1] = best[n] + 1;
      next[end] = new1;
      end++;
    }
    if (best[n] + 2 < best[new2]) {
      best[new2] = best[n] + 2;
      next[end] = new2;
      end++;
    }
  }
}

public int fewestMoves(String[] board) {
  /* First, represent the board as a bitmask */
  int start = 0;
  for (int i = 0; i < 4; i++)
    for (int j = 0; j < 4; j++)
      if (board[i].charAt(j) == '1')
        start |= 1 << (i * 4 + j);
  /* Fill our "best" list with max values */
  for (int i = 0; i < 65536; i++) best[i] = 999999;
  /* Define the bitmasks for 1-point operations */  
  for (int i = 0; i < 16; i++) {
    moves[i] |= 1L << i;
    if (i <= 11) moves[i] |= 1L << (i + 4);
    if (i >= 4) moves[i] |= 1L << (i - 4);
    if (i % 4 > 0) moves[i] |= 1L << (i - 1);
    if (i % 4 < 3) moves[i] |= 1L << (i + 1);
  }
  /* Place our initial board state int the queue for processing */
  best[start] = 0;
  next[end] = start;
  end++;
  /* Run through the queue until we're done */
  while (end > pos) {
    process(next[pos]);
    pos++;
  }
  /* Return the fewest number of moves to reach an empty board */
  return best[0];
}

Value	450
Submission Rate	245 / 284 (86.27%)
Success Rate	201 / 245 (82.04%)
High Score	HardCoder for 448.49 points (1 mins 39 secs)
Average Score	342.84 (for 201 correct submissions)

The first thing to see about this problem, and really it's main intent, is that greedy fails. In many cases, the greedy solution is the optimal one, but n = 40 is a good counter-example. Notice that our stacks of cannon balls can have 1, 4, 10, 20, 35... cannon balls in them. A greedy solution would find that 40 = 35 + 4 + 1, or 3 stacks. But, in reality, 2 stacks of 20 is better.

This in mind, a DP-based, subset-sum type of solution, is probably the next thing to come to mind, and given the constraints, this works just fine. This is probably the most common type of solution that was submitted.

Still another way to do it is to work in a recursive fashion, keeping track of the best solution we find, and essentially "backtracking". In other words, try starting with the largest pile and working down (greedy), and see how that goes. Then, try smaller piles instead, but only so long as it's still possible for us to do better than our current best solution, and bail out as soon as that's no longer the case. Since teh greedy solution is already fairly close to the best solution, this highly pruned brute force approach actually runs in time for values much higher than the constraints.

int[] stacks = new int[2001];

/* n = the number of cannon balls to arrange into stacks
   m = the index of the largest pile to consider
   b = the value to beat, bail out if our result will be worse than this */
public int go(int n, int m, int b) {
  if (n == 0) return 0; // No more cannon balls to stack
  if (m == 1) return n; // With piles of 1, this is trivial
  int best = n; // We know, at worst, we can do piles of 1
  int stop = Math.min(b, best); // bail out threshold
  int s = n / stacks[m]; // Max # of stacks of the largest size
  if (s >= stop)  // If this will push us over our limit, bail out
    return best;
  // Try any number of stacks of the current size
  for (int j = s; j >= 0; j--) {
    best = Math.min(best, j + go(n - j * stacks[m], m - 1, stop - j));  // Recurse
    // If we improved our best, we improved our bailout threshold
    stop = Math.min(stop, best); 
    // 1 is the best we can ever expect to do, no sense going further
    if (best == 1) return best; 
  }
  return best;
}

public int fewestPiles(int n) {
  int a = 1;
  int layer = 0;
  // First, figure out how large each stack is
  for (int i = 1; i <= 2000; i++) {
    layer += i;
    stacks[i] = stacks[i - 1] + layer;
    if (stacks[i] <= n) a = i; // Keep track of the largest stack we need to consider
  }
  // Do it!
  return go(n, a, n);
}

Value	1000
Submission Rate	45 / 284 (15.85%)
Success Rate	30 / 45 (66.67%)
High Score	misof for 694.65 points (20 mins 52 secs)
Average Score	522.47 (for 30 correct submissions)

First, we need to parse the input, and determine a number of things: the adjacency for the countries, the number of armies in each country, and which country is ours. A subtle detail to pick out from the problem statement is that, once we start war with a country, we continue battling only that country until the end of the war. Thus, the number of armies in each individual territory is not a consideration in our state space. In fact, our state space is only which countries we own (a bitmask), and the number of armies we have left.

At each state, we need to choose (optimally) the country to attack next. To determine our chances of success when attacking a particular country, we need to know the probability that we'll be left with 1, 2, 3, etc armies after the battle. Multiply each value by our chances of success against all remaining countries knowing that we only have the given number of armies reminaing. Sum those quantities, and we have our overall expected chances of winning by first attacking that country. We just need to pick the best country.

Determining our chances of winning against the other countries with a given number of army units is simply a matter of (memoized) recursion. To determine the likelihood of being left with a given number of army units after a war, we need to simulate (and use Dynamic programming) to calculate out the expected results. Since we'll be needing these values frequently as our solution calculates the results, it's best to have a table created a head of time. So, prob[attacker][defender][remain] is the probability that a country with attacker armies, fighting against a country with defender armies, will be left with remain armies at the end of the war.

int tCount;
double[][] dp = new double[65536][21];
double[][][] prob = new double[21][21][21];
int[] enemy = new int[15];
int[] adjacency = new int[15];
int enemyMask = 0;

/* owned = bitmask of what countries we own
   armies = # of armies we have left */
public double go (int owned, int armies) {
  /* If we've already processed this, return it */
  if (dp[owned][armies] >= 0)
    return dp[owned][armies];
  /* If there's no enemies we haven't already taken over, we've won */
  if (((65535 - owned) & enemyMask) == 0)
    return dp[owned][armies] = 1.0;
  double best = 0;
  /* For each country we don't already own, but that we can reach,
     try attacking it, and see which country is optimal to attack next */
  for (int i = 0; i < tCount; i++)
    if ((owned & (1 << i)) == 0 && (adjacency[i] & owned) > 0) {
      double d = 0;
      /* Expectation = Sum of Prob(left with # armies) * 
         prob(winning with that many armies) */
      for (int j = 1; j <= armies; j++)
        d += prob[armies][enemy[i]][j] * go(owned | (1 << i), j);
      best = Math.max(best, d);
    }
  return dp[owned][armies] = best;
}

public double defeatAll(String[] armies) {
  tCount = armies.length;
  int owned = -1;
  int a = 0;
  enemyMask = 0;
  // Initialize our memoization cache
  for (int i = 0; i < (1 << 16); i++)
    for (int j = 0; j < 21; j++)
      dp[i][j] = -1.0;
  // Build our probability table
  for (int ps = 1; ps <= 20; ps++)
    for (int es = 1; es <= 20; es++) {
      double[][] d = new double[ps + 1][es + 1];
      d[ps][es] = 1.0;
      for (int i = ps; i > 0; i--)
        for (int j = es; j > 0; j--) {
          double d1 = (1.0 * i * i) / (1.0 * i * i + j * j + i * j);
          double d2 = 1.0 - d1;
          d[i][j - 1] += d[i][j] * d1;
          d[i - 1][j] += d[i][j] * d2;
        }
      for (int i = 1; i <= ps; i++)
        prob[ps][es][i] = d[i][0];
    }
  // Parse all the data
  // - find our country
  // - determine size of each army
  // - build a bitmask of enemy countries
  // - build an adjacency bitmask for each country
  for (int i = 0; i < armies.length; i++) {
    String[] s = armies[i].split(" ");
    if (s[0].equals("Y")) {
      owned = 1 << i;
      a = Integer.parseInt(s[1]);
    } else {
      enemy[i] = Integer.parseInt(s[1]);
    }
    if (s[0].equals("E")) {
      enemyMask |= 1 << i;
    }
    for (int j = 2; j < s.length; j++)
      adjacency[i] |= 1 << Integer.parseInt(s[j]);  
  }
  // Do it!
  return go(owned, a);
}