JOIN
 Match Editorial
SRM 243
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 Problems

ComputationalComplexity
Used as: Division Two - Level One:
 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.

Generators
Used as: Division Two - Level Two:
 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)
Used as: Division One - Level One:
 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 Zp. 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.

FastSpider
Used as: Division Two - Level Three:
 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
If 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:
 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.

TwoKings
Used as: Division One - Level Three:
 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,0003 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.

By lbackstrom
TopCoder Member