|
Match Editorial |
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 second-place 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 all-time top debuts. Mg9H, the only other coder to solve the Hard, took second.
The Problems
InsideOut
Used as: Division Two - Level One:
Value 250 Submission Rate 190 / 198 (95.96%) Success Rate 187 / 190 (98.42%) High Score Sartak for 248.27 points (2 mins 22 secs) Average Score 217.74 (for 187 correct submissions)
This problem is a simplified form of my favorite "hand-waving" 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/2-1]) + reverse(line[n/2..n-1]);
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
pre-swap the left and right sides.
return reverse(line[n/2..n-1] + line[0..n/2-1]);
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 "hand-waving" 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 "hand-waving" algorithm is the way to go.
TwoTurtledoves
Used as: Division Two - Level Two:
Used as: Division One - Level One:
Value 500 Submission Rate 156 / 198 (78.79%) Success Rate 127 / 156 (81.41%) High Score ahri for 491.48 points (3 mins 45 secs) Average Score 352.30 (for 127 correct submissions)
Value 250 Submission Rate 167 / 168 (99.40%) Success Rate 155 / 167 (92.81%) High Score jshute for 249.06 points (1 mins 44 secs) Average Score 207.42 (for 155 correct submissions)
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.
ParenReduction
Used as: Division Two - Level Three:
Value 1100 Submission Rate 10 / 198 (5.05%) Success Rate 2 / 10 (20.00%) High Score Mg9H for 581.82 points (34 mins 1 secs) Average Score 516.22 (for 2 correct submissions)
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 "pretty-printing" 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 5-by-5-by-2 table of booleans describing whether or not parentheses are required in each possible configuration, or equivalently use a giant series of if-statements 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 left-associative 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:
Value 600 Submission Rate 24 / 168 (14.29%) Success Rate 4 / 24 (16.67%) High Score Vedensky for 261.96 points (48 mins 10 secs) Average Score 244.36 (for 4 correct submissions)
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 brute-force 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 brute-force 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^W-1, where W is the
number of weights. Then consider the digits of each number in base 3.
If the i-th digit is D, then add D-1 to the i-th 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.
ArithSeq
Used as: Division One - Level Three:
Value 900 Submission Rate 10 / 168 (5.95%) Success Rate 4 / 10 (40.00%) High Score ploh for 683.33 points (17 mins 10 secs) Average Score 490.82 (for 4 correct submissions)
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+...+(K-1) kept numbers and 1+2+...+(K-1) dropped numbers. Again recalling the story about Gauss, we see that block K must begin at K*(K-1)+1. Therefore it must end at K*(K-1)+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*(K-1)
As an aside on the problem-writing process, I was mildly dismayed to
realize that square roots of double-precision floating point numbers
yielded enough precision to handle the numbers in this problem (up to
about 670 billion). Old-timers may remember that I was once famously
burned by the
combination of long integers and double-precision 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*(N-1)+1. We know that the arithmetic sequence will fit in block M, which begins at M*(M-1) + 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 64-bit 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 DELTA-1 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*(n-1)+1
limit = delta*(delta-1)+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*(k-1) then
skip = k*(k-1)+1 - j
break
if j < i then // found a valid sequence
return i
return length*(length-1)+1 // the default answer
Note 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.
