Match Editorial

Division 1 coders faced a pretty balanced set of 3 completely different problems. Petr showed a tremendous performance, outplaying the second (misof) and third (andrewzta) finishers by almost 500 points. With his 15th SRM win, Petr shares with radeye the 4th place in career SRM wins. dmwright (16) and tomek (19) aren't far ahead, but catching up to SnapDragon (39) may take a while...

In Division 2, 13 coders were able to solve the hard. MMind and kappa took the top 2 spots, with newcomer neitsch at third, AJA and gootsa took fourth and fifth respectively. All these coders advance to Div 1, except AJA who will need to compete in Div 2 at least once more.

The Problems

Value	250
Submission Rate	293 / 308 (95.13%)
Success Rate	278 / 293 (94.88%)
High Score	Viali for 248.97 points (1 mins 50 secs)
Average Score	210.06 (for 278 correct submissions)

To solve this problem, we need to first compute the average time it takes Johny to type a letter. If times has N elements, then the total time needed to type all letters is times[N - 1] and the average is times[N - 1]/N. Now we just iterate through all letters and check whether typing this letter (times[i] - times[i - 1]) takes longer than average. The only exception is the first letter, time for each can be computed as just times[0]. Java code follows:

    public String lettersToPractice(String letters, int[] times) {
        String ans = "";
        int N = times.length;
        if (times[0] * N > times[N - 1]) ans += letters.charAt(0);
        for (int i = 1; i < N; i++) if ((times[i] - times[i - 1]) * N > times[N - 1]) ans += letters.charAt(i);
        return ans;
    }

Value	500
Submission Rate	256 / 308 (83.12%)
Success Rate	140 / 256 (54.69%)
High Score	jerschneid for 487.03 points (4 mins 39 secs)
Average Score	376.41 (for 140 correct submissions)

Value	250
Submission Rate	302 / 306 (98.69%)
Success Rate	218 / 302 (72.19%)
High Score	overwise for 247.56 points (2 mins 49 secs)
Average Score	222.62 (for 218 correct submissions)

Many coders were trapped by this problem, though it didn't require any special skills or algorithms. The hardest thing was to make sure you've chosen a correct approach. If you are not sure, sometimes its better to implement a bit longer but safer algorithm instead of trying to prove the short one.

The shortest was greedy algorithm. It can be proved that the optimal strategy uses the minimal possible hours button clicks (the proof is left to reader). Knowing the exact number of hours button clicks, we adjust minutes properly and find the exact number of minutes button clicks. See Petr's solution for a clean implementation.

If you were not sure about the greedy approach during the contest, the problem could be brute forced through all reasonable strategies. Even in a challenge haste one can easily see that neither button should be clicked more than, say, 1000 times. Therefore one can just iterate through all 1M cases, check for each case whether it fixes the clock and return the minimal number of clicks among all proper cases. This approach isn't error-prone and doesn't require any tricks, so you are safe choosing it.

Value	1000
Submission Rate	61 / 308 (19.81%)
Success Rate	13 / 61 (21.31%)
High Score	kappa for 715.40 points (19 mins 38 secs)
Average Score	527.69 (for 13 correct submissions)

Being able to dissect a problem into subproblems was essential for this task (see antimatter's article on this). So, this problem consists of several parts. First, we need to find which machines can be taken independently, and can not. As soon as we find all groups of machines which can be taken independently, we'll take powers of these groups and combine them to get the answer. Lets look at these parts in order.

The most important detail to solve the first part is to note that dependency relation is symmetrical. In other words, if machine A is dependent on machine B, then machine B is dependent on machine A. Therefore all machines can be represented as vertices of the graph, where two vertices are connected if and only if they represent machines which depend on each other. One can easily see that if machine A needs machine B to work, and B needs machine C, then machine A needs machine C too. Therefore, if vertices X1 and X2 are connected in our graph, then machines X1 and X2 can not be used apart. To solve first part of our problem, split the graph into connected components. For each connectivity component, we can either use all machines from it or don't use any of them, therefore for each component we store only the number of vertices in it.

Now lets continue with the second part of our problem. We have a set of numbers (powers of connectivity components) and we want to find all possible sums of its subsets. Regarding coding details, you can use Floyd-Warshall to compute the transitive closure of the graph, and a simple BFS to find connectivity components.

Value	500
Submission Rate	195 / 306 (63.73%)
Success Rate	165 / 195 (84.62%)
High Score	laibo for 473.01 points (6 mins 51 secs)
Average Score	285.83 (for 165 correct submissions)

First, you need to note that if George is slower than a snail, the answer will be (distance - 1) / snailSpeed. Therefore, we can concentrate on cases when George is faster than a snail.

The easiest way to solve the problem is a classical binary search, with the distance George carries each of snails as the parameter (we can binary search over the time George spends carrying each snail as well). At each step of the binary search, one can simulate the whole race, storing and changing the time spend and George's position. The optimal value is reached if George drops the last shail exactly 1 meter from the finish. If he drops it earlier, we increase the time George carries each snail, and vice versa.

Instead of simulating the process each time, we can find the place where George drops the last snail in O(1) time. If George carries each snail for d meters, it takes him d / georgeSpeed to do this. Snails will have enough time to cover d1 = d * snailSpeed/ georgeSpeed. Next, George and snails will move one to each other, covering (d - d1) with the speed of (georgeSpeed + snailSpeed). Playing with this formulas a bit gives you that it takes George t0 = (2 * d) / (georgeSpeed + snailSpeed) hours to carry a snail and return for the next one. George will spend this time for each of the snails except for the last one. Therefore, the total time snails will travel is equal to T = (snails - 1) * t0 + (d / georgeSpeed), and the distance they'll pass is equal to T * snailSpeed. If this is smaller than distance - 1, we increase d, otherwise we decrease it. See andrewzta's solution for a clear implementation of this approach.

If this optimization isn't enough for you, you can avoid binary search at all, solving the last equation mathematically. (see Petr's solution). On the other hand, during the challenge its really important to correctly estimate your skills and abilities. If you think coding the "slow" binary search will take you less time than looking for the formula, it may be better to go with one of the first approaches.

Value	1100
Submission Rate	31 / 306 (10.13%)
Success Rate	6 / 31 (19.35%)
High Score	Petr for 871.08 points (15 mins 26 secs)
Average Score	548.58 (for 6 correct submissions)

We can reword the problem in the therms of graph theory, building a graph of dependencies. Each machines becomes a node of the graph, and, if machine A depends on machine B, we add a vertex from A to B. First of all, the dependency relationship is transitive. That is, if machine A depends on machine B, and machine B depends on machine C, then machine A also depends on machine C (because, if we won't take C, we won't be able to take B and, therefore, A). To use this property we build the transitive closure on the graph (further in this text, saying "dependent" will mean transitive dependency).

Now, like in the D2 hard problem, we need to group together machines which can not be used one without another. In D2 hard problem we had a non-oriented graph and needed to find connectivity components. In this problem, the graph is oriented. Machines A and B cannot be used one without another if and only if there is a path from A to B and from B to A. In other words, if A and B are in the same strongly connected component of the graph. Splitting the graph into strongly connected components is a classical problem, and low constraints for this problem allow you to choose from a number of algorithms.

As soon as we split the graph into strongly connected components, we find the component which isn't dependent on any other component (prooving that at least one such component always exists is left to the reader). Having this component found, we can split all vertices of the graph into 3 subsets: C, D and N. C will contain all vertices from the selected component, D contains all vertices which are dependent on vertices from C, and N will contain all vertices which are not dependent on any vertice C (neither vertice from C can not depend on any vertices outside C by definition). Next step will be proving that sets N and D are independent from each other (so, a machine from N can not depend on machine from D and vice versa).

First, all machines in D depend on machines from C. If machine A from N depends on machine B from D, then, because of the transitivity, machine A must depend on any machine from C. But all machines from N are not dependent on any machine from C, therefore we are in conradiction.
Second, let machine A from D depend on machine B from N. But machine A from D also depends on any machine c1 from C. According to the problem statement, "If a machine A depends on machines B and C, then B is dependent on C, C is dependent on B, or both B and C depend on each other.". Therefore, machine c1 depends on B or B depends on c1. Anyway, either of these cases contradicts the definition of set N. Our assumption is proved, so sets N and D are independent from each other.

Having that proved, we run the algo recursively on sets N and D, getting sets S_N and S_D as answers. To solve the problem for the whole set, we need to consider three following cases.
In the first case, we don't take any machine from C. Therefore, we can't take any machine from D too, so each number from S_N will be represented in the answer.
In the second case, we don't take any machines from N, but take all machines from C. Here, for any s1 from S_D, the answer will contain (s1 + |C|), where |C| stands for the number of machines in C.
In the third case, we take all machines from C and may take some machines from N. Then, for any s1 from S_D and s2 from S_N, (s1 + s2 + |C|) will be in the answer.
The answer for the whole problem will be the set containing all numbers which can be received in at least one of the cases mentioned above.

As an implementation note, representing the set of all possible answers as a long number (with the ability to take k machines represented as the k-th bit in the number) makes the coding much shorter and easier.