Match Editorial

The Problems

Div-I
Value	300 points
Submission Rate	294/310 (94.84%)
Success Rate	264/294 (89.80%)
High Score	radeye for 293.51 points

Implementation
This is a straight-forward problem to solve, simply following the directions given. Java and C# users can use the startsWith method of their string class to see if the remaining letters correspond to a particular token. C++ users can use strncmp or the substr method to do the same. It's then a matter of picking the longest token that matches (if any) and adding it to a list. For Java and C# users, the toArray method of ArrayList is quite useful.

Mistakes seemed primarily to result from not following directions.

Div-I
Value	450 points
Submission Rate	249/310 (80.33%)
Success Rate	195/249 (78.31%)
High Score	reid for 443.58 points

Implementation
On the surface, this appears to be one of those difficult number theory problems. But in fact a naive solution using obvious methods is sufficient.

The first task is being able to find all relatively prime integers that are between 0 and N exclusive. Relatively prime can be alternatively defined as two numbers that have a greatest common divisor of 1. Thus one can use the well-known Euclidean algorithm to filter out the numbers that are relatively prime to N.

Next we need to find the order of each relatively prime number. The hint given in the problem statement regarding (a*b) mod N = (a mod N)*(b mod N) was really unnecessary, as N is extremely small, giving no risk of overflow. One can simply multiply an accumulator by the number that is relatively prime to N, then find its value modulo N, and repeat this until 1 is obtained.

Since this was a problem with a very small domain of possible inputs, it's reasonable to iterate through all possible inputs in one's testing. This way one can be sure that no strange answers are generated and no arithmetic errors occur.

Div-I
Value	900 points
Submission Rate	52/310 (16.78%)
Success Rate	13/52 (25.00%)
High Score	John Dethridge for 449.65 points

Implementation
The method of solving this problem is to iterate through all possible "interesting" values of t >= 0 (representing time). One could implement a fancy method of determining that both roaming nodes are moving away from all static nodes, thus concluding that distances will always increase from that time on, but that's unnecessary work and requires dealing with a bunch of special cases. It's easier to simply iterate through time up to some point where the two roaming nodes will necessarily have to be moving out of range of all static nodes. Since the nodes are required to move along an axis, we know that at most 20000 + range seconds need to pass before both nodes will have left the system. It is very reasonable to compute minimal distances between the two roaming nodes for 50000 different times.

So now all that is left is computing the minimal distance for two roaming nodes at a particular point in time. To do this, we iterate through all the possible combinations of endpoints that are in range of the two roaming nodes. We then just need to compute the minimal distance between those two endpoints in the static network.

Since this is a static network, we can precompute these distances before iterating over time. This is a simple application of an all-pairs-shortest-paths algorithm, such as Floyd's algorithm. The static nodes represent a graph, where there are edges between any pair of nodes that are within range of each other, with weight corresponding to Euclidean distance.