Member Search 
Tuesday, September 23, 2003 Match summary SnapDragon won again, surprising to no one, but it was by no means a sure thing. SnapDragon finished all three problems first, but a few minutes later WishingBone snuck into the lead with an exceptionally fast time on the Hard. In the challenge phase, SnapDragon spotted a flaw in a competitor's code, but wleite beat him to the challenge by five seconds, denying SnapDragon 50 points that would have propelled him into first place. It looked like WishingBone would eke out the victory until his Hard problem timed out during system tests. Division 1 also witnessed the end of an amazing streak by Tomek, who had until now submitted all three problems in every challenge he had entered. In Division 2, there were lots of high scores after the coding phase, but challenges and system tests claimed all but two of the submitted Hard problems. Newcomer moggy won in his debut, with vavadera close behind. The ProblemsBritishCoinsUsed as: Division Two  Level One:
There are 12 pennies in a shilling and 20 shillings in a pound, so there are 12*20 = 240 pennies in a pound. One simple way to convert pennies into the larger denominations is to use two loops, one to convert pennies to pounds and one to convert the remaining pennies to shillings. int pounds = 0, shillings = 0; while (pence >= 240) { pounds++; pence = 240; } while (pence >= 12) { shillings++; pence = 12; } return new int[]{ pounds, shillings, pence };We can accomplish the same thing without any loops by using integer division and mod. int pounds = pence / 240; pence = pence % 240; int shillings = pence / 12; pence = pence % 12; return new int[]{ pounds, shillings, pence };Alternatively, we can write all the math in a single line as return new int[]{ pence/240, (pence%240)/12, pence%12 };ParallelSpeedup Used as: Division Two  Level Two: Used as: Division One  Level One:
Assume that there are p processors. Then there are p*(p1)/2 pairs of processors, so the communications between the various pairs take a total of overhead*p*(p1)/2 milliseconds. If the tasks can be distributed evenly among the processors, then every processor gets k/p tasks. Otherwise, some processors get one extra task. Therefore the total time required is either k/p + overhead*p*(p1)/2 (if p divides evenly into k)or 1+k/p + overhead*p*(p1)/2 (otherwise)We can combine these two cases into a single formula by guaranteeing that the division k/p rounds up instead of down, as in (k+p1)/p + overhead*p*(p1)/2 To find the optimal number of processors, we loop through different values of p, keeping track of which value yields the fastest running time. It makes sense to start at 1 and count upwards, but when can we stop? Clearly, we will never use more than k processors, so one simple strategy is to loop from 1 to k. However, as k gets large, the calculation of p*(p1)/2 starts to overflow 32bit integers, so we would have to be careful to use 64bit integers. A more efficient alternative that works with 32bit integers is to stop as soon as the communications overhead exceeds k. For example, if we have 1000000 tasks, we will never choose a number of tasks where the communications overhead is more than 1000000 milliseconds. ZorbaTHut used a variation of this reasoning to place an upper limit of 1000 on the loop. An even more efficient alternative depends on the fact that the curve of running times versus number of processors is concave. In other words, it slopes downward until it reaches the minimum, and then slopes upward forever. Therefore, we can exit the loop as soon as the running time in one iteration is greater than the running time in the previous iteration. See, for example, Yarin's and ChristopherH's solutions. ShortPalindromesUsed as: Division Two  Level Three:
A key observation is that, to make the shortest possible palindrome out of base, you should never add letters to both the front and back of the string. If you were to do so, then you could make an even shorter palindrome by removing the first and last characters that you added. Therefore, the shortest palindrome that you can make out of base must either start with the first letter of base or end with the last letter of base (or both, if the first and last letters of base are the same). It is easy to turn this observation into a recursive algorithm: shortest(base) if base is already a palindrome then return base if base has the form A...A then return A + shortest(...) + A if base has the form A...B then return min(A + shortest(...B) + A, B + shortest(A...) + B)where min chooses the shorter of the two strings, or the lexicographically earliest if the strings have the same length. Unfortunately, a naive implementation of this algorithm might take exponential time, because a call on a string of size n can result in two calls on strings of size n1. Such an implementation would be likely to time out on strings of size 25. The second key observation is to notice that the above algorithm can end up calling shortest multiple times on the same substring, but that it never calls shortest on a string that is not a substring of the original base. The first property suggests that memoization might be a good idea, whereas the second property hints at dynamic programming. Either will work. To apply memoization, we modify shortest to remember which strings it has already been called on, and the answer for each. Then shortest begins by checking whether it has seen the current argument before. If so, it looks up the answer in a table. Otherwise, it computes the answer as above, but makes the recursive calls to the new, memoizing version of shortest. Once it is done, it saves the new answer in the table. To apply dynamic programming, we make a table of all the possible substrings of base. Then we process the entries of the table from shortest to longest. For each entry, we compute the shortest palindrome of that entry using the above rules, except that we replace the recursive calls with lookups in the table. See newcomer moggy's solution for a nice example of this approach. ContinuedFractionsUsed as: Division One  Level Two:
If you are math phobic, this problem probably gave you a severe case of the heebie jeebies. Even if you are comfortable with math, you may have been uncomfortable with this problem because it was deliberately written to test a slightly different skill from most TopCoder problems. Usually, challenge problems ask you either to come up with an algorithm from scratch or to use an algorithm that is clearly specified. This problem asked you to use a particular algorithm, but did not specify how that algorithm works. Intead, you were asked to generalize the algorithm from some sample calculations, which is something that happens frequently in real life. The algorithm begins by finding the integer part of the square root, which is easily done by a loop: int root = 0; while (root*root <= n) root++; root;root becomes the first element of the answer. The remainder is the fraction (sqrt(n)root)/1. We next begin a loop in which we process remainders of the form (sqrt(n)d)/m until we get back to (sqrt(n)root)/1. At each stage, we must convert the fraction (sqrt(n)d)/m into the form 1  q + (sqrt(n)d')/m'where q is a positive integer and the remainder (sqrt(n)d')/m' is between 0 and 1. The sample calculations went through the following steps: sqrt(n)d 1 1  =  =  m m m sqrt(n)+d   *  sqrt(n)d sqrt(n)d sqrt(n)+d 1 1 =  =  m * (sqrt(n)+d) sqrt(n)+d   n  d*d (nd*d)/mAt this point, we can simplify (nd*d)/m to get m'. There is no obvious reason to expect that nd*d will always be divisible by m, except that the problem statement implies that this will be the case. Next, we need to massage (sqrt(n)+d)/m' into the form q + (sqrt(n)d')/m', where q is an integer and (sqrt(n)d')/m' is between 0 and 1. This can be accomplished by setting q = (root+d)/m' and d' = q*m'  d. Altogether, then, our main loop looks like repeat m' = (n  d*d) / m q = (root + d) / m' d' = q*m'  d add q to output list d = d' m = m' until d == root and m == 1 An interesting fact about these periodic continued fractions is that the last element is always twice the first element. Therefore an alternative test for the ending condition is repeat .... until q == 2*root An even more intriguing fact about these periodic continue fractions, albeit one that is ultimately useless for the problem, is that, if you remove the first and last elements from the periodic continued fraction, then the remaining elements form a palindrome. For example, the periodic continued fraction for the square root of 158 is { 12, 1, 1, 3, 12, 3, 1, 1, 24 }The last element (24) is twice the first element (12), and the remaining elements (1, 1, 3, 12, 3, 1, 1) form a palindrome. Scheduling Used as: Division One  Level Three:
This problem looks scary at first, but the constraints keep it reasonable. What at first seems like it will require some heavy duty graph theory in the end requires nothing fancier than memoization, a staple of Division 1 Hard problems. We define a recursive function solve(tasks,cur,delay)that computes the minimum time needed to complete the set of tasks, assuming that the task cur is currently executing and that it has delay units of time to go. If no tasks are executing, then cur will be 1 and delay will be 0. The initial call will be to solve(allPossibleTasks,1,0). There are three main cases:
In pseudocode, solve is solve(tasks,cur,delay) if tasks is empty then return delay best = 999999999 for each t in tasks if t is eligible to run then if time[t] > delay then total = delay + solve(tasks{t},t,time[t]delay) else total = time[t] + solve(tasks{t},cur,delaytime[t]) best = min(best,total) if cur != 1 then total = delay + solve(tasks,1,0) best = min(best,total) return best Unfortunately, this algorithm is too slow as written because it tries the tasks in every possible order. There are a maximum of 12 tasks, but there are trillions of ways to order those 12 tasks. Notice, however, that we make many calls to solve with the same arguments. For example, suppose tasks 14 are all eligible to start immediately and all run in the same amount of time. Then we will try running 1&2 together followed by 3&4, 1&3 together followed by 2&4, and so on. Each of these patterns will eventually make a call to solve({5,...,12},1,0). We can save time by caching the value of solve({5,...,12},1,0) in a table the first time it is called, and looking it up each subsequent time instead of recomputing it. This technique is called memoization. We modify solve to check the table at the beginning and save the minimum time in the table at the end. The lines marked with stars are new but the rest of solve is unchanged. solve(tasks,cur,delay) if tasks is empty then return delay * combine tasks, cur, and delay into a single key * lookup that key in a table * if it's there, grab its associated value and return it compute best as in the previous version * save key and best in the table return best One final issue is how to represent the set of remaining tasks (or, alternatively, the set of completed tasks). Most people used bitmasks, but this was not crucial. 
