Wednesday, November 12, 2008 Match summaryThe coders in Division 1 were proposed three problems somehow related search or graphs. The easy was a DFS problem, solution for the medium required BFS, and the hard was a task on graph connectivity. Division 2 shared two of those problems, with a numbers manipulation as the easy. Newcomer decowboy won the Division 2 title, moving over 1900 rating points after his very first SRM. acsaga and oa12gb were about halfchallenge behind, significantly ahead of the crowd. In Division 1, ilyakor got his first SRM win, beating second finisher Petr by more than 50 points. Nobody except two winners solved the hard problem, with Rizvanov_de_xXx coming third thanks to numerous challenges. The ProblemsInverseFactoringUsed as: Division Two  Level One:
If you'll look at the list of all factors of some number N, you'll recognise that you can find there many pairs of numbers f1 and f2 such that f1 * f2 = N (no surprise here, if f1 is a factor of N, then N/f1 will also be a factor). Therefore, to find N we need to select two factors such that their product is N and multiply them. How to do that? The easiest way is to sort the array of factors, take the smallest and the biggest factors of N, and return their product. Proving that the product of those factors will be equal to N is simple: if (f1 * f2) == N and (a1 * a2) == N, and f1 < a1, then (a2 < f2). So, if f1 is the smallest factor of N (f1 < f for any factor f), then f2 will be the biggest factor. PiecesMoverUsed as: Division Two  Level Two: Used as: Division One  Level Two:
After solving an easy DFS problem, coders were proposed a much harder BFS problem (read this if "BFS" and "DFS" do not sound familiar to you). In general, every time you are asked to find a shortest sequence of moves to reach a certain goal, think of a shortest path algorithm through a graph. For this problem, building the corresponding graph is very simple: each vertex of a graph is represented by an unique configuration of pieces on the board, and two vertices are connected by a edge if and only if the corresponding configurations can be transformed one into another by one move. We are to find the shortest path from vertex A (corresponding to the starting configuration of the pieces) to any of the final vertices (where the pieces are at adjacent squares). To find this path, we'll use BFS algorithm, which is pretty well described in the turorial (see links earlier in this paragraph). Lets "time for vertex V" (Tv) be the length of the shortest path from the starting configuration to vertex V. So, the general structure of the algorithm is simple and is a standard for BFS:
public class PiecesMover { int N, ans; boolean[][] data; HashSetCrazyBot Used as: Division Two  Level Two: Used as: Division One  Level One:
This problem, quite hard with a bit higher constraint, was pretty bruteforcable with short paths. Since at each step we choose one of 4 possible directions, the total number of paths of length 14 is 4^14 = 2^28. This is a bit too much for a 2seconds limit, but we may significantly cut this number. For example, if the first two steps of a robot will be "EW", then the path is already nonsimple and we can stop checking further steps. This trick cuts the number of paths to a reasonable number, so the very simple DFS will run well in time: public class CrazyBot { int N; double e, w, s, n, good; boolean[][] visit; public double getProbability(int n1, int east, int west, int south, int north) { N = n1; good = 0; // This array stores all points visitied by robot visit = new boolean[3 * N + 5][3 * N + 5]; e = east / 100.; w = west / 100.; s = south / 100.; n = north / 100.; go(N + 2, N + 2, 0, 1.); return good; } void go(int x, int y, int step, double prob) { // If we stay at the point which was already visited, then we stop checking this path. if (visit[x][y]) return; // If we made N steps without visiting the same point twice, then we add the probability of this path to the answer. if (step >= N) { good += prob; return; } // Mark this point as visited and continue into each of 4 directions. visit[x][y] = true; go(x + 1, y, step + 1, prob * e); go(x  1, y, step + 1, prob * w); go(x, y + 1, step + 1, prob * n); go(x, y  1, step + 1, prob * s); // Unmark the point when we checked all paths. visit[x][y] = false; } }RoadsOfKingdom Used as: Division One  Level Three:
This problem has two solutions  one was intended for higher constraints and is discussed in forums, and the other one will be explained here. Rewording the problem statement, we are to find a probability that after the rain the remaining roads will form a tree connecting all existing vertices. Since the problem is quite hard, we want to dissect the problem into smaller problems, and maybe those smaller problems will be either solvable or similar to the original one. "V and W are connected" means "cities V and W will still be connected by a road after the heavy rain." Some other abbreviations to be used in this text:
Lets start from any vertex V from set S and see how it can be connected to other vertices if the graph is 'good' (i.e.  is a tree).
Obviously, V must be connected to at least one other vertex. If there is exactly one such vertex W, then we reduced the problem
to a smaller size: Lets now see what happens if V is connected to at least 2 cities  W1 and W2. Then we can split set (S  V) into subsets S1 and S2 (S2 = S  V  S1), such that every vertex from (S  V) belongs to exactly one subset and the following conditions are satisfied. If we remove roads VW1 and VW2 from the graph, then:
P(S) = P(S1) * P(S2) * Connected(V, {W1, W2}) * Disconnected(S1, S2) = P(S1) * P(S  V  S1) * Connected(V, {W1, W2}) * Disconnected(S1, S  V  S1) We can check all possible ways to split S into two subsets S1 and S2, recursively find the values P(S1) and P(S2), and compute the total answer.
Similarly, if vertex V is connected to exactly k distinct vertices W1, W2, W3, then set S split into 3 subsets S1, S2, S3
with properties similar to those mentioned above, and the answer will be:
If vertex V is connected to vertex W1, and S1 is the set of vertices which are connected to V through W1, then the answer for
the set S is The first version of the pseudocode for this formula may look as the following (prob[i][j] is the probability that cities i and j are connected by a road after the heavy rain): double Connected(Set S, vertex V, Set X) { double answer = 1; for (all vertices W in S) if (V is in X) answer *= prob[V][W]; else answer *= (1  prob[V][w]); return answer; } double Disconnected(Set S1, Set S2) { double answer = 0; for (all vertices W1 in S1) for (all vertices W2 in S2) answer *= (1  prob[W1][W2]); return answer; } double P(Set S) { if (S is empty or contains only 1 vertex) return 1; vertex V = any vertex from S double answer = 0; for (all nonempty subsets S1 from S not containing V) for (all vertices W1 in S1) answer += P(S1) * Connected(S1, V, {W1}) * P(S  S1) * Disconnected(S  S1  V, S1). return answer; }Of course, an implementation of this naive code will a) time out and b) count some possible tree more than once. For example, for an obvious input {"08", "80"} the algorithm will return 2  because we can pick each of two vertices as V and the other will be W1. To avoid problem b), we need to fix the way to select vertices V and W in method P(). The easiest way to do that is always pick only the vertex with the smallest index. Therefore, method P() changes to the following: double P(Set S) { if (S is empty or contains only 1 vertex) return 1; vertex V = vertex from S with the smallest index double answer = 0; vertex W1 = vertex from S with the smallest index (other than V). for (all nonempty subsets S1 from S not containing V and containing W1) answer += P(S1) * Connected(S1, V, {W1}) * P(S  S1) * Disconnected(S  S1  V, S1). return answer; } Now lets improve the speed of our method. It seems that we often check whether a vertex is connected to all vertices of some set S1 or not connected to any vertex of some set. Therefore, we can implement the following two methods: double connectedToAll(vertex V, set S) { double answer = 1; for (all vertices W in S) answer *= prob[W][V]; return answer; } double notConnectedToAny(vertex V, set S) { double answer = 1; for (all vertices W in S) answer *= (1  prob[W][V]); return answer; }and reuse them in our Connected() and Disconnected() methods. The final version of the solution will look as following (of course, the results of most our methods can be memoized in some arrays, to avoid computing the same value more than once): double connectedToAll(vertex V, set S) { double answer = 1; for (all vertices W in S) answer *= prob[W][V]; return answer; } double notConnectedToAny(vertex V, set S) { double answer = 1; for (all vertices W in S) answer *= (1  prob[W][V]); return answer; } double Connected(Set S, vertex V, Set X) { double answer = 1; return connectedToAll(V, X) * notConnectedToAny(V, S  X); } double Disconnected(Set S1, Set S2) { double answer = 0; for (all vertices W1 in S1) answer *= notConnectedToAny(W1, S2); return answer; } double P(Set S) { if (S is empty or contains only 1 vertex) return 1; vertex V = vertex from S with the smallest index double answer = 0; vertex W1 = vertex from S with the smallest index (other than V). for (all nonempty subsets S1 from S not containing V and containing W1) answer += P(S1) * Connected(S1, V, {W1}) * P(S  S1) * Disconnected(S  S1  V, S1). return answer; } 
