A week of 715

AtCoder Grand Contest 031 was the main event of the Mar 11 - Mar 17 week (problems, results, top 5 on the left, analysis). I was stuck for a long time trying to solve any of the last three problems, finally getting F in with some serious squeezing into the time limit. eatmore solved that problem and had enough time and energy left for problem D, thus winning a clear first place. Congratulations!

Said squeezing was required because I over-complicated a simple step of the solution. There was an odd number m up to 10⁶, and up to 10⁵ queries (a, b), and I needed to check for each query if there exists a number k such that a*4^k=b modulo m. I ended up grouping queries (a, b) by gcd(a, b), then in each group we need to answer discrete logarithm queries "is this number a power of 4 modulo q=m/gcd(a,b)", which can be done using big-step-small-step algorithm. This was still not fast enough, but we can actually do big steps only once per group, and small steps once per query, then the optimal size of a big step (and the overall complexity of answering one query) becomes not sqrt(q) but sqrt(q/c) where c is the number of queries in the group, and the solution runs in time.

Of course, all this was completely unnecessary and I should've just found connected components in the graph where edges connect x with 4*x modulo m :)

In the previous summary, I have mentioned an Open Cup problem: let's define f(x) as the smallest non-negative number that can be obtained by placing + or - before each digit in the decimal representation of x, and computing the resulting sum. What is the sum of all numbers x between l and r  that have f(x) equal to 0, 1, ..., 9, modulo 10⁹+7? l and r have at most 100 digits, and there are 10000 testcases to solve in 2 seconds.

The first step is pretty typical for such "between l and r" problems: let's compute the answers for segments [0,r] and [0,l-1] and get the final answer by subtraction. The second step is as typical: let's build our number x from left to right, then as soon as the next digit is smaller than the corresponding digit of r, the remaining digits can be arbitrary and we can use dynamic programming to share computations within testcase and between testcases.

The dynamic programming state will consist of two parts: the number of remaining digits, and something describing the digits already chosen. However, it's not entirely clear what that something should be :) As the first approximation, we would need to store a set of numbers achievable by placing + or - before all digits already chosen. However, with 100 digits the achievable numbers would be up to 900, so we'd have something like 2⁹⁰¹ states.

Here we need to become more practical. First, it seems natural to expect that there's no need to use very big intermediate sums, so we can take a guess and introduce a cap of, say, 100. This still leaves us with at most 2¹⁰⁰ states. Most of those states are not reachable, though, so we can write a small program that would generate all reachable states and learn that there are only 23108 states with a cap of 100, and 65618 states with a cap of 200 (the program uses BigIntegers as bitmasks):

import java.math.BigInteger;
import java.util.*;

public class PlusMinusSums {
    static final int BUBEN = 200;
    static final BigInteger MASK = BigInteger.ONE.shiftLeft(BUBEN).subtract(BigInteger.ONE);

    public static void main(String[] args) {
        ArrayDeque queue = new ArrayDeque<>();
        Map> stateToMoves = new HashMap<>();
        queue.push(BigInteger.ONE);
        stateToMoves.put(BigInteger.ONE, null);
        while (!queue.isEmpty()) {
            BigInteger cur = queue.poll();
            List moves = new ArrayList<>();
            for (int digit = 0; digit < 10; ++digit) {
                BigInteger next = makeMove(cur, digit);
                if (!stateToMoves.containsKey(next)) {
                    queue.add(next);
                    stateToMoves.put(next, null);
                }
                moves.add(next);
            }
            stateToMoves.put(cur, moves);
        }
        System.err.println(stateToMoves.size());
    }

    private static BigInteger makeMove(BigInteger cur, int digit) {
        BigInteger ifAdd = cur.shiftLeft(digit);
        BigInteger ifSub = cur.shiftRight(digit);
        BigInteger ifSubMinus = BigInteger.valueOf(Integer.reverse(cur.intValue() & ((1 << digit) - 1)) >>> (31 - digit));
        return ifAdd.or(ifSub).or(ifSubMinus).and(MASK);
    }
}

This is already quite promising, but still not enough to fit in the time limit. But we can take this idea of automatically discovering the state space further, and say that many of the states we have are actually equivalent. All that matters in the end is the lowest bit set in the final state, and that bit is always between 0 and 9. Therefore, we can do the following process, which is essentially automaton minimization: first, color all states in 10 colors based on the lowest bit set in them. Then repeatedly iterate over all states, and create a new coloring based on the following 11-tuple of colors for each state: the color of this state and the 10 states we can reach from it. After some amount of iterations the number of colors stops changing, which means we have found the equivalence classes of states. It turns out we have only 715 different states in this problem! Here's the code to be inserted into the main() method above:

Map stateToKey = new HashMap<>();
for (BigInteger x : stateToMoves.keySet()) {
    long key = x.getLowestSetBit();
    if (key >= 10) throw new RuntimeException();
    stateToKey.put(x, key);
}
int numStates = 10;
Random random = new Random(54815353151L);
while (true) {
    long base = random.nextLong() * 2 + 1;
    Map newStateToKey = new HashMap<>();
    Set newKeys = new HashSet<>();
    for (BigInteger x : stateToMoves.keySet()) {
        long key = stateToKey.get(x);
        for (BigInteger dest : stateToMoves.get(x)) {
            long childKey = stateToKey.get(dest);
            key = key * base + childKey;
        }
        newKeys.add(key);
        newStateToKey.put(x, key);
    }
    if (newKeys.size() == numStates) break;
    if (newKeys.size() < numStates) throw new RuntimeException();
    numStates = newKeys.size();
    stateToKey = newStateToKey;
    System.err.println(numStates);
}

Having just 715 states makes the overall solution run in time. Moreover, now we can also check the validity of our original assumption: we can notice that the number of different states does not change if we restrict the intermediate sums to 100 or 200, strongly suggesting that we have found all of them.

Thanks for reading, and check back for more!