Match Editorial

Match summary

Petr'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 half-step ahead of a very close group.

The Problems

Value	250
Submission Rate	860 / 912 (94.30%)
Success Rate	795 / 860 (92.44%)
High Score	catcher for 249.29 points (1 mins 31 secs)
Average Score	208.44 (for 795 correct submissions)

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;
  }

Value	500
Submission Rate	655 / 912 (71.82%)
Success Rate	303 / 655 (46.26%)
High Score	BigGameHunters for 470.26 points (7 mins 14 secs)
Average Score	299.50 (for 303 correct submissions)

Value	250
Submission Rate	626 / 645 (97.05%)
Success Rate	448 / 626 (71.57%)
High Score	Giorgi for 246.51 points (3 mins 23 secs)
Average Score	189.17 (for 448 correct submissions)

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++;
...

...
    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 non-empty is necessary because of a specific behavior of String.split() method (remove that check and try this solution against input with currentDir = "/").

Value	1000
Submission Rate	109 / 912 (11.95%)
Success Rate	19 / 109 (17.43%)
High Score	cryinlaugh for 733.98 points (18 mins 34 secs)
Average Score	541.01 (for 19 correct submissions)

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 i-th element of have is equal to the number of times the 
            // i-th 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 "non-used" 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 non-used appearences of the used letters (ditto, because the prefix with more than 100 non-used 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;
    }
}

Value	500
Submission Rate	287 / 645 (44.50%)
Success Rate	82 / 287 (28.57%)
High Score	ACRush for 443.28 points (10 mins 26 secs)
Average Score	263.68 (for 82 correct submissions)

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:

1. Create list A of vertices.
2. Add vertex i to that list.
3. Create a new list B, containing all vertices directly accessible from at least one vertex which was in list A.
4. Replace list A with list B.
5. If list A contains vertex i, then append '1' to answer. Otherwise, append '0'.
6. If we've completed less than 1000 cycles, return to point 3.

Having that done for all vertices, we merge all output sequences to one sequence, which has '1' as the i-th character if at least one of the initial sequences had '1' as the i-th 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.

Value	1000
Submission Rate	57 / 645 (8.84%)
Success Rate	3 / 57 (5.26%)
High Score	tos for 580.57 points (29 mins 0 secs)
Average Score	507.73 (for 3 correct submissions)

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.

1. F(x, y) = G(y, x) = G(1 - x, 1 - y) = F(1 - y, 1 - x).
2. The function 1 - F(x, y) - G(x, y) (i.e. the probability of a draw) is bimonotonic. That means, if one of variables is fixed, it first increases by the other variable and then decreases.
3. The curves F(x, y) = const are convex. The curves G(x, y) = const are concave.