Match Editorial

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 Problems

Value	250
Submission Rate	175 / 207 (84.54%)
Success Rate	100 / 175 (57.14%)
High Score	Qool for 245.14 points (4 mins 0 secs)
Average Score	182.08 (for 100 correct submissions)

Implementing the given formula is straightforward, and can be done using built-in 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.

Value	500
Submission Rate	100 / 207 (48.31%)
Success Rate	63 / 100 (63.00%)
High Score	nickel for 487.80 points (4 mins 30 secs)
Average Score	339.42 (for 63 correct submissions)

Value	250
Submission Rate	189 / 199 (94.97%)
Success Rate	177 / 189 (93.65%)
High Score	Eryx for 249.23 points (1 mins 35 secs)
Average Score	217.09 (for 177 correct submissions)

Despite the math terminology, this problem is really very straightforward. You can loop from 1 to p-1, 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 p-1 numbers, just make sure that all the integers from 1 to p-1 have been generated.

Value	1000
Submission Rate	20 / 207 (9.66%)
Success Rate	10 / 20 (50.00%)
High Score	zolom for 909.00 points (9 mins 10 secs)
Average Score	589.74 (for 10 correct submissions)

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)/manSpeed

Value	500
Submission Rate	114 / 199 (57.29%)
Success Rate	84 / 114 (73.68%)
High Score	radeye for 472.97 points (6 mins 52 secs)
Average Score	301.18 (for 84 correct submissions)

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.

Value	1000
Submission Rate	22 / 199 (11.06%)
Success Rate	7 / 22 (31.82%)
High Score	Eryx for 641.33 points (24 mins 19 secs)
Average Score	505.08 (for 7 correct submissions)

At first glance, the state space for this problem seems huge, as there are 10,000³ 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.

This allows us to write a brute force solution that will run in time. We know that the answer is at most 4, so we are only interested in cases where the answer is 3 or less. If we haven't forked the kings or cornered one of them after 2 moves, then we won't be able to capture a king on the third. Each time we move the queen, there are at most 400 positions it can end up with. Moving it twice gives 400*400 possibilities. One of the kings moves once in between, for a maximum of 400*16*400 = 2,560,000 possibilities, each of which can be evaluated quickly to determine if a king is cornered, or if they are forked.