February 21, 2019 Single Round Match 751 Editorials

SRM 751 was held on Feb 21, 2019. Thanks to majk and misof for setting the problems and majk for penning the editorials

Div2 Easy: Calkin-Wilf

The process can be simulated directly if we store the fractional representation of the current node.

struct CalkinWilf {
    vector <int> findRational(string path) {
        int a = 1, b = 1;
        for (char p: path) {
            if (p == 'L') {
                b += a;
            } else {
                a += b;
            }
        }
        return {a,b};
    }
};

Complexity is O(N).

Div2 Medium: Calkin-Wilf Reversed

Consider a non-root node (a,b) and without loss of generality let a < b. Its parent is the node (a,b-a). We can simulate the process of navigating the tree to the root. However, as the third sample suggests, that would be too slow. Note that we can perform k steps at once if b > k*a – the depth increases by k and (a,b) becomes (a,b-k*a). For performance it is optimal to take k = floor(b/a).

Voila, we have invented Euclidean algorithm!

struct CalkinWilfReversed {
    ll getDepth(ll a, ll b) {
        if (a > b) return getDepth(b, a);
        else if (a == 1) return b-1;
        else return b/a + getDepth(b%a, a);
    }
};

The complexity is O(log(MAX)).

Div2 Hard: Half Graph

A necessary condition for the existence of a half graph is that the degree of every vertex is even. If that is not the case, we can report that no answer exists.

Consider each connected component of G individually. If the number of edges in it is odd, then there clearly is no answer. Otherwise, find an Eulerian tour (a tour which contains all edges exactly once). This exists because the degrees are even. As the length of the tour is even, we can process all edges along the tour and put odd edges into one half and even indexed into second half. Each of the halves will have the properties sought.

bool A[50][50];
int D[50];
int N;

structHalfGraph {
    vector<int> findEulerTour(int u) {
        if (D[u] == 0) return {};
        vector<int> E{u};
        bool done = false;
        while (!done) {
            int u = E.back();
            for (int w = 0; w < N; ++w) {
                if (A[v][w]) {
                    A[v][w] = A[w][v] = false;
                    D[v]--; D[w]--;
                    if (u == w) done = true;
                    else E.push_back(w);
                    break;
                }
            }
        }
        for (int i = 0; i < E.size(); ++i) {
            while (D[E[i]] != 0) {
                auto sub = findEulerTour(E.get(i));
                E.insert(E.begin() + i, sub.begin(), sub.end());
            }
        }
        return E;
    }
    
    vector<string> compute(vector<string> x) {
        N = x.size();
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < N; ++j) {
                A[i][j] = x[i][j] == '1';
                if (A[i][j]) D[i]++;
            }
            if (D[i] % 2 == 1) return {};
        }

        for (int i = 0; i < N; ++i) {
            auto E = findEulerTour(i);
            if (E.size() % 2 == 1) return {};
            for (int j = 0; j < E.size(); j += 2) {
                int u = E[j], v = E[j+1];
                A[u][v] = A[v][u] = true;
            }
        }

        for (int i = 0; i < N; ++i) {
            x[i] = string(N, '0');
            for (int j = 0; j < N; ++j) {
                if (A[i][j]) x[i][j] = '1';
            }
        }
        return x;
    }
};
 

Div1 Easy: Hyperbox

The surface volume of a hyperbox is 2*(a*b*c + a*b*d + a*c*d + b*c*d). Let’s backtrack the lengths of the sides starting from the shortest one. On the first three sides, we break as soon as it is clear that such hyper box does not exist. For example, given sides (a,b), if a hyperbox with sides (a,b,b,b) has too large surface volume, we can stop. The fourth side can be calculated and checked in O(1).

struct Hyperbox {
    int count(int volume) {
        if (volume % 2 == 1) return 0;
        volume /= 2;
        int ans = 0;
        for (ll a = 1; 4*a*a*a <= volume; ++a) {
            for (ll b = a; (3*a+b)*b*b <= volume; ++b) {
                for (ll c = b; (2*a*b + a*c + b*c)*c <= volume; ++c) {
                    ll d = (volume - a*b*c)/(a*b + b*c + a*c);
                    ans += d >= c && a*b*c+a*b*d+a*c*d+b*c*d == volume; 
                }
            }  
        }
        return ans;
    } 
};

We can easily verify that this runs fast enough for v = 2*10^8. Let’s prove the complexity.

The time complexity is O(volume).

Div1 Medium: Wrong Base

The natural way of solving the problem would be to first calculate x_i, then h^(x_i) and finally, the sum. However using Baby Step Giant Step algorithm directly would be too slow.

Instead, we use the fact that g is a generator of the multiplicative group, hence for all h != 0 there exists an integer e, such that g^e = h. This can be found by a single invocation of BSGS. The rest is simple:

h^(x_i) = (g^e)^x_i = (g^x_i)^e = y_i^e

Finally when h = 0, the answer is 0.

constexpr int MOD = 998244353;

struct WrongBase {
    int pow(int a, int x) {
        ll r = 1, p = a;
        while (x > 0) {
            if (x % 2 == 1) r = (r*p) % MOD;
            p = (p*p) % MOD;
            x /= 2;
        }
        return r;
    }
    
    int bsgs(int g, int h) {
        ll gS = 1, p = h
        int SQRT = 32000, gInv = pow(g, MOD-2);

        unordered_map<int,int> M; 
        for (int i = 0; i < SQRT; ++i) {
            M[p] = i;
            (p *= gInv) %= MOD;
            (gS *= g) %= MOD;
        }

        p = 1;
        for (int i = 0; i < SQRT; ++i) {
            if (M.find(p) != M.end()) return M[p] + i * SQRT;
            (p *= gS) %= MOD;
        }
        return -1;
    }

    public int getSum(int g, int h, int a, int d, int n) {
        if (h == 0) return 0;
        int logH = bsgs(g, h);
        ll ans = 0;
        for (int i = 0; i < n; ++i) {
            ans += pow(a, logH);
            a += d;
        }
        return ans % MOD;
    }
};

The complexity is O(sqrt(MOD) + n*log(MOD)).

Div1 Hard: AllInclusiveStrings

The first observation is that in a string of minimal length, each letter occurs at most twice. This is because for an all-inclusive string containing x > 2 copies of a given letter, we can form a new all-inclusive string by keeping only the first and the last occurence.

We model the problem as a directed graph, where letters are vertices, and each required string is an arc.

Let’s first describe a backtracking solution for generating minimal all-inclusive strings. Initially, all arcs are unmarked, and the string is all-inclusive as soon as all edges are marked.

At each position, we try to append every letter x, except if

• the vertex x has degree zero, or
• all incoming arcs to x are already marked, or
• the letter already occurs in the prefix, but some of the vertices from which there is an arc to x

Afterwards, mark all arcs to x for which the source vertex is present in the prefix.

In other words, when the letter is appended for the second time, all bigrams that end with such letter must be present after this append. If they are present after appending the letter for the first time, the letter is never appended for the second time.

Now we need to speed up this backtracking solution by reusing calculations, either using memoization or an explicit DP. The state is (length) * (the set of letters in prefix) * (the set of letters for which all incoming arcs are marked). There are O(N * 3^N) states, O(N) transitions from each state, and with a bit of precomputation each transition can be done in O(1). The total runtime is thus O(3^N * N^2). This seems like a lot, but since there are many unreachable states, this runs fast in practice. Furthermore, if we compute the DP row by row, the transitions can be performed in-place, and the memory complexity is 3^N words, fitting into the ML.

constexpr int MOD = 998244353;
constexpr int M = 16;
int C[M], P3[M+1], D[43046721];
bool P[M], B[43046721], U[M][M];

struct AllInclusiveString {
    vector<int> shortest(vector<string> A) {
        int N = A.size();
        if (N == 0) return {0,1};
        for (int i = 0; i < N; i++) {
            int a = A[i][0]-'a';
            int b = A[i][1]-'a';
            U[a][b] = P[a] = P[b] = true;
            C[b] |= 1<<a;
        }

        vector<int> T; 
        for (int i = 0; i < M; i++) if (P[i]) T.add(i);

        int K = T.size();
        P3[0] = 1;
        for (int i = 0; i < K; i++) P3[i+1] = P3[i] * 3;
        
        D[0] = 1;
        B[0] = true;
        for (int i = 1; ; i++) {
            for (int j = P3[K]-1; j >= 0; j--) {
                if (!B[j]) continue;
                int e = 0;
                for (int k = 0; k < K; k++) {
                    if (j / P3[k] % 3 != 0) e |= 1<<T[k];
                }
                for (int k = 0; k < K; k++) {
                    int cur = j / P3[k] % 3;
                    if (cur == 2) continue;
                    bool ok = (e&C[T[k]])==C[T[k]];
                    if (cur == 0 || ok) {
                        int l = j + (1 + ok - cur) * P3[k];
                        (D[l] += D[j]) %= MOD;
                        B[l] = true;
                    }
                }
                D[j] = 0;
                B[j] = false;
            }

            if (B[P3[K]-1]) return { i, D[P3[K]-1] };
        }
    }
};