Thursday, February 16, 2006 Match summary 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 ProblemsSpeedTyperUsed as: Division Two  Level One:
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; }Please note we replace division with multiplication to avoid floating point imprecision. Doing so when possible is a very useful habit. BrokenClock Used as: Division Two  Level Two: Used as: Division One  Level One:
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 errorprone and doesn't require any tricks, so you are safe choosing it. GalaxyTripUsed as: Division Two  Level Three:
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 FloydWarshall to compute the transitive closure of the graph, and a simple BFS to find connectivity components. SnailRaceUsed as: Division One  Level Two:
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. GalaxyExpeditionUsed as: Division One  Level Three:
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 nonoriented 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.
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.
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 kth bit in the number) makes the coding much shorter and easier. 
