December 26, 2022 Single Round Match 842 Editorials

ToniasTower

The first row must have at least 1 cube. And as each following row must have more cubes than the previous one, row k must have at least k cubes, for all k.

This tells us that the smallest tower with k rows must be the one with exactly 1+2+…+k cubes. If we have fewer cubes than that, we cannot build any tower with k rows.

Once we know this, we can easily find the optimal k for N cubes: the largest k such that 1+2+…+k <= N.

(We can use a formula for that, but we don’t have to: as N <= 100,000, we can simply increment k until the sum exceeds N.)

Now we have a tower of the optimal height, but if N > 1+2+…+k we also have some unused cubes. What shall we do with them? 

Well, we just need to add them to the tower somehow. The most straightforward way of doing that is simply adding all of them to the bottom row.

As the number of cubes in an optimal tower is roughly quadratic in its height, the optimal height of a tower for N cubes is roughly the square root of N. Hence, the time complexity of this solution is O(sqrt(N)).

int minCubes(int rows) {
    return rows * (rows+1) / 2;
}

public int[] build(int N) {
    // find the optimal number of rows
    int rows = 1;
    while (minCubes(rows+1) <= N) ++rows;

    // build the smallest possible tower
    int[] answer = new int[rows];
    for (int r=0; r<rows; ++r) answer[r] = r+1;

    // add the remaining cubes to the bottom row and we are done
    answer[rows-1] += N - minCubes(rows);
    return answer;
}

SmallRectangles

Clearly if there are duplicates in A we can discard them, as they will just create new copies of rectangles we already have. An easy way to implement this is to simply insert all elements of A into a set, which will automatically discard duplicates. Symmetrically, we can also discard duplicates from B. Below we will assume that we already did this.

Let A contain x and B contain y elements. This creates x*y rectangles. But are they all distinct?

The only case when they aren’t distinct is if there are some pairs (u, v) and (v, u) that both appear among the above x*y rectangles. The correct answer is then x*y minus the number of such pairs.

How can we count such pairs? The key observation is that both values u and v must have the property that they appear in both A and B.

Let C be the intersection of A and B, and let C contain z elements. In other words, let z be the number of distinct values that appear both in A and in B.

Each pair (u, v) = (v, u) that got counted twice consists of two distinct elements of C. Hence, there are exactly z*(z-1) / 2 such pairs.

public long count(int[] Aprefix, int[] Bprefix, int AL, int BL, 
                  int AM, int BM, int seed) {

    // generate the arrays A and B
    long state = seed;
    int[] A = new int[AL];
    for (int i=0; i<Aprefix.length; ++i) A[i] = Aprefix[i];
    for (int i=Aprefix.length; i<AL; ++i) {
        state = (state * 1103515245 + 12345) % (1L << 31);
        A[i] = (int)(1 + (state % AM));
    }
    int[] B = new int[BL];
    for (int i=0; i<Bprefix.length; ++i) B[i] = Bprefix[i];
    for (int i=Bprefix.length; i<BL; ++i) {
        state = (state * 1103515245 + 12345) % (1L << 31);
        B[i] = (int)(1 + (state % BM));
    }

    // discard duplicates from A and B
    HashSet<Integer> SA = new HashSet<Integer>();
    for (int a : A) SA.add(a);
    HashSet<Integer> SB = new HashSet<Integer>();
    for (int b : B) SB.add(b);

    // find the size of their intersection
    long common = 0;
    for (int b : SB) if (SA.contains(b)) ++common;

    // compute the final answer
    return 1L * SA.size() * SB.size() - ((common * (common-1)) / 2);
}

StringReduction

Clearly, we can start by using the swaps to sort the string: bringing equal letters together can never harm us, it can only help. From this point on we can treat each letter separately.

The main trap in this problem is to try applying the erasing rules greedily. In general, this does not work. For example, suppose we have 13 equal letters and two rules: one that works on a block of size 12 and the other that works on a block of size 4. The simple greedy solution will erase 11 of the 12 letters and be left with 2, but the optimal solution will instead apply the other rule 4 times, each time erasing 3 letters.

One good way to gain intuition about this problem is to realize that if we make everything (both the number of letters and each rule) one smaller, we get a more standard knapsack / coin change style problem.

That can help bring us to a correct solution: instead of trying to come up with some more complicated greedy rule (which will still be wrong), we can simply try all ways to apply the rules, and use memoization/dynamic programming to make sure the search runs in time.

Suppose we have N copies of a letter and a collection of rules for that letter, given in the array X. Then, let dp[y] denote the smallest number of letters we can end with if we start from y letters and apply the given rules to erase some of them. Clearly, dp[0]=0 and dp[1]=1. For any bigger y: dp[y] is the minimum of all dp[y-(x-1)], taken over all x from X that can be used in this situation (i.e., 1 < x <= y).

int solveOne(int letterCount, int[] rules) {
    if (letterCount == 0) return 0;
    int[] dp = new int[letterCount+1];
    for (int s=0; s<=letterCount; ++s) {
        dp[s] = s;
        for (int x : rules) {
            if (x > s) continue;
            dp[s] = Math.min( dp[s], dp[s-(x-1)] );
        }
    }
    return dp[letterCount];
}

public int reduce(String start, int[] X, String Y) {
    int N = X.length;
    int answer = 0;
    for (char c='a'; c<='z'; ++c) {
        int ruleCount = 0;
        for (int n=0; n<N; ++n) if (Y.charAt(n) == c) ++ruleCount;
        int[] rules = new int[ruleCount];
        for (int n=0; n<N; ++n) if (Y.charAt(n) == c) rules[--ruleCount] = X[n];
        int letterCount = 0;
        for (char x : start.toCharArray()) if (x == c) ++letterCount;
        int curr = solveOne(letterCount, rules);
        answer += curr;
    }
    return answer;
}

SmoothMultiples

If C is reasonably large (in the reference solution: at least 3000), the number of multiples of C in the range [A,B] is so small that we can test each of them for being K-smooth. This leaves us with the same problem but a much smaller value of C.

Imagine that we are building an exactly 11-digit number from the left to the right. (This number may have leading zeros, those aren’t taken into account when evaluating whether it’s K-smooth.) Any moment during this construction can be described by two variables: the variable “remains” giving the number of digits we still need to determine, and the variable “prefix” giving the 11-remains digits we already determined.

For the current pair (remains, prefix) we always want to answer the same question: how many corresponding smooth multiples are there? To answer this question we proceed as follows:

• We determine the smallest and the largest number that can be obtained by adding the remaining digits.
• If the largest number is less than A, or the smallest is more than B, there are no smooth multiples for this pair (remains, prefix).
• If all the numbers we can produce are within the range [A,B], we get an easier problem. In this problem we have already made sure that the number we produce will be in the correct range, and so we only care about the other two constraints: it must be K-smooth and divisible by C. We’ll explain below how to solve this case.
• If neither of the above cases applies, i.e., we can produce some numbers that are within the range [A,B] but also some that are outside this range, the current prefix must match one of the prefixes of A and B. Thus, there are only a few such situations and we don’t have to give them too much attention. We solve them simply by trying all viable possibilities for the next digit. For each of them, we’ll make a recursive call with (remains minus 1, prefix plus the new digit).

As promised above, let’s now look at the middle case. We have some prefix, we know how many unknown digits remain, and we want to count the number of ways in which this can be done. The key observation is that here we can use memoization: we don’t have to count the answer separately for each possible prefix, we can cleverly reuse some information we already computed. Why? Because the answer to our question is completely determined by three values:

• Obviously, the value “remains”: the number of remaining digits.
• The value (prefix modulo C): the current remainder modulo C we have.
• The value (prefix modulo 10): the last digit of the current prefix.

Why is this the case? Because the last digit of the prefix tells us which options for the next one are valid, and once we choose the next digit d, the new remainder modulo C will be uniquely determined by the old remainder z and by d: it will be (10*z+d) modulo C. Thus, if we have different pairs (remains, prefix) but the values (prefix modulo C) and (prefix modulo 10) both match, the sequences of following digits that create smooth multiples will be exactly the same in both situations.

And this is precisely where we can apply memoization: for each situation (remains, prefix mod C, prefix mod 10) we will compute the answer once and then reuse it whenever we encounter the same situation again.

With C <= 3000 this gives us at most 12*3000*10 questions to answer. For each of these questions, the first time we encounter it, we do the same simple thing we did in a case analyzed above: iterate over all <= 10 viable options for the next digit, and for each of them make a recursive call to count the solutions with the new longer prefix.

int K;
long A, B, C;
long[][][] memo;

long recurse(int remains, long prefix) {
    long minval = prefix, maxval = prefix;
    for (int i=0; i<remains; ++i) {
        minval = 10*minval;
        maxval = 10*maxval+9;
    }
    if (maxval < A) return 0;
    if (minval > B) return 0;
    if (remains == 0) {
        if (prefix % C == 0) return 1;
        return 0;
    }
    if (A <= minval && maxval <= B) {
        // we are inside the range, memoize if we can
        int rem = (int)(prefix % C);
        int last = (int)(prefix % 10);
        if (memo[remains][rem][last] >= 0) return memo[remains][rem][last];
        long answer = 0;
        for (int d=0; d<10; ++d) {
            if (Math.abs(d - prefix%10) > K) continue;
            answer += recurse(remains-1, 10*prefix+d);
        }
        memo[remains][rem][last] = answer;
        return answer;
    } else {
        // we are on the edge, iterate over all possibilities for the next digit
        long answer = 0;
        for (int d=0; d<10; ++d) {
            if (prefix != 0 && Math.abs(d - prefix%10) > K) continue;
            answer += recurse(remains-1, 10*prefix+d);
        }
        return answer;
    }
}

public long count(int _K, long _A, long _B, long _C) {
    K = _K;
    A = _A; 
    B = _B;
    C = _C;
    if (C >= 3000) {
        System.out.println("brute");
        long answer = 0;
        for (long i=1; i*C<=B; ++i) {
            long N = i*C;
            if (N < A) continue;
            if (good(K,N)) ++answer;
        }
        return answer;
    }
    System.out.println("dp");
    memo = new long[12][(int)C][10];
    for (int a=0; a<12; ++a) for (int b=0; b<C; ++b)
        for (int c=0; c<10; ++c) memo[a][b][c] = -1;
    return recurse(11,0);
}

Let T be the threshold at which we switch to brute force, and let Z=10 be the base in which we are solving the task. The brute force solution needs to check O(B/T) numbers, each of them in O(log B) arithmetic operations. The DP solution needs to answer O( log B * T * Z ) questions, each can be answered in O(Z) time. The optimal choice of T is asymptotically the one where both worst cases are the same, i.e., B/T should be on the same order as T*Z*Z. This gives us that for the best asymptotic time complexity T should be on the order of sqrt(B/Z^2).

ColorfulStrip

We can represent the current state of the strip as a set containing single-colored segments that form the current strip. Each element of the set will be a triple (start, end, pcolor), where [start,end) is the half-open interval of indices that form the segment, and pcolor is 10 to the power of the color of this segment.

Along with this data structure we shall maintain the current fingerprint of the strip. Initially, there is a single segment (0, N, 1) and the fingerprint is N.

Each coloring operation can be simulated as follows:

• Take the current interval [lo, hi)
• Repeatedly, find the first interval I in the set that ends after lo. If this interval starts at hi or later, we have already erased everything that overlaps our current interval. Otherwise, remove the part of the interval I that overlaps [lo, hi). 
• Note that if I contains [lo, hi) strictly inside, this will produce two new intervals of I’s color: one ending before lo and the other starting at hi. This special case can only happen once per operation.
• Add the new interval [lo, hi) with the appropriate pcolor to the set.

Each time we add or remove an interval, we can directly recompute how the fingerprint changes: the change is equal to the pcolor of that interval (i.e., 10 to its color), times its length. This value is subtracted for intervals we erase and then added for the new interval(s) we insert.

Each operation will increase the size of the set by at most 2, so there are at most 2*Q insertions into the set during the solution. The total number of times we completely erase an interval from the set must also be at most 2*Q, so the number of operations with the set performed during a single coloring operation amortizes to a constant.

int N, C, Q;
long MOD;
long[] pow10;
int[] QL, QR, QC;
long[] QCP;

long pow10big(int N) {
    if (N == 0) return 1;
    long tmp = pow10big(N/2); tmp *= tmp; tmp %= MOD;
    if ((N % 2) == 1) { tmp *= 10; tmp %= MOD; }
    return tmp;
}

public int recolor(int _N, int _C, int _Q, int maxL, int seed) {
    N = _N; C = _C; Q = _Q; MOD = 1_000_000_007;

    pow10 = new long[300000];
    pow10[0] = 1;
    for (int i=1; i<pow10.length; ++i) pow10[i] = (pow10[i-1] * 10) % MOD;

    QL = new int[Q];
    QR = new int[Q];
    QC = new int[Q];
    QCP = new long[Q];

    long state = seed;

    for (int i=0; i<Q; ++i) {
        state = (state * 1103515245 + 12345) % (1L << 31);
        int qlen = (int)(1 + (state % maxL));
        
        state = (state * 1103515245 + 12345) % (1L << 31);
        QL[i] = (int)(state % (N+1-qlen));
        QR[i] = QL[i] + qlen - 1;

        state = (state * 1103515245 + 12345) % (1L << 31);
        QC[i] = (int)(state % C);
        QCP[i] = pow10big(QC[i]);
    }

    // going to simulate with a set
    // java structs are slow, so we do a set of longs where we store just the
    // endpoint + index to where the rest of data is stored
    TreeSet<Long> ends = new TreeSet<Long>();
    int[] starts = new int[2*Q+3];
    long[] colors = new long[2*Q+3];
    int qq = 1;
    starts[0] = 0;
    colors[0] = 1;
    ends.add( ((1L * N) << 20) | 0 );

    long fingerprint = N;
    long answer = 0;

    for (int q=0; q<Q; ++q) {
        int lo = QL[q], hi = QR[q]+1;
        while (true) {
            long where = ends.ceiling( (1L * (lo+1)) << 20 );
            int idx = (int)(where & ((1L << 20) - 1));
            long chi = where >> 20;
            long clo = starts[idx];
            if (clo >= hi) break;
            if (chi <= hi) {
                if (clo >= lo) {
                    // this entire interval gets erased
                    ends.remove(where);
                    long tmp = (chi - clo); tmp *= colors[idx]; tmp %= MOD;
                    fingerprint += MOD; fingerprint -= tmp; fingerprint %= MOD;
                } else {
                    // cut off the tail part
                    ends.remove(where);
                    long tmp = (chi - lo); tmp *= colors[idx]; tmp %= MOD;
                    fingerprint += MOD; fingerprint -= tmp; fingerprint %= MOD;
                    ends.add( ((1L * lo) << 20) | idx );
                }
            } else {
                if (clo >= lo) {
                    // cut off the head part
                    long tmp = (hi - clo); tmp *= colors[idx]; tmp %= MOD;
                    fingerprint += MOD; fingerprint -= tmp; fingerprint %= MOD;
                    starts[idx] = hi;
                } else {
                    // cut out the middle
                    long tmp = (hi - lo); tmp *= colors[idx]; tmp %= MOD;
                    fingerprint += MOD; fingerprint -= tmp; fingerprint %= MOD;
                    starts[idx] = hi;

                    starts[qq] = (int)clo;
                    colors[qq] = colors[idx];
                    ends.add( ((1L * lo) << 20) | qq );
                    ++qq;
                }
            }
            if (chi >= hi) break; // no more stuff to do
        }

        // insert the new interval, recompute the fingerprint
        starts[qq] = lo;
        colors[qq] = QCP[q];
        ends.add( ((1L * hi) << 20) | qq );
        ++qq;

        long curr = (hi - lo);
        curr *= QCP[q];
        curr %= MOD;
        fingerprint += curr;
        fingerprint %= MOD;

        // update the final hash
        answer += fingerprint * pow10[q];
        answer %= MOD;
    }
    return (int)answer;
}