Match Editorial

Match summary

The score distribution in this round seems similar to the ones in rounds 1-A and 1-B. The problems were balanced, with the exception of the hard problem, which was solved by only three people. The top spot was taken by reid, second went krijgertje and rounding out the top three was Krzysan, who regained his red status. Congratulations to them and to all the advancers!

The Problems

Value	250
Submission Rate	274 / 300 (91.33%)
Success Rate	236 / 274 (86.13%)
High Score	Krzysan for 248.44 points (2 mins 15 secs)
Average Score	208.06 (for 236 correct submissions)

This proved to be a simple problem -- many people solved it, and some did so in impressively short times. A naive approach is to fix the start and end indices of a contignuous subsequence. We can then test if the numbers in the sequence are friendly. We can do this by testing if each number in the subsequence is friendly with the first number in it.

        
    public int count(int[] a) {
        int nr = 0;
        for (int i = 0; i < a.length;i++) {
            for (int j = i + 1; j < a.length; j++) {
                if (isFriendly(i, j, a)) nr++;
                else break;
            }
        }
        return nr;
    }

        boolean isFriendly(int start, int end, int[] a) {
        for (int i = start + 1; i <= end; i++)
                        if (!friendly(a[start], a[i]) return false;
                return true;                
        }

    int[] digits(int x) {
        int[] ret = new int[10];
        if (x == 0) ret[0] = 1;
        else {
            while (x != 0) {
                ret[x % 10] = 1;
                x /= 10;
            }
        }
        return ret;
    }

    boolean friendly(int x, int y) {
        int[] a = digits(x);
        int[] b = digits(y);
    return Arrays.equals(a, b);
    }

Value	500
Submission Rate	123 / 300 (41.00%)
Success Rate	102 / 123 (82.93%)
High Score	Krzysan for 434.66 points (11 mins 22 secs)
Average Score	286.70 (for 102 correct submissions)

To solve this problem we can simply try every possible valid queen placement on the board, and check if the configuration covers all the cells on the board. One way of doing this is the following:

    boolean ok() {
        for (int i = 0; i < 8; i++) {
            if (row[i]) continue;
            for (int j = 0; j < 8; j++) {
                if (b[i].charAt(j) == '.') {
                    if (column[j] || firstDiagonal[i - j + 7] || secondDiagonal[i + j]) return false;
                }
            }
        }
        return true;
    }

    void back(int curRow, String curSol) {
        if (curRow == 8) {
            if (!ok()) return;
            if (curSol.length() < sol.length() ||
                    (curSol.length() == sol.length() && curSol.compareTo(sol) < 0))
                sol = curSol;
            return;
        }
        for (int i = 0; i < 8; i++) {
            if (!column[i] && !firstDiagonal[curRow - i + 7]
                && !secondDiagonal[curRow + i] && b[curRow].charAt(i) != '#') {

                row[curRow] = true; column[i] = true;  firstDiagonal[curRow - i + 7] = true; 
                secondDiagonal[curRow + i] = true;

                back(curRow + 1, curSol + (char)('1' + row) + (char)('A' + i));

                row[curRow] = false; column[i] = false; firstDiagonal[curRow - i + 7] = false; 
                secondDiagonal[curRow + i] = false;
            }
        }
        back(curRow + 1, curSol);
    }

Value	1050
Submission Rate	9 / 300 (3.00%)
Success Rate	3 / 9 (33.33%)
High Score	reid for 524.49 points (37 mins 34 secs)
Average Score	470.65 (for 3 correct submissions)

This problem is a bit harder than the usual div 1 1000. The problem asks the solver to find the number of different connected subgraphs of a given graph G, with the set V of vertices, and the set E of edges, so that the subgraphs contains all vertices in V. The fact that n is smaller than 16 suggests that an exponential solution is possible. One approach would be to try finding num[V'], where V' is a subset of V and num[V'] is the number of connected subgraphs of G that have as vertices the nodes in V'. Also let e[V'] be the number of subgraphs of G, with the vertex set V'. e[V'] is easy to find because if we have m edges between the vertices of V' in the original graph, then for each edge we have two possibilities, adding it or not adding it to a subgraph, so e[V'] = 2^m.

Now suppose we want to find num[V'], and we know e[V'] and also num[V"] and e[V"] for every subset V" of V'. Having this data, it's easier for us to compute the number of disconnected subgraphs of G with the vertex set V'. Let v be the vertex with the largest index in V'. Now for a subgraph G' of G that contains the vertices V' to be disconnected we have to have v in one connected component, and the other vertices in different components, so we have to split V' in two sets of nodes V₁ and V₂. We also need a connected subgraph with the nodes V₁ and another subgraph with the nodes V₂. This way we can find that the number of disconnected subgraphs with the vertice set V' is equal to the sum of num[V₁] * e[V₂] for every possible way of splitting V' in sets V₁ and V₂ so that V₁ contains the node v.

To find the connected graphs we just need to substract the previous number from e[V']. So we have the recurrence formula num[V'] = e[V'] - sum num[V₁] * e[V₂]. This solution has the complexity O(3ⁿ + n * 2ⁿ) because we can iterate through the sets and subsets in the problem by going through numbers 0 to 3ⁿ - 1. The digits that are not 0 in the current number correspond to the vertices of V', and digits 1 and 2 correspond to vertices in V₁ and V₂, respectively.

One way of implementing the above would be this:

    void doit(int x, int b1, int b2, int l) {
        if (x == n) {
            if (l == 2)
                num[b1 | b2] = (10000 + num[b1 | b2] - (e2[b1] * num[b2])) % 1000;
        } else {
            doit(x + 1, b1, b2, l);
            doit(x + 1, b1 | (1 << x), b2, 1);
            doit(x + 1, b1, b2 | (1 << x), 2);
        }
    }
    public int countWays(String[] paths) {
        n = paths.length;
        num = new int[1 << n];
        e2 = new int[1 << n];
        for (int i = 0; i < (1 << n); i++) {
            for (int j = n - 1; j  >= 0; j--) {
                if ((i & (1 << j))!= 0) {
                    if (i == (1 << j)) {
                        num[i] = 1;
                        e2[i] = 1;
                    } else {
                        num[i] = num[i & ~(1 << j)];
                        for (int j1 = j - 1; j1 >= 0; j1--) {
                            if ((i & (1 << j1))!= 0) {
                                if (paths[j].charAt(j1) == 'Y') {
                                    num[i] = (2 * num[i]) % 10000;
                                }
                            }
                        }
                        e2[i] = num[i];
                    }
                    break;
                }
            }
        }
        doit(0, 0, 0, -1);
        return num[(1 << n) - 1] % 10000;
    }