JOIN
 Match Editorial
SRM 288
Wednesday, February 8, 2006

Match summary

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

AccountBalance
Used as: Division Two - Level One:
 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;
}
```
FindTriangle
Used as: Division Two - Level Two:
 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)
Used as: Division One - Level One:
 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.;

```
TurnOffLights
Used as: Division Two - Level Three:
 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];
}

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

```
CountryWar
Used as: Division One - Level Three:
 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];

/* 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;
// 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
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")) {