Wednesday, May 4, 2005 Match summary In Division 1, pparys took home his first SRM victory, solving all three problems correctly. bladerunner and Petr took the second and third slots. venco, Ruberik and misof rounded out the set of coders who successfully got all three. In division 2, dplass was first, followed by matthew0028 who failed systests on his easy. As an interesting note, had his easy passed, he would still have been second place, but by a margin of less than 1 point. haixiashi made a good entrance to TopCoder with a third place finish, which catapaulted him into division 1 for next time. The ProblemsBlackjackWinnerUsed as: Division Two  Level One:
This problem, given a certain value of bet will return one of four values: bet, 0, bet, or bet * 3 / 2. The trick is to frame the if statements in the right order. Notice from the constraints that bet is always even, so rounding isn't an issue here. public int winnings(int bet, int dealer, int dealerBlackjack, int player, int blackjack) { if (player > 21  player < dealer && dealer ≤ 21) return bet; if (dealerBlackjack == 1 && blackjack == 1) return 0; if (dealerBlackjack == 1 && blackjack == 0) return bet; if (blackjack == 1 && dealerBlackjack == 0) return bet * 3 / 2; if (dealer > 21  player > dealer) return bet; return 0; }ReportAccess Used as: Division Two  Level Two: Used as: Division One  Level One:
This problem was not especially difficult, and was rather straightforward. The point here was to see (hopefully) a quick way to write a solution. The initial thought might be to split out the permissions for each user into an array, split out the required permissions into an array, and compare, for each user, whether or not their permissions include all of the necessary ones. This is a fine solution, but could take a little while to code (relatively speaking). The next thought might be to do a simple string search for each required permission within the permission string for each user. However, this by itself could fail in the case where the report requires permission for "system", and the user only has permission on "systemadmin". Instead, we need to search for a string that can't be a substring of something else. We do this by padding each user's permission string with spaces on each end. We can then search for each required permission, padded with a space at the front and back, to ensure that it won't be a substring of another permission. The final requirement is to sort the resulting list of allowed users, which is handled trivially by the API for your language of choice. public String[] whoCanSee(String[] userNames, String[] allowedData, String[] reportData) { boolean[] b = new boolean[userNames.length]; int c = 0; for (int i = 0; i < userNames.length; i++) { allowedData[i] = " " + allowedData[i] + " "; b[i] = true; for (int j = 0; j < reportData.length; j++) if (allowedData[i].indexOf(" " + reportData[j] + " ") == 1) b[i] = false; if (b[i]) c++; } String[] ret = new String[c]; c = 0; for (int i = 0; i < userNames.length; i++) if (b[i]) { ret[c] = userNames[i]; c++; } Arrays.sort(ret); return ret; }AirTravel Used as: Division Two  Level Three:
That we are given the distance formula is a big help here, as most people probably don't have it memorized. (I sure didn't.) Furthermore, deriving it can be a bit of a time consuming, and certainly mathintense exercise. Of course, looking for the appropriate online resources is always a good option, too. In any case, the first step is to calculate the distances between each pair of airports that we are allowed to travel, and store them in an array, where d[i][j] is the distance from airport i to airport j. Note the need to convert degrees to radians when using the trig functions. If we are not allowed to travel from airport i to airport j, we use a suitably high "infinity" value, like 999999, as our distance. Next, we loop over our aiports, and essentially determine if the distance from airport i to airport j can be made shorter by travelling through airport k on the way. We execute this loop as many times as there are airports, to allow for the possibility that we travel through all of the airports. Notice here that if travel from i to j is not allowed, then travelling through k will only be better if travel from i to k and k to j are both allowed; this is due to our use of an infinity value. Finally, we check our "best" distance from origin to destination, and return 1 if it's our infinity value (meaning we can't make that trip), or the value. double[][] d; double mul = 3.14159265358979323 / 180; public double cdist(double lat1, double lon1, double lat2, double lon2) { return 4000 * Math.acos(Math.sin(lat1 * mul) * Math.sin(lat2 * mul) + Math.cos(lat1 * mul) * Math.cos(lat2 * mul) * Math.cos(lon1 * mul  lon2 * mul)); } public double shortestTrip(int[] latitude, int[] longitude, String[] canTravel, int origin, int destination) { d = new double[latitude.length][latitude.length]; for (int i = 0; i < latitude.length; i++) for (int j = 0; j < latitude.length; j++) if (i == j) d[i][j] = 0; else d[i][j] = 999999; for (int i = 0; i < canTravel.length; i++) { String[] s = canTravel[i].split(" "); for (int j = 0; j < s.length; j++) { int k = Integer.parseInt(s[j]); if (i != k) { double t = cdist(latitude[i], longitude[i], latitude[k], longitude[k]); System.out.println(i+" "+k+" "+t); d[i][k] = Math.min(d[i][k], t); } } } for (int n = latitude.length  2; n ≥ 0; n) for (int i = n; i < latitude.length; i++) for (int j = 0; j < latitude.length; j++) for (int k = 0; k < latitude.length; k++) d[i][j] = Math.min(d[i][j], d[i][k] + d[k][j]); if (d[origin][destination] == 999999) return 1; return d[origin][destination]; }BrokenCalculator Used as: Division One  Level Two:
This problem, at first glance, might appear like a straightforward Breadth First Search, but upon digging in a little further, it's obvious a little more thought is needed. The first thing to do is determine what numbers we can type in without using any operators. If our target is within this set, we return 1, 2, or 3 as appropriate. Otherwise, we start keeping track of the fewest keys needed to get to every number from 0 to 999. Since our target will require an operator key after entering some number, we initialize those values we can reach to 2, 3, or 4, and the remainder to a suitable infinity value. Next, we set up a queue for which values we will search, and populate it with all the values we can reach without operators. Then, we take numbers out of the queue one at a time, try each of the [up to four] operations on them, and add them back to the queue if the resultant number has been reached in less steps than our previous best. We continue this until the queue is empty. Note that after performing an operation, we will need to either press the equals key to see our result, or press another operator to continue our calculation. Hence, we always add 1 more key press after performing the operation. Once the queue is empty, if our best result for the target is our infinity value, then it can't be reached, and return 1. Else, return the best result. // fewest keystrokes to get to target values int[] best = new int[1000]; // fewest keystrokes not involving any operators int[] bestnop = new int[1000]; // queue int[] q = new int[1000000]; int p = 0; int r = 0; // add a value to the queue void add(int i) { q[p] = i; p++; } // pull next value from queue int get() { r++; return q[r  1]; } // is there anything in the queue? boolean full() { return (p > r); } public int fewestKeys(int[] keys, String operators, int target) { // which operations can we do boolean plus = (operators.indexOf("+") > 1); boolean sub = (operators.indexOf("") > 1); boolean mul = (operators.indexOf("*") > 1); boolean div = (operators.indexOf("/") > 1); // initialize our infinity values for (int i = 0; i < 1000; i++) { best[i] = 999999; bestnop[i] = 999999; } // everything we can type with three numbers for (int i = 0; i < keys.length; i++) for (int j = 0; j < keys.length; j++) for (int k = 0; k < keys.length; k++) { bestnop[keys[i] * 100 + keys[j] * 10 + keys[k]] = 3; best[keys[i] * 100 + keys[j] * 10 + keys[k]] = 3; add(keys[i] * 100 + keys[j] * 10 + keys[k]); } // ...with two numbers for (int i = 0; i < keys.length; i++) for (int j = 0; j < keys.length; j++) { bestnop[keys[i] * 10 + keys[j]] = 2; best[keys[i] * 10 + keys[j]] = 2; add(keys[i] * 10 + keys[j]); } // ... with one number for (int i = 0; i < keys.length; i++) { bestnop[keys[i]] = 1; best[keys[i]] = 1; add(keys[i]); } // if we don't need any operators, no need to continue if (best[target] < 999999) return best[target]; // we know we have to perform an operation, so add that keypress for (int i = 0; i < 1000; i++) if (best[i] < 999999) best[i]++; // while there's more searching to do... while (full()) { // get next value to search int n = get(); // try each allowed operation using each number we can reach without operators // ... lather, rinse, repeat for (int i = 0; i < 1000; i++) if (bestnop[i] < 999999) { if (plus && n + i < 1000) { int t = best[n] + bestnop[i] + 1; if (t < best[n + i]) { best[n + i] = t; add(n + i); } } if (sub && n  i ≥ 0) { int t = best[n] + bestnop[i] + 1; if (t < best[n  i]) { best[n  i] = t; add(n  i); } } if (mul && n * i < 1000) { int t = best[n] + bestnop[i] + 1; if (t < best[n * i]) { best[n * i] = t; add(n * i); } } if (div && i > 0) { int t = best[n] + bestnop[i] + 1; if (t < best[n / i]) { best[n / i] = t; add(n / i); } } } } // is it impossible? if (best[target] == 999999) return 1; // otherwise return the result return best[target]; }PatternCutting Used as: Division One  Level Three:
The nature of this problem, especially given the tight constraint on the size of the paper, is that most people could do this very easily by hand. However, teaching a computer to do it is the real challenge here. My solution works like this: first, figure out the four rotations of the pattern, and store them somehow. Then, setup an imaginary piece of paper, which is all there. Next, start from the upperleft, traversing lefttoright, top to bottom, trying to cut out a pattern at each location, rotated in each of the four orientations. Every time this is possible, cut it from our paper, recurse (starting at the next position), then put the pattern back into the paper to try the next rotation/position. We simply keep track of the highest counts as we go, and return the best result. But, given 36 squares in the sheet of paper, that's 36 * 4 cutouts to try, and recursing after each attempt will clearly give us way too long of a run time. So, we need to optimize things a bit. I introduced several optimizations in my solution. First, note that if the pattern is a 1x1 square or a 1x2 square, these are the two cases that return the largest number of cutouts, and are very easy results to calculate right up front. Now, as we are cutting out from our pattern, we can do another big optimization: bailing out when we know that we can't improve our best result. For instance, if the paper has 36 squares, and the pattern uses 5 squares, we know, with certainty, that our result can never be more than 7. So, if we find a way to make 7 cutouts, we can return that result and look no more. Similarly, if we're at row 2, column 1 on this 6x6 sheet, we know that we only have 30 more squares to look at, so we can't possibly cut out more than 6 more squares. In my solution, I use the variable localMax to indicate this. Similarly, when recursing, we pass in the best result we have found so far from that point, passed as the parameter min. So, for instance, if my recursion has yielded that it's possible to cut out 5 of a pattern from where I am already, I know that further recursive calls need not consider cases where it's no longer possible to cut out more than 5, since they cannot possibly improve my result. After all this is done, the recursive function simply returns the best result. // the sheet we cut from public boolean[][] b; // size of our paper public int mx, my; // the four rotations public String[][] p; // number of blocks in the pattern public int c; // cut out a pattern, rotated, at a given position public void cut(int x, int y, int r) { for (int i = 0; i < p[r].length; i++) for (int j = 0; j < p[r][i].length(); j++) if (p[r][i].charAt(j) == 'X') b[x + j][y + i] = true; } // paste the pattern back in public void paste(int x, int y, int r) { for (int i = 0; i < p[r].length; i++) for (int j = 0; j < p[r][i].length(); j++) if (p[r][i].charAt(j) == 'X') b[x + j][y + i] = false; } // can we cut the pattern out from here? public boolean canCut(int x, int y, int r) { if (x + p[r][0].length() > mx) return false; if (y + p[r].length > my) return false; for (int i = 0; i < p[r].length; i++) for (int j = 0; j < p[r][i].length(); j++) if (p[r][i].charAt(j) == 'X' && b[x + j][y + i]) return false; return true; } // Determine the most cuttings we can do, starting at (x, y), // knowing that we don't care about results less than min public int partialMax(int x, int y, int min) { int best = 0; while (y < my) { int maxRemain = (my  y  1) * mx + (mx  x); maxRemain /= c; if (min > maxRemain) return best; if (best > maxRemain) return best; int localbest = best; for (int r = 0; r < 4; r++) if (canCut(x, y, r)) { cut(x, y, r); x++; if (x ≥ mx) { x = 0; y++; } localbest = Math.max(localbest, 1 + partialMax(x, y, localbest)); x; if (x < 0) { x = mx  1; y; } paste(x, y, r); } best = Math.max(best, localbest); x++; if (x ≥ mx) { x = 0; y++; } } return best; } public int getMax(int width, int height, String[] pattern) { // Deal with the trivial cases that could cause a timeout if (pattern.length * pattern[0].length() == 2) return (height * width / 2); if (pattern.length * pattern[0].length() == 1) return height * width; // Determine the size of paper, and number of blocks in our pattern c = 0; for (int i = 0; i < pattern.length; i++) for (int j = 0; j < pattern[i].length(); j++) if (pattern[i].charAt(j) == 'X') c++; my = height; mx = width; // create our virtual paper b = new boolean[width][height]; // and our pattern rotations p = new String[4][]; p[0] = pattern; p[2] = new String[pattern.length]; for (int i = 0; i < pattern.length; i++) { p[2][i] = ""; for (int j = 0; j < pattern[0].length(); j++) p[2][i] += pattern[pattern.length  1  i].charAt(pattern[0].length()  1  j); } p[1] = new String[pattern[0].length()]; for (int i = 0; i < pattern[0].length(); i++) { p[1][i] = ""; for (int j = 0; j < pattern.length; j++) p[1][i] += pattern[j].charAt(pattern[j].length()  i  1); } p[3] = new String[pattern[0].length()]; for (int i = 0; i < pattern[0].length(); i++) { p[3][i] = ""; for (int j = 0; j < pattern.length; j++) p[3][i] += pattern[pattern.length  1  j].charAt(i); } // start our searchcutting from the upper left return partialMax(0, 0, 0); } 
