Wednesday, December 22, 2004 Match summary In Division 1, only four people solved the Medium and a mostly different four solved the Hard. ploh dominated as the only coder to submit all three problems. When all three of his programs passed system tests, ploh led secondplace pparys by almost 500 points. In Division 2, newcomer fluffy_ was also the only coder to solve all three problems, in an impressive debut just shy of the list of alltime top debuts. Mg9H, the only other coder to solve the Hard, took second.
The ProblemsInsideOutUsed as: Division Two  Level One:
This problem is a simplified form of my favorite "handwaving" argument. How do you swap the left and right sides of an array? You use three separate reversal steps, like this. [Hold your hands up with both thumbs pointing left. Your right thumb should be touching your left pinky. Now, rotate your left hand so your thumbs are together (Reversal #1). Then rotate your right hand so your thumb is pointing right (Reversal #2). Finally, rotate both hands as a single unit around the pivot point formed by your left thumb and your right pinky, until both thumbs are again pointing left (Reversal #3). Notice that your hands are now in their original orientations, but that they have swapped places.] For this problem, we needed to do the first two reversal steps, but not the third. In other words, the final answer is something like return reverse(line[0..n/21]) + reverse(line[n/2..n1]);where n is the length of the string. See csfalcon's and mukund's solutions for nice examples of this approach. Alternatively, we can do the whole thing with one reversal step if we preswap the left and right sides. return reverse(line[n/2..n1] + line[0..n/21]); Now, how do you reverse a string S? If it's not built into your language, you could do something like T = ""; for (i = 0; i < S.length; i++) T = S[i] + T; S = T;but repeated concatenations are slow. A faster method is lo = 0; hi = S.length; while lo < hi do swap(S[lo++], S[hi]); One further remark on the "handwaving" algorithm. Besides making a great demonstration, it really is a practical algorithm for swapping the two sides of an array. There are easier ways to do it when the two sides are of equal size, as they were in this problem, but when the two sides are of different sizes, the "handwaving" algorithm is the way to go. TwoTurtledovesUsed as: Division Two  Level Two: Used as: Division One  Level One:
This problem was easy to solve with two loops, one counting up the days and one counting down the types of presents within the day. int count = 0; for (int day = 1; ; day++) { for (int type = day; type > 0; type) { count += type; if (count >= n) return type; } }For example, Ryan has a nice implementation of this approach. These loops run quite fast, even for very large n, but you might have been scared off by the fact that n could range up to 1 billion. In that case, you probably tried to process all the presents for a single day with a formula instead of with a loop. How many presents do I give my true love on day D? This is just the sum from 1 to D, which, if you remember the famous story about Gauss, you'll recall is D*(D+1)/2. You could use this formula to quickly count up the days until you reach the last day, and only then count down the types of presents within the last day. int count = 0; int day = 1; while (count + day*(day+1)/2 < n) { count += day*(day+1)/2; day++; } for (int type = day; ; type) { count += type; if (count >= n) return type; }Again we have two loops, but this time they are not nested. See Larry's solution for a clean implementation of this approach. ColinMacLeod implemented a minor variation in which he computes the sum on the fly instead of using the formula. For a really impressive example of mathematical overkill, see jms137's solution. ParenReductionUsed as: Division Two  Level Three:
There were two parts to this problem: first parsing the original expression (most likely into a binary tree usually called an abstract syntax tree) and then "prettyprinting" the tree back into a string. Parsing was best done recursively. Because the original expression was fully parenthesized, finding the next operator at each step is a matter of counting parentheses. The recursive algorithm is if the string is a single letter then build a leaf node out of the single letter else strip off the opening and closing parentheses find the only operator not enclosed in parentheses parse the substring to the left of the operator parse the substring to the right of the operator build a tree node from the operator and the two subtrees built by the recursive calls Unparsing boils down to figuring out how each operator behaves when it is the left or right child of each other operator. For example, a '*' needs parentheses only if it is either the left child of a '^' or the right child of a '^' or '/'. You could build a 5by5by2 table of booleans describing whether or not parentheses are required in each possible configuration, or equivalently use a giant series of ifstatements to accomplish the same thing. A simpler approach uses the idea of precedence levels. The five operators have three different precedence levels. Addition and subtraction have precedence level 1, multiplication and division have precedence level 2, and exponentiation has precedence level 3. In addition, it will be convenient to allow 4 as an artificial precedence level. Now, when printing a particular expression, we will include a precedence level. Operators below that precedence level will require parentheses, operators at or above that precedence level will not. In pseudocode, this algorithm can be written as function show(expr, level) is if expr is a leaf node then return expr.letter else if expr.op == '^' then leftLevel = 4 rightLevel = 3 if expr.op == '*' then leftLevel = 2 rightLevel = 2 if expr.op == '/' then leftLevel = 2 rightLevel = 3 if expr.op == '+' then leftLevel = 1 rightLevel = 1 if expr.op == '' then leftLevel = 1 rightLevel = 2 left = show(expr.left, leftLevel) right = show(expr.right, rightLevel) p = precedence level of expr.op if p > level then return left + expr.op + right else return '(' + left + expr.op + right + ')'Notice how the associative operators (multiplication and addition) use the same precedence level for both recursive calls, while the right and leftassociative operators increase the precedence level for one of their recursive calls. The initial call to show uses precedence level 1 so that the overall expression is not surrounded by parentheses. Rationalization Used as: Division One  Level Two:
We have up to 110 possible numbers to tweak, and each can be increased by one, decreased by one, or left alone, so there are 3^110 possible combinations to consider. Obviously, this is far too many for a purely bruteforce solution. We can cut down on the search space by recognizing that we never want to decrease one of the desired alternative's scores or increase one of the other athernative's scores, so really there are only 3^10*2^100 possible combinations. Now, 3^10 is only about 60000, so it is feasible to bruteforce all possible combinations of weights, as long as we come up with a smarter way to handle the individual scores. The easiest way to generate all the weights is with recursion. function doWeights(i, numTweaks) is if i == weights.length then ...process the scores... else doWeights(i+1, numTweaks) if weights[i] < 9 then weights[i]++ doWeights(i+1,numTweaks+1) weights[i] if weights[i] > 1 then weights[i] doWeights(i+1,numTweaks+1) weights[i]++If you prefer iteration, you can loop from 0 to 3^W1, where W is the number of weights. Then consider the digits of each number in base 3. If the ith digit is D, then add D1 to the ith weight. Now, for each configuration of weights, we need to find the minimum number of scores that need to be tweaked. This can be done greedily. Consider a particular alternative's scores in the various categories. If we are going to tweak any of them, we might as well tweak the one with the largest weight first. If we want to tweak a second one, we might as well tweak the one with the second largest weight, and so on. Thus, by sorting the weights—or, rather, by sorting the indices of the weights—we can easily generate a table optimal[i][j] of the best score that can be achieved by alternative i using exactly j tweaks. One catch is that "optimal" for the desired alternative means as big as possible, and for all other alternatives means as small as possible. Given this table, we can loop through the possible numbers of tweaks to the desired alternative, and for each one loop through all the other alternatives to find the minimum number of tweaks to that alternative for the desired alternative to beat it. If we ever hit an alternative that can't be beat, then we can stop looking at the other alternatives. for (num1 = 0; num1 <= W; num1++) total = numTweaks + num1 for (i = 0; i < scores.length; i++) if i == desired then continue for (num2 = 0; num2 <= W; num2++) if optimal[desired][num1] > optimal[i][num2] then total += num2 if total > bestSoFar then continue outer loop else continue middle loop // desired can't beat alternative i continue outer loop bestSoFar = min(bestSoFar, total)ploh implemented essentially this algorithm. Dynamic programming can also be used to find the optimal scores for each alternative, as in evgeni's solution, but this is slower than the greedy approach. ArithSeqUsed as: Division One  Level Three:
I hope most people turned away from their keyboards and started scribbling on paper when they opened this problem, because solving it requires some insight into the structure of the set. Remember that the set was generated by the pattern keep 1, drop 1, keep 2, drop 2, keep 3, drop 3, etc. Where does block K (the block generated by "keep K") begin and end? To see where it begins, notice that it is preceded by 1+2+...+(K1) kept numbers and 1+2+...+(K1) dropped numbers. Again recalling the story about Gauss, we see that block K must begin at K*(K1)+1. Therefore it must end at K*(K1)+K = K*K. So an easy test to determine whether a number X is in the set is function inSet(X) is K = ceiling(sqrt(X)) return X > K*(K1)As an aside on the problemwriting process, I was mildly dismayed to realize that square roots of doubleprecision floating point numbers yielded enough precision to handle the numbers in this problem (up to about 670 billion). Oldtimers may remember that I was once famously burned by the combination of long integers and doubleprecision square roots, so I had certainly intended folks to work only with longs on this problem. Now, let M be the total size of the desired sequence, DELTA*(N1)+1. We know that the arithmetic sequence will fit in block M, which begins at M*(M1) + 1, so that value yields a good default answer. (Incidentally, this is the reason for the constraints. The default answer for the maximum inputs is 8410000002900000001, which is within a few percent of the maximum positive 64bit integer. In fact, however, the default answer will never be used when DELTA is much larger than N.) Assuming we start at 1 and search upwards, when can we be sure that no better answer than the default answer is possible? In other words, when should we stop looking and just return the default answer? As soon as the end point of the candidate sequence passes the last value in block DELTA, because then the sequence would have to cross a block of DELTA missing numbers, but the gap between numbers in the sequence is only DELTA1 wide. In fact, a slightly tighter analysis shows that the end point of the candidate sequence can't pass the first value of block DELTA. Ok, so this tells us when we can quit looking and just return the default value, but for large DELTA, this still only cuts the size of the search space down from about 10^20 to about 10^16—still far too large to search exhaustively. We need a way to step through the search space faster than one unit at a time. Suppose we are checking a particular candidate sequence and discover that one of the numbers in that sequence falls in between two blocks. Then we can skip ahead by the distance between that number and the start of the next block. The blocks we are dealing with can be quite large, so this can mean skipping ahead by a huge distance each step. In pseudocode, this algorithm might be written function minStart(n,delta) is skip = 1 length = delta*(n1)+1 limit = delta*(delta1)+1 // limit can be improved for (i = 1; i <= limit; i += skip) for (j = i + length  1; j >= i; j = delta) k = ceiling(sqrt(j)) if j <= k*(k1) then skip = k*(k1)+1  j break if j < i then // found a valid sequence return i return length*(length1)+1 // the default answerNote that the inner loop counts backwards instead of forwards. This is in the hope that numbers at the end of the sequence will generate bigger skips than numbers at the beginning of the sequence. See my solution in the practice room for a faster algorithm that doesn't use sqrt at all, but instead uses only integer arithmetic. 
