Match Editorial

Both divisions saw a good number of coders finishing all three problems fairly quickly. In both divisions, the challenge phase proved to be very eventful, with a lot of solutions dropping like flies. In Division 1, system testing knocked down a fair number of the easy and hard submissions as well.

In the end, Division 1 was led by ivan_metelsky, followed by Eryx and rem. In Division 2, malcin took top honors, with RizLA and TheJanitor not far behind.

I'd also offer a special note of congratulations to HiltonLange, for becoming the first (and currently only) VB coder to go red.

The Problems

Value	250
Submission Rate	297 / 356 (83.43%)
Success Rate	221 / 297 (74.41%)
High Score	hubPL for 247.41 points (2 mins 55 secs)
Average Score	204.07 (for 221 correct submissions)

Since our task here is to find the value(s) that occur most frequently, a good way to start is by counting how many times each value occurs. If we are given n values initially, then no element will appear more than n times. So, we can start by looking for any elements that appear n times, and if there are any, that's our result. If not, look for elements that appear n-1 times, etc.

public class ClassScores {

public int[] findMode(int[] scores) {
  int[] count = new int[101];
  for (int i = 0; i < scores.length; i++)
    count[scores[i]]++;
  for (int i = scores.length; i ≥ 1; i--) {
    int c = 0;
    for (int j = 0; j ≤ 100; j++)
      if (count[j] == i)
        c++;
    if (c > 0) {
      int p = 0;
      int[] ret = new int[c];
      for (int j = 0; j ≤ 100; j++)
        if (count[j] == i) {
          ret[p] = j;
          p++;
        }
      return ret;
    }
  }
  return new int[0];
}

}

Value	500
Submission Rate	61 / 356 (17.13%)
Success Rate	17 / 61 (27.87%)
High Score	darkknight7 for 400.51 points (14 mins 57 secs)
Average Score	281.72 (for 17 correct submissions)

Value	250
Submission Rate	262 / 309 (84.79%)
Success Rate	145 / 262 (55.34%)
High Score	antimatter for 244.16 points (4 mins 24 secs)
Average Score	183.93 (for 145 correct submissions)

Simulating the payoff of a loan at a given interest rate is not too difficult to code (we just need to follow the procedure as described in the problem), and since there are at most 600 iterations, we can repeatedly run this simulation as we attempt to find the correct interest rate. If our simulation results in paying off the loan before all of the payments are made in full, then our interest rate is too low. If we have made all of the payments, but there is still a balance left on the loan, then the interest rate is too high. Using these guidelines, we can then do a binary search, or similar method, to iteratively calculate our way to the correct value.

Now, the mathematically minded might be tempted to play with the formula a bit, and move a few things around to expose a geometric series, which can be expressed in a closed form. I'll leave the mathematical gruntwork as an exercise to the reader, but it goes something like this:

Let the monthly compounding factor, c = 1 + interestRate / 1200 (Thus, for 12% interest, c = 1.01),
m = monthlyPayment,
p = price,
n = loanTerm

Then, m * (c ^ n - 1) = p * c ^ n * (c - 1).

You might now notice that algebraic manipulation will get us a closed form expression to isolate any of the variables, except for c, which is needed to calculate the interest rate. Thus, even with some mathematical insight, some programmatic work is still necessary to find the desired result.

public class AutoLoan {

private double amort(double principal, double payment, int term, double interest) {
  double m = interest / 1200;
  if (principal * m > payment)
    return 1;
  for (int i = 0; i < term; i++)
    principal = principal * (1 + m) - payment;
  return principal;
}

public double interestRate(double price, double monthlyPayment, int loanTerm) {
double ret = 0;
double inc = 1000000000;
while (inc ≥ 1.0E-18) {
  double d = amort(price, monthlyPayment, loanTerm, ret + inc);
  if (d ≤ 0) {
    ret += inc;
  }
  inc /= 2.0;
}

return ret;

}

}

Value	1000
Submission Rate	124 / 356 (34.83%)
Success Rate	64 / 124 (51.61%)
High Score	Xero for 954.31 points (6 mins 16 secs)
Average Score	693.88 (for 64 correct submissions)

This is another problem that is fairly easily solved with a bit of grunt work to calculate out the desired values. Since we are looking for the lattice point that is closest to our best fit, our best bet is to first calculate the location of the actual best fit point (using floating point, that is), and then find the closest lattice point.

To find the best fit point, we one important observation: calculating the best fit x-coordinate and the best fit y-coordinate separately will give us our best fit point. Why? Since the scoring of a point as being best fit is based upon the sum of the squares of the distances from each of the points, we see that:

score = sum(d^2) = sum(sqrt((x - x0)^2 - (y - y0)^2)^2)
  = sum((x - x0)^2 + (y - y0)^2)
  = sum((x - x0)^2) + sum((y - y0)^2)

So, to minimize the score, it suffices to minimize each sum separately.

To minimize each sum, a ternary search works well. However, in this case, if you were inclined to do the mathematical gruntwork, then you found a nice shortcut. The average of the x-coordinates will give you the x-coordinate of the best fit point, and the same goes for the y-coordinates. (Why? Hint: Use calculus to prove where the minimum value is.)

Either way, once you have the location of the best fit point it's just simply a matter of finding the closest lattice point, and the easiest way to do this is by rounding. (Note the constraints were intended to prohibit the case where a point was equidistant from multiple lattice points.)

Value	500
Submission Rate	254 / 309 (82.20%)
Success Rate	98 / 254 (38.58%)
High Score	Eryx for 485.03 points (5 mins 1 secs)
Average Score	354.32 (for 98 correct submissions)

Since we are selecting two strings, each 3 characters in length, we know that, in order for them to be of any consequence to our ability to compress the string, they must appear in the string at least once. There are at most 48 3-characters substrings of our input, and thus at most 48 * 48 = 2304 possible pairs, so we can easily brute force through all of these possibilities.

The only trick is how to generate the best possible compressed string, given a source string. Simply search and replacing one string followed by the other is not guaranteed to give us the best possible result. Instead, we need to work left to right, and if the next 3 characters are either of the strings, we know we will compress by one character, and continue searching following that string. Otherwise, we increment by one character, and continue searching.

The only other thing that may have caused issues was short inputs. Anything 6-8 characters in length will compress by exactly 2 characters, always. Anything 3-5 characters in length will compress by 1 character. Anything 1 or 2 characters long can't be compressed at all, so we return the original length.

public class CompressionText {

public int shortestLength(String original) {
  int best = original.length();
  for (int i = 0; i < original.length() - 2; i++)
    for (int j = 0; j < original.length() - 2; j++) {
      int cur = original.length();
      int pos = 0;
      String s1 = original.substring(i, i + 3);
      String s2 = original.substring(j, j + 3);
      while (pos < original.length() - 2) {
        String s = original.substring(pos, pos + 3);
        if (s.equals(s1) || s.equals(s2))
          { cur--; pos += 3; }
        else
          pos++;
      }
      best = Math.min(best, cur);
    }
  return best;
}

}

Value	1000
Submission Rate	34 / 309 (11.00%)
Success Rate	22 / 34 (64.71%)
High Score	rem for 665.27 points (22 mins 42 secs)
Average Score	521.16 (for 22 correct submissions)

At first glance, a board with 100 spaces and up to four players suggests a state space of 100,000,000 possibilities, making it computationally impossible to simply look at every possible state. Instead, we need to consider each player individually.

We can calculate, for a given player, the possibility that they win the game after exactly n moves, having started on space i, as the sum of the probabilites of rolling a given value, multiplied by the chances of them finishing the game after exactly n-1 moves, starting from space j (where j is the space they land on after making their move). As we calculate these values, we also keep track of the probability that the player has _not_ finished the game after n moves. Then, the probability of a player winning the game on his n-th move is the probability that he finishes on that move, multiplied by the probabilities that each of his opponents hasn't yet finished. Iterate this, starting from n = 1, and sum the results, to determine the overall probability of a player winning.

Notice the constraints in this problem are setup so that a board where a player can never win (e.g. twelve consective chutes), or where the probability of getting to the finish is very very small, are not allowed. The worst case scenario allowed under the constraints is where there are the maximum possible number of chutes, all going back to space 0, that alternate location. e.g. chutes on spaces 98, 96, etc. In this case, calculating out 10,000 moves for each player gives sufficient precision.

public class ChutesAndLadders {

int REPS = 12000;

public double[] winningChance(int[] start, int[] end, int[] players) {
  // Define probabilities of rolling 2, 3, ... , 12
  double[] p = new double[]{0, 0, 1.0/36, 2.0/36, 3.0/36, 4.0/36,
   5.0/36, 6.0/36, 5.0/36, 4.0/36, 3.0/36, 2.0/36, 1.0/36};
  // Where does each space "land"
  int[] dest = new int[100];
  // First assume no chute/ladder
  for (int i = 0; i < 100; i++)
    dest[i] = i;
  // If there is a chute/ladder, assign it
  for (int i = 0; i < start.length; i++)
    dest[start[i]] = end[i];
  // Keep track of the probability that a player will get to the end,
  // assuming they stated in space X, and have taken Y moves.
  double[][] win = new double[100][REPS];
  // Probabiliy that a player will NOT have won after Y moves.
  double[][] notWin = new double[100][REPS];
  for (int i = 0; i < 99; i++) {
    win[i][0] = 0;
    notWin[i][0] = 1;
  }
  // On space 99, you've already gotten to the end
  win[99][0] = 1;
  notWin[99][1] = 0;
  
  double[] ret = new double[players.length];
  double eps = 1.0;
  
  // Calculate the probabilities of exiting the board after r moves, starting from space s
  for (int r = 1; r < REPS; r++) {
    for (int s = 0; s < 99; s++) {
      for (int d = 2; d ≤ 12; d++)
        if (s + d ≥ 99)
          win[s][r] += p[d] * win[99][r - 1];
        else
          win[s][r] += p[d] * win[dest[s + d]][r - 1];
      win[s][r] = Math.min(win[s][r], 1.0);
      notWin[s][r] = notWin[s][r - 1] - win[s][r];
    }
    for (int c = 0; c < players.length; c++) {
      double pr = 1;
      for (int m = 0; m < players.length; m++)
        if (m > c)
          pr *= notWin[players[m]][r - 1];
        else if (m < c)
          pr *= notWin[players[m]][r];
        else
          pr *= win[players[m]][r];
      ret[c] += pr;
      eps -= pr;
    }
  }

  return ret;
}

}