Wednesday, August 10, 2005 Match summary 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 ProblemsClassScoresUsed as: Division Two  Level One:
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 n1 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]; } }AutoLoan Used as: Division Two  Level Two: Used as: Division One  Level One:
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), 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.0E18) { double d = amort(price, monthlyPayment, loanTerm, ret + inc); if (d ≤ 0) { ret += inc; } inc /= 2.0; } return ret; } }MissileTarget Used as: Division Two  Level Three:
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 xcoordinate and the best fit ycoordinate 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) 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 xcoordinates will give you the xcoordinate of the best fit point, and the same goes for the ycoordinates. (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.) CompressionTextUsed as: Division One  Level Two:
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 3characters 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 68 characters in length will compress by exactly 2 characters, always. Anything 35 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; } }ChutesAndLadders Used as: Division One  Level Three:
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 n1 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 nth 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; } } 
