JOIN
 Match Editorial
SRM 417
Thursday, September 11, 2008

## Match summary

In the first division competitors faced a technical easy problem, a tricky hard, and a medium where they had to choose between two completely different approaches. janos enjoys his first match victory thanks to his good performance on all three problems. He was followed by microsoft and Zhukov_Dmitry. Victory in the second division went to damnerd.

# The Problems

ReversedSum
Used as: Division Two - Level One:
 Value 250 Submission Rate 795 / 866 (91.80%) Success Rate 716 / 795 (90.06%) High Score KnightOfTheSun for 249.27 points (1 mins 32 secs) Average Score 212.96 (for 716 correct submissions)

This problem is about how to implement the Rev(x) function. This can be done in many ways. The "classic" aporoach is illustrated in KnightOfTheSun's solution. Another approach is to convert integers to strings, reverse them, and parse the integers back. See rudolfking's C# solution for the reference.

TemplateMatching
Used as: Division Two - Level Two:
 Value 500 Submission Rate 234 / 866 (27.02%) Success Rate 141 / 234 (60.26%) High Score peterLiang for 420.35 points (12 mins 52 secs) Average Score 251.79 (for 141 correct submissions)
Used as: Division One - Level One:
 Value 250 Submission Rate 584 / 640 (91.25%) Success Rate 470 / 584 (80.48%) High Score arti_kz for 243.81 points (4 mins 33 secs) Average Score 174.44 (for 470 correct submissions)

This problem was a technical one. All you needed to do was described in the problem statement: iterate over all the substrings and select the best one. You also need to resolve ties carefully. See darnley's solution for clear implementation in Java and ACRush's soluton in C++.

TripleJump
Used as: Division Two - Level Three:
 Value 1000 Submission Rate 28 / 866 (3.23%) Success Rate 3 / 28 (10.71%) High Score damnerd for 436.60 points (48 mins 10 secs) Average Score 359.09 (for 3 correct submissions)

The first thing you need to understand clearly before solving this problem is the following fact. Consider two independent random variables X and Y, uniformly distributed over some range [A, B]. Then their sum can possess values in range [2A, 2B], but values from this range will come with different probabilities! To illustrate this fact consider throwing two coins: the probability to get two "heads" or two "tails" is 0.25 each, but you have a 50% chance to get one "head" and one "tail".
Now let's go back to the problem. First of all let's substract the length of our first jump from all opponent's results. This will reduce the problem to a "double jump", where the length of each of the two jumps is a random variable. The core part of the solution is implementing the following function: F(z) = probability that your two remaining jumps will have total length at least z. Those of you who are familiar with theory of probablity might now that such function F(z) is called a distribution function. In our problem z = x + y, where x and y are random values, uniformly distributed in range [lower, upper]. Let's illustrate this on the cartesian plane Oxy.

F(z) is proportional to the area of the red figure above the line x + y = z. Indeed, each point inside this figure has coordinates that in sum are greater than z. Some basic calculations allows us to find F(z) as:

Now, lets sort the opponents results in the descending order. In this case our chance to get the first plase will be F(opponents[0]). Chance to get second place F(opponents[1]) - F(opponents[0]), third: F(opponents[2]) - F(opponents[1]) and so on.

CubeNets
Used as: Division One - Level Two:
 Value 500 Submission Rate 240 / 640 (37.50%) Success Rate 130 / 240 (54.17%) High Score jbernadas for 443.34 points (10 mins 25 secs) Average Score 278.39 (for 130 correct submissions)

There are two different approaches for this problem. The first one is just to google for "cube net" and find out that there are only 11 distinct cube nets. After that you just need to compare the figure from the input with these eleven "canonical" cube nets carefully. This is still not a trivial coding task and many competitors, who selected this approach, failed it. See darnley's solution for the implementation details.
Another approach is to find any position with an '#' and "put" the cube there. After that start "rolling" the cube recursively while you have adjacent '#' cells. One each roll assign the the cell to the surface of the cube that touches it. At the end check if all the '#' cells had an assigned surface. See jbernadas's solution for clear implementation.

WalkingDistance
Used as: Division One - Level Three:
 Value 1000 Submission Rate 109 / 640 (17.03%) Success Rate 12 / 109 (11.01%) High Score kefir for 799.98 points (15 mins 0 secs) Average Score 553.99 (for 12 correct submissions)

Let's start from an example that illustrates that both two points where the maximal walking distance is achieved are not necessary be the vertices of the graph.

There are several approches for this problem. But in any case we need to calculate shortest distances among each pair of vertices, and to iterate through all pairs of edges. Now, when the two edges (let's call them AB and CD) are fixed lets find points p from AB and q from CD with the maximal possible walking distance between them. Basicly, there are four candidates for the shortest p-q path: p-A-C-q, p-A-D-q, p-B-C-q, p-B-D-q. If we think about p and q as a real-valued parameter in range [0, AB] and [0, CD] correspondingly, the length of the shortest path is the minimum of four linear function of arguments p and q. Let's denote them by f1..f4. We need to find the maximum of min{f1, f2, f3, f4} over all possible p and q. For those of you who are familiar with linear programming theory it might be obvious that to get the maximal length of the shortest path we need to check all intersection points of lines f1 - f2 = 0, f1 - f3 = 0, f1 - f4 = 0, f2 - f3 = 0, f2 - f4 = 0, f3 - f4 = 0, p = 0, p = AB, q = 0, q = CD.
For the rest of you I suggest simplier, and actually, more efficient, approach. It happens that the following pairs of paths are equal for the optimal values of p and q: p-A-C-q = p-B-D-q and p-A-D-q = p-B-C-q. This can be proved from the contrary: if this is not true we can always increase the length of the shortest path. In this case, the length of the shortest path can be found as a half of the minimum of the two following cycle lengths: p-A-C-q-D-B-p and p-A-D-q-C-D-p. See Im2Good's solution for clear implementation.
Minilek in his solution introduced another approach, that is based on two nested ternary searches to determine p and q.

By Pawa
TopCoder Member