Tuesday, May 17, 2005 Match summary Eryx won this match easily, with high scores on two of the problems. Almost 90 points behind, petr took second place, and got his target after only 6 matches, beating the record held by snewman of 8 matches. Round out the top 3 was Jan_Kuipers, helped by 25 points in the challenge phase. In division 2, zolom too first in his fourth match, while bramandia and kolo took second and third. The ProblemsComputationalComplexityUsed as: Division Two  Level One:
Implementing the given formula is straightforward, and can be done using builtin power functions, or by writing your own. Once you find the runtimes for each algorithm, you just need to find the minimum by iterating over them. A number of coders made the mistake of initializing a variable (which would contain the speed of the fastest algorithm) that was too small. Others cast the result to an integer or double, and lost the precision they would need. GeneratorsUsed as: Division Two  Level Two: Used as: Division One  Level One:
Despite the math terminology, this problem is really very straightforward. You can loop from 1 to p1, and check each number to see if it's a generator. Using the equation given in the notes, it's easy to generate the sequence, and then you just need to make sure that the sequence is equal to Z_{p}. There are a few ways to do this, but the most obvious is to just have a boolean array indicating which numbers have been generated in the sequence. After you generate p1 numbers, just make sure that all the integers from 1 to p1 have been generated. FastSpiderUsed as: Division Two  Level Three:
There were two different ways to do this. One way requires you to use calculus, while the other is a numerical approximation. For the calculus approach, you can think of how far the spider moves in a second, in proportion to the length of the rubber band. At second t, the length of the rubber band is 1+t*manSpeed feet. At this exact point (time t), the spider is moving at a rate of spiderSpeed/(1+t*manSpeed) percent of the total rubber band length per second. More precisely, the derivative with respect to t of the percent along the band of the spider's position is spiderSpeed/(1+t*manSpeed). Therefore, over some number of seconds, x, the percent of the band length that the spider has moved is Integral(spiderSpeed/(1+t*manSpeed),t) evaluated from 0 to x, or spiderSpeed*ln(1+manSpeed*t)/manSpeed. Since we want the spider to go all the way along the rubber band, we set this to 1, and solve for t: spiderSpeed*ln(1+manSpeed*t)/manSpeed = 1 ln(1+manSpeed*t) = manSpeed/spiderSpeed 1+manSpeed*t = exp(manSpeed/spiderSpeed) t = (exp(manSpeed/spiderSpeed)1)/manSpeedIf you calculus was rusty, there was another way. You could simply simulate the spider with a large number of very small steps, alternating between the man moving and the spider moving. Because of the constraints, it is possible to achieve enough precision with a solution like this to solve the problem. TopFive Used as: Division One  Level Two:
This problem obviously refers to the TopCoder challenges. In the first step, you should calculate the probability of beating each of the other people independently. You can do this by examining each of the 8 outcomes (2 outcomes for each of 3 problems) for each person. Then, you can use brute force to find all the possible ways to get 1st, 2nd, 3rd, 4th, or 5th. A simple way to do this is to recursively find all sets of 0, 1, 2, 3 and 4 people, representing the people who beat you. Then, for each of these sets, compute the probability that those people beat you, and that you beat everyone else. This is done by simply multiplying all the individual probabilities (of beating people or being beat by people) together. Add up the results from all sets, and return this result. TwoKingsUsed as: Division One  Level Three:
At first glance, the state space for this problem seems huge, as there are
10,000^{3} different board positions. However, there is a simple strategy to
capture a king in 4 moves. First, move the queen to the same row as king 1 (if
you can't do this, it means you can capture a king right off). The king will
then have to move to one of the two adjacent rows. Next, move the queen to the
same column as king 2. This will force the second king to move to one of the
adjacent columns. Now, you can move the queen diagonally one space in one of
the four directions to fork the kings, attacking them both, and on the next move
you can capture one of them. Therefore, if we haven't forked the kings
(including cases where they are lined up) or cornered one on the edge of the
board after 2 moves, we need not continue, as we already know an equal or better
way to do it. 
