Saturday, June 14, 2008 Match summaryPetr's match appeared to be much easier than his previous matches  a whopping total of 3 coders solved the hard problem in Division 1. LayCurse won the round, with rpeng and tos rounding the top 3. In Division 2, newcomer cryinlaugh destroyed the opponents, winning by 300+ points. WSM and yappy were next 2 finishers, with yappy and Hanaban finishing a halfstep ahead of a very close group. The ProblemsFallingFactorialPowerUsed as: Division Two  Level One:
For this problem, the solution was just an implementation of the described algorithm: check whether k is positive and apply the corresponding operation: public double compute (int n, int k) { double res = 1; if (k >= 0) for (int i = 0; i < k; i++) res *= n  i; else for (int i = 0; i < k; i++) res /= n + i + 1; return res; }RelativePath Used as: Division Two  Level Two: Used as: Division One  Level One:
The shortest relative path from current directory to a file can be built using the following algorithm. First, we need to find a directory, which is a common parent of both current directory and file, and is the furthest from root among all such directories. To find that, we will split boths paths using '/' as the delimiter. Then, we start from the first element for both paths and discard them until they become different: public String makeRelative(String path, String currentDir) { String[] p = path.split("/"); String[] s = currentDir.split("/"); int n1 = 0; while (n1 < p.length && n1 < s.length && p[n1].equals(s[n1])) n1++; ...The best path will be moving level above until we reached that directory, and then go down until we find the file: ... int n2 = n1; String ans = ""; while (n2 < s.length) if (s[n2++].length() > 0) ans += "../"; while (n1 < p.length) if (p[n1++].length() > 0) ans += p[n1  1] + "/"; return ans.substring(0, ans.length()  1); } Checking if the corresponding element is nonempty is necessary because of a specific behavior of String.split() method (remove that check and try this solution against input with currentDir = "/"). IdealStringUsed as: Division Two  Level Three:
For the purposes of this editorial, "ideal string" will mean "ideal string of length L". A string P is good if there is an ideal string S, such that P is a prefix of S. If there is not such ideal string S, string P is bad. Like in many other problems asking for a lexicographically smallest string or array, the solution for this one uses greedy approach. We will select characters from left to right one by one, checking on each step whether we'll be able to construct the string of necessary length. To make sure we are using each letter proper number of times, we'll counters for all letters used. Taking into account that it never helps to use B before A, we will add letters to the answer in the alphabetical order: public String construct(int L) { String ans = ""; int nxt = 0; // the next letter which will be introduced. // 0 corresponds to 'A', 1  to 'B', and so on int[] have = new int[26]; // The ith element of have is equal to the number of times the // ith letter must be used until the end of the string. while (ans.length() < L) { boolean ok = false; // we still haven't found a way to construct an ideal string for (int i = 0; i < nxt; i++) // If it is possible to add a previously used letter to the answer // and construct an ideal string, we'll do that if (ok = (have[i] > 0 && CanConstruct(unknown params)) { have[i]; ans += (char)('A' + i); break; } if (ok) continue; // Now, we will try to add a new letter to the answer ans += (char)('A' + nxt++); // If we still can not construct a valid string, // then it is not possible at all. if (!can(ans.length(), CanConstruct(unknown params))) return ""; } return ans; } The most difficult part of the solution is method CanConstruct(), which is to determine whether the current prefix (ans in our code) is good. The easiest way of implementing it is the following: try all letters from 'A' to 'Z', throw out the letters which already be used a proper amount of times (if a letter 'C' first appeared on the second position, and it was already used 2 times, then we can not use it anymore), append remaining letters to the current prefix ans. If at least one of those new prefixes is good, then prefix ans is also good. This looks like a nice Dynamic Programming solution, but there is an issue  there are too many prefixes to represent each of them as a state of a DP program. Luckily, we can notice that prefix "ABCDBCD" is good if and only if prefix "ABCDDCB" is also good (because the order of the last 3 letters doesn't really matter in terms of "goodness" of a prefix). We'll try to unite prefixes into groups, with each groups representing prefixes which all either all good or all bad, and run a DP solution which state will be a group of prefixes, instead of a single prefix. And to unite prefixes in groups, we need to find which properties of a prefix matter in terms of goodness, and which are not. The most obvious meaningful property of a prefix is its length  if we'll need to append a 'new' letter L to the prefix, the length of the prefix will determine the total number of occurences of letter L. Other meaningful params are: the number of different letters used and the number of times each of those letters appeared in the prefix. Fortunately, since the maximal input length is small (100), so the total number of letters used does not matter  if we run out of letters, we will definitely need a much longer string. So we are left with 2 params  the length of a prefix (an integer), and the number of times we'll need to use letters which are already in the word (an array of ints). This is still way too many states, but we can notice that arrays {0, 1, 2} and {0, 2, 1} are not really different  for example, prefix "ABC" can be extended to multiple ideal stringū of length 6 ("ABCBCC", "ABCCCB" and "ABCCBC"). In other words, the parameter which determines if a prefix is good is the grand total number of "nonused" occurences of already present letters (3 for "ABC", 1 for "ABCBC"). Now we cut the space enough  we know that each prefix is good or bad depending on its length (an integer not greater than 100) and the total number of nonused appearences of the used letters (ditto, because the prefix with more than 100 nonused appearences definitely can NOT be extended to an ideal string of length less than 100). The implementation of the DP is quite classical: boolean canConstruct(int len, int left) { if (left < 0) // invalid input return false; if (len == L) // if we a prefix is of necessary length, then we don't need any more letters return left == 0; if (left + len > L) // is already too long return false; if (memo[len][left] != 1) // if we already found the answer for this state return memo[len][left] == 1; // can construct an ideal string using a 'new' letter if ((canConstruct(len + 1, left + len))  // or can construct an ideal string using an 'old' letter (left > 0 && canConstruct(len + 1, left  1))) { memo[len][left] = 1; return true; } memo[len][left] = 0; return false; } Using all the information we've found about ideal strings, we can make our solution much prettier: public class IdealString { int L; int[][] memo; public String construct(int L) { this.L = L; String ans = ""; int nxt = 0; Queue<Character> q = new LinkedList(); memo = new int[L + 1][L + 1]; while (ans.length() < L) { if (can(ans.length() + 1, q.size()  1)) { ans += q.poll(); continue; } char c = (char)('A' + nxt++); for (int i = 0; i < ans.length(); i++) q.add(c); ans += c; if (!can(ans.length(), q.size())) return ""; } return ans; } boolean can(int len, int left) { if (left < 0) return false; if (len == L) return left == 0; if (left + len > L) return false; if (memo[len][left] != 0) return memo[len][left] == 1; if ((can(len + 1, left + len))  (left > 0 && can(len + 1, left  1))) { memo[len][left] = 1; return true; } memo[len][left] = 2; return false; } }AllCycleLengths Used as: Division One  Level Two:
The major part of this problem is to estimate (or to believe) that the answer will not be very long (our forums already have the proof for that). Once you have that, you iterate through all vertices and for each vertex i:
Having that done for all vertices, we merge all output sequences to one sequence, which has '1' as the ith character if at least one of the initial sequences had '1' as the ith character. Now we need to find the shortest representation of this sequence. This task also becomes easy as soon as we remember that the length of the period can not be longer than 50  check all possible start positions of the period X, and for all L between 1 and 50 we check whether we can represent the answer as the prefix of length X + period of length L starting at position X. We iterate for X from 0 to infinity and for L from 1 to 50, and return the first answer we'll get. ReasonableOddsUsed as: Division One  Level Three:
Let x be the unknown skill of the first team, and y be the skill of the second team. Note that, given x and y, it's not hard to calculate the probabilities of winning for each of the teams and the probability of a draw. For example, to calculate the probability of winning for the first team we can iterate through all possible outcomes A:B, where 0 ≤ B < A ≤ k, and sum the values x^{A} * (1  x)^{k  A} * C(k, A) * y^{B} * (1  y)^{k  B} * C(k, B). Each such value is the probability of the outcome A:B. To clarify this, note that x^{A} * (1  x)^{k  A} gives us the probability for the first team to score exactly in given A shots, and the binomial coefficient C(k, A) gives the number of ways to choose this A shots among all k shots (if you are not familiar with binomial coefficients, please check this tutorial). If we denote the probability of winning for the first team as F(x, y) and the probability of winning for the second team as G(x, y), then we'll need to check whether the following system of equations have a solution: F(x, y) = p1 G(x, y) = p2 The problem reduces to choosing some searching method in order to solve this system of equations. As it appears, the functions F(x, y) and G(x, y) have a number of special properties which allow to use different search algorithms to solve this problem. Here's one such algorithm: set x = 0, y = 0 repeat many times: find x' such that F(x', y) = p1 and set x = x' find y' such that G(x, y') = p2 and set y = y' This algorithm is based on the following property: if F(x1, y1) = F(x2, y2), then x1 ≤ x2 if and only if y1 ≤ y2. The proof is very intuitive. If two teams had skills x1 and y1, and the skill of the first team increased to x2, then the skill of the second team also should be increased in order to maintain the same winning probability for the first team. Similarly, if the skill level of the second team increased to y2, then the skill of the first team also needs to increased. Obviously, the same property holds for the function G. Now, suppose that our system has a solution x^{*}, y^{*}. Using induction, we can show that at any moment in our algorithm x ≤ x^{*} and y ≤ y^{*}. Both inequalities hold at the beginning. The inequality y ≤ y* holds, when we change x to x'. As F(x', y) = F(x*, y*) = p1, there should be x' ≤ x^{*}. Similarly, the inequality x ≤ x* holds, when we change y to y'. As G(x, y') = p2, there should be y' ≤ y^{*}. Another useful fact that can also be proven by induction is that we never decrease the values of x and y during this algorithm. At the beginning of the cycle, F(x, y) ≤ p1 and G(x, y) ≤ p2. We therefore need to increase x to make F(x, y) = p1. Increasing of x causes decreasing of G(x, y), therefore we will then need to increase y to obtain G(x, y) = p2. Increasing of y causes decreasing of F(x, y) and we will need again to increase x, and so on. So, as x and y always increase and at every time x ≤ x^{*}, y ≤ y^{*}, x and y should become closer and closer to x^{*} and y^{*}. The only remaining question is the speed of convergence. It's actually not an easy question, but fortunately the functions F and G are quite special and point (x, y) converges to (x^{*}, y^{*}) pretty fast. It allows to use the following approach. If after some many steps we have a point (x, y) such that F(x, y) and G(x, y) are within a very small EPS of p1 and p2, answer "YES", otherwise answer "NO". One final note is that searching for x' and y' can be done with usual dichotomy as functions F and G are monotonic by any variable given that the other variable is fixed. See the LayCurse's solution for an example of implementation of this approach. As a conclusion, let's give 3 more special facts about functions F and G, which can be used to construct other search algorithms for this problem. The first of these facts is not hard to prove, but for the other two there seem to be no easy proof.

