Wednesday, January 3, 2007 Match summaryWhat do school boys and girls do during the winter holidays? That's right, they compete in TopCoder High School SRMs! More than 200 competitors took part in HS SRM 26, with Zuza winning the match with a comfortable lead. fatit finished second and reiten rounded out the top three.The ProblemsThirdBuyDiscountUsed as: Division One - Level One: It should be easy to see that putting the most expensive items into the discount positions (positions with indices divisible by 3) is the optimal strategy. Accordingly, just sort the items by the price, and apply the discount for the n / 3 most expensive ones, with n representing the number of the items. Java code follows: public static double minCost(int[] prices, int discount) { double ret, k; int n, i, j; n = prices.length; ret = 0; k = 0.01 * (100 - discount); Arrays.sort(prices); for (i = 0; i < n; i++) if (i < n / 3) ret += k * prices[n - 1 - i]; else ret += prices[n - 1 - i]; return ret; }CompressedString Used as: Division One - Level Two: There is a straightforward recursive solution for this problem. If the first character of s is a digit and the second is the opening paranthesis, then find the corresponding closing paranthesis -- the answer is equal to the answer for the substring enclosed by the parantheses, multiplied by the value of the first digit, plus the answer for the remaining part of s (from the position immediately after the closing paranthesis until the end of the string). In the other case, the answer is equal to the answer for the same string without the first character plus 1. Java code follows: public int getLength(String s) { if (s.length() <= 1) return s.length(); if (s.charAt(1) != '(') return 1 + getLength(s.substring(1)); int left = 2, n = 2, stack = 1; for (int a = left; a < s.length(); a++) { if (s.charAt(a) == ')') stack--; if (s.charAt(a) == '(') stack++; if (stack == 0) { n = a; break; } } return (s.charAt(0)-'0')*getLength(s.substring(2,n))+getLength(s.substring(n+1)); }CoolNumbers Used as: Division One - Level Three: Suppose, we have a function f(x) that returns the number of cool numbers between 0 and x, inclusive. The answer for the problem is equal to f(upperBound) - f(lowerBound - 1). Function f(x) uses dynamic programming. Let's introduce a function doit(int step, int last, int len, int match, int done). This goes through the binary representation of x from left to right, constructing a number, and returns the number of the cool numbers that has a constructed prefix. Here step is the number of the remaining digits, last is a value of the previous digit, len is a number of the last consequtive equal digits, match indicates whether the constructed prefix is equal to the corresponding prefix of x, and done indicates whether the constructed prefix contains a group of three consecutive ones or zeroes (i.e. whether the constructing number is already cool). Java code follows: static int memo[][][][][] = new int[33][2][4][2][2]; static int s[] = new int[33]; static int n; public static int doit(int step, int last, int len, int match, int done) { int ret, i; if (len > 3) len = 3; if (len == 3) done = 1; if (step < 0) return done; if (memo[step][last][len][match][done] >= 0) return memo[step][last][len][match][done]; ret = 0; for (i = 0; i < 2; i++) if (match == 0 || i <= s[step]) { if (i == last) { if (match == 1 && i == s[step]) ret += doit(step - 1, i, len + 1, 1, done); else ret += doit(step - 1, i, len + 1, 0, done); } else { if (match == 1 && i == s[step]) ret += doit(step - 1, i, 1, 1, done); else ret += doit(step - 1, i, 1, 0, done); } } return memo[step][last][len][match][done] = ret; } public static int f(int x) { int ret, i, j, k, y, z; if (x < 0) return 0; ... // fill the array memo by -1 for (z = x, n = 0; z != 0; z >>= 1) s[n++] = z & 1; // s now contains a binary representation of x ret = doit(n - 2, s[n - 1], 1, 1, 0); // count all cool nubers with the same number of digits (in binary) as s for (i = n - 2; i > 0; i--) ret += doit(i - 1, 1, 1, 0, 0); // count all other cool numbers less than x return ret; } public static int count(int lowerBound, int upperBound) { return f(upperBound) - f(lowerBound - 1); } |
|