Thursday, September 11, 2008 Match summaryIn 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 ProblemsReversedSumUsed as: Division Two  Level One:
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. TemplateMatchingUsed as: Division Two  Level Two: Used as: Division One  Level One:
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++. TripleJumpUsed as: Division Two  Level Three:
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".
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:
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.
Used as: Division One  Level Three:
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 pq path: pACq, pADq, pBCq, pBDq. If we think about p and q as a realvalued 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 f_{1}..f_{4}. We need to find the maximum of min{f_{1}, f_{2}, f_{3}, f_{4}} 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 f_{1}  f_{2} = 0, f_{1}  f_{3} = 0, f_{1}  f_{4} = 0, f_{2}  f_{3} = 0, f_{2}  f_{4} = 0, f_{3}  f_{4} = 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: pACq = pBDq and pADq = pBCq. 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: pACqDBp and pADqCDp. 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. 
