February 22, 2022 Single Round Match 824 Editorials

SubtractionGenerator

Counting the number of digits in a number can be a useful routine in this problem. To do that, we simply repeatedly divide the number by 10 until we reach zero. Each division by 10 removes one digit.

int digits(int x) {
    int answer = 0;
    while (x > 0) {
        ++answer;
        x /= 10;
    }
    return answer;
}

Another useful operation is taking a number and constructing a nearby power of 10. For example, we can generate the first power of ten that is strictly greater than our result as follows:

int x = 1;
while (x <= result) x *= 10;

Now we are ready to solve the problem we were given. Our solution will consider just two cases. The first case: suppose we take the x we just constructed (the first power of 10 greater than the desired result) and y = x – result. Clearly, digits(x) is one greater than digits(result), so x is good. The only problem this solution can have is that y can be too small.

If that happens, we can set y2 = x / 10 and then recompute a new value of x using the formula x2 = y + result. Here, y2 is the smallest number with the same number of digits as result. As y2 is greater than y, x2 is greater than x, and thus x2 still has more digits than result and we are done.

public int[] generate(int result) {
    int x = 1;
    while (x <= result) x *= 10;
    int y = x - result;
    if (y < x/10) {
        y = x/10;
        x = y + result;
    }
    return new int[] {x, y};
}

HopscotchCounting

This is an introductory problem for the topic “counting objects using dynamic programming”.

Suppose we want to draw a hopscotch with N squares. We can start with either one square or with two squares. If we start with one square, it’s easy to continue: in the next rows we can draw any hopscotch with N-1 squares. If we start with two squares, we must be a bit more careful: we are now going to draw a hopscotch with N-2 squares, but we must start it with a row that has only one square.

In order to handle this, we can divide the hopscotches of each size into two piles: those that start with one square and those that start with two. We will count the size of each pile separately.

In the code below, startWithOne[x] is the number of hopscotch plans that have a total of x squares and have one square in their first row. Similarly, startWithTwo[x] is the count of x-square plans that start with two squares.

From the above observations we get the recursive formulas used in the code.

public int count(int N) {
    int MOD = 1_000_000_007;
    int[] startWithOne = new int[N+1];
    int[] startWithTwo = new int[N+1];
    startWithOne[0] = startWithTwo[0] = 1;
    startWithOne[1] = 1;
    for (int n=2; n<=N; ++n) {
        startWithOne[n] = (startWithOne[n-1] + startWithTwo[n-1]) % MOD;
        startWithTwo[n] = startWithOne[n-2];
    }
    return (startWithOne[N] + startWithTwo[N]) % MOD;
}

ExactRate

A segment has ratio S:F between successes and failures if and only if it contains S*x successes and F*x failures for some real x >= 0.

Suppose we assign the value +F to each success and the value -S to each failure. Then, the S*x successes have a total value of S*F*x and the F*x failures have a total value of -S*F*x. Hence, each segment with the correct ratio has total value zero.

And vice versa: Take any nonempty segment that now has a total value of zero. Let u and v be the number of successes and failures in this segment. We have u*F – v*S = 0, from which both u and v must be positive and then the equation can be rewritten to u:v = S:F.

Hence, we can take the array of N booleans (successes and failures of our athlete) and transform it into an array of +Fs and -Ss. In this array we are looking for the longest segment with zero sum. That is easy to do: we will simply go through all prefix sums of the array. Segments with zero sum are precisely segments [x,y) such that the prefix sum of the range [0,x) equals the prefix sum of the range [0,y). To find the longest such segment, it is sufficient to keep track of the first occurrence of each value that occurs among the prefix sums.

public int[] getLongest(int N, int seed, int threshold, int S, int F) {
    long[] H = new long[N];
    H[0] = (seed * 1103515245L + 12345) % (1L << 31);
    for (int n=1; n<N; ++n) H[n] = (H[n-1] * 1103515245L + 12345) % (1L << 31);

    HashMap<Long, Integer> firstSeen = new HashMap<Long, Integer>();
    long runningTotal = 0;
    int bestStart = 0, bestEnd = 0;
    firstSeen.put(runningTotal, 0);
    for (int n=0; n<N; ++n) {
        if (H[n] > threshold) runningTotal += F; else runningTotal -= S;
        if (firstSeen.containsKey(runningTotal)) {
            int p = firstSeen.get(runningTotal);
            if (n+1-p > bestEnd-bestStart) { bestStart=p; bestEnd=n+1; }
        } else {
            firstSeen.put(runningTotal, n+1);
        }
    }

    return new int[] {bestStart, bestEnd};
}

SeeAllDifferences

In this problem we are examining a Markov process. Such a process has some states and it moves between them based on some sequence of random choices. In general, questions about the expected time until the process reaches a specific state boil down to systems of linear equations. In this particular problem the set of states we have is rather large, so we will have to be a bit clever about how we are constructing and solving those equations.

The expected time from some intermediate state to the end of the game depends on two things: the set of differences we have already seen, and the last value rolled on the die. (The order in which we saw those differences clearly doesn’t matter, and previous rolls clearly do not matter as well. The last roll does matter, because it influences probabilities for the next difference. E.g., if the last rolled number was anything other than 1 or D, the next roll cannot produce the difference D-1.)

Thus, we have D*2^D states. For each of those states we’ll have one variable X[state] that denotes the answer we seek: “What is the expected number of extra rolls needed to get from this state to a state in which all D differences have been seen?”

For the states where we have already seen all D differences the answer is trivially 0. For each other state we can now look at what happens in the next roll and write a linear equation that relates the answer to this state to the answers for other states.

For example, suppose D=4 and we are in the state (0011,2). I.e., in the current state we have already seen differences 2 and 3, and the last rolled number was a 2. What happens in the next roll? We roll a 1, 2, 3, or a 4. In the first case we will reach the state (0111,1), in the second case the state (1011,2), the third case leads to (0111,3), and the fourth case leads to (0011,4). Thus, X[0011,2] equals 1 for the roll we just made, plus the average of answers for those four new states.

Thus, we get a system of D*2^D linear equations for D*2^D variables. It’s easy to show that the system is regular (i.e., has a unique solution) but it’s too big to solve all at once.

To get a better solution, we can note that the state space is almost acyclic: we are only adding new differences to the set of seen ones, we are never removing any. Each new roll will either leave us with the exact same set we had, or it will add one new difference.

We will now process all states by iterating from 1111 down to 0000. This order has the useful property that all supersets of a set are processed before the set itself. Thus, when we are for example processing the set 0011, we already know the value X[1011,2] because the state 1011 has already been processed.

Each state is associated with D variables. The D equations for these variables may refer to each other. In our example, the equation for X[0011,2] refers to X[0011,4], and then the equation for X[0011,4] refers to X[0011,2] again. But this is not a problem: we can simply use the standard Gaussian elimination algorithm to solve this set of D equations and learn all values X[0011,*] at the same time.

HorsesGoHome

Subproblem 1: knight distance. Suppose we want to get a chess knight from (0,0) to (x,y) with x,y >= 0, what is the minimum number of steps to do that?

Knight distances are actually pretty uniform. (If you never in your life looked at the output of a BFS for a chess knight, you may wish to do so now.) There are only two non-trivial special cases: the distance to (0,1) is 3 and the distance to (2,2) is 4. Other than these, each knight distance can be computed as follows:

• Lower bound 1: each jump decreases x+y by at most 3, so we need at least ceiling( (x+y)/3 ) jumps.
• Lower bound 2a: each jump decreases x by at most 2, so we need at least ceiling( x/2 ) jumps.
• Lower bound 2b: we need at least ceiling( y/2 ) jumps.
• Parity requirement: the number of jumps must have the same parity as x+y.
• The smallest distance that satisfies all these constraints is always the correct distance.

Subproblem 2: knight path construction: Suppose we want to actually get a chess knight from (0,0) to (x,y). How to do that?

Instead of explicitly writing greedy sequences of moves and messing up all kinds of +- signs, simply use the above formula repeatedly. For each step try all 8 possible jumps and pick one that decreases your distance from the goal.

Subproblem 3: Suppose for now the knights don’t see each other and may move independently. What is the minimum total number of jumps?

The answer here is what is called the assignment problem. For each of the H horses and each of the 64 cells of the stable we know the minimum number of moves for that horse to reach that cell. This gives us a weighted bipartite graph. In this graph we are looking for the minimum cost matching that covers all horses. Such a matching can be constructed in polynomial time. (E.g., using the Hungarian algorithm for the assignment problem, or using any implementation of minimum cost maximum flow.)

Subproblem 4: If the knights block each other, can we always get a solution with that number of moves?

Sure we can.

Lemma: If not all knights are in their desired destinations, there is always a knight whose desired destination is empty.

Proof: If they are all blocked by other knights, we can find a cycle of knights who block each other. That is a contradiction with our solution being optimal: it would be better to simply leave all those knights where they are.

Now let’s pick a knight and construct one shortest path for this knight to his goal. Along this path there can be some other knights blocking some of the cells. Schematically, it can look as follows: A…B..C.D….. where A, B, C, D are different knights. Instead of A having to wait, we will move D to A’s destination, then C to D’s current location, then B will replace C, and finally A will replace B. The total number of steps is the same as if A went through everyone else, and the final effect is also the same: there are still knights in locations B, C, D, only the location A is now empty and the end of that path now has a knight.