A double Moscow week

The first week of April was of course focused on ICPC 2019 World Finals (problems, results, top 12 on the left, official broadcast, our stream, analysis). It feels strange to write a short summary given the amount of coverage available for the contest, but I'll do it anyway :) Warsaw took a huge early lead, but almost stopped after two hours, spending eternity on the technically tricky problem C and still not solving it. The three pre-tournament favorites Moscow, MIT and Tokyo overtook them, but only Moscow could solve all 10 solvable problems. Congratulations to the winners and to all medalists!

Problem K was the most exciting for me, even though I didn't actually solve it myself. It went like this: you are given a street with n<=500 traffic lights on it arranged from left to right. The i-th traffic light stays red for r_i seconds, then green for g_i seconds, then repeats this cycle infinitely. The cycles for all traffic lights start at the same time 0, r_i and g_i are integers, and r_i+g_i does not exceed 100. Suppose you approach this street from the left at a random moment in time, and drive until you encounter a red light for the first time, or until you pass the entire street. What is the probability that you see red for the first time on 1st, 2nd, ..., n-th traffic light?

Codeforces Global Round 2 took place on Saturday, when most of the teams were already back home or on the way there (problems, results, top 5 on the left, analysis). ICPC gold medalist ecnerwala got enough points for the first place in less than an hour, even though our entire streaming team was trying to catch him as you can see :) Well done!

Problem G in this round was very nice. You have n game units, each capable of causing 1 unit of damage per second. You need to merge them into m bigger game units, and if a_i units were merged into the i-th bigger unit, it will cause a_i units of damage per second. The m bigger units will then attack an enemy army also consisting of m units, with the j-th enemy unit having b_j hit points. The attack will happen second-by-second, and in each second each of your big units attacks one enemy unit. It is allowed for multiple units to attack one enemy unit in one second. What is the fastest way to decrease the hit points of all enemy units to zero or negative? You can choose the way you merge the n units into m big units, but you can do it only once, before all attacks.

Thanks for reading, and check back for more!

An order statistic week

The weekend of the Mar 25 - Mar 31 week was already the time to travel to Porto for ICPC World Finals for participants, but it still had a couple of rounds. TopCoder SRM 754 was the first one (problems, results, top 5 on the left, analysis). tourist's solution for the medium was challenged, which doesn't happen very often, but he more than made up for that by being the only contestant to solve the hard. Congratulations on the win!

Codeforces Round 549 followed a few hours later (problems, results, top 5 on the left, analysis). It was Um_nik's turn to dominate, being the only one to solve all problems but already leading the field with a sizable margin after solving 4 out of 5. Well done!

In the previous summary, I have mentioned an AtCoder problem: we pick n independent uniformly random points on a circle, and then find two points the (circular/angular) distance between which is as close to 1/3 of the circle as possible. What is the expected value of the difference between that distance, expressed as a fraction of the circle, and 1/3? n is up to 10⁶, and you need to compute the answer using division modulo 10⁹+7.

The official editorial has a similar but not exactly the same explanation that does not require any googling to solve the problem. However, I'd like to share my approach as well.

Let's collapse the circle 3 times, in other words project each point between 1/3 and 2/3 to x-1/3, and each point between 2/3 and 1 to x-2/3. The original question of finding two points with distance as close to 1/3 as possible almost translates into finding two closest points on this projection: if two points x and y are close, then these two points are either also close on the original circle (with probability 1/3), or the distance between them on the original circle is close to 1/3 (with probability 2/3), since 2/3 is also 1/3 when viewed from another angle. Moreover, these probabilities of 1/3 are almost independent for pairs of consecutive points: it's impossible that all pairs of consecutive points are close on original circle as well, but apart from that the probability that any k<n consecutive pairs each are close on the original circle as well is equal to 1/3^k.

Now, in order to find the expected value of the difference between the sought distance and 1/3, define f(x) as the probability that this difference is >=x, then our answer is the integral of f(x).

Consider g(x,k) to be the probability that the k-th smallest distance (in sorted order, the so-called order statistic) between consecutive points from n uniformly random ones being >=x. Then we can find the probability that exactly k distances between consecutive points are less than x as g(x,k+1)-g(x,k) (we define g(x,0)=0 here). If the points are picked on a circle of size 1/3 instead of the unit circle, that probability is equal to g(3x,k+1)-g(3x,k). Finally, if we have k such distances on the 1/3 circle less than x, then in order to have our answer >=x, we need all of those small distances to be "also close" on the original circle, the probability of which is 1/3^k, therefore we have established that f(x)=sum_k((g(3x,k+1)-g(3x,k))/3^k).

Since we're interested in the integral of f(x), we can swap summation and integration in the above formula, and learn that we're interested in sum_k((int(g(3x,k+1))-int(g(3x,k)))/3^k)=sum_k((int(g(x,k+1))-int(g(x,k)))/3^k+1).

Finally, int(g(x,k)) is simply the expected value of the k-th order statistic of distances between consecutive points when n uniformly random points are chosen on a circle. It turns out it's possible to google it: int(g(x,k))=1/n*(1/(n-k+1)+1/(n-k+2)+....+1/n).

Most of the terms cancel out, and we get int(g(x,k+1))-int(g(x,k))=1/(n*(n-k)), and int(f(x))=sum_k(1/(n*(n-k)*3^k+1)), where the summation is done over all values of k from 0 to n-1, which solves our problem, and the actual code we submit just computes this sum.

As I was coming up with this solution, I did not just invent it from top to bottom. Instead, I was digging from both ends: first, I've noticed that the setting is similar but not exactly the same as just finding the smallest distance between n random points on a circle of size 1/3. Then, I've googled that such distance has a known closed-form expression, and the same is true for k-th order statistic. Then, I've noticed that knowing how the k-th order statistic behaves allows us to split the probability space into areas where we just need to multiply by 1/3^k. Finally, I've put the pieces together and verified that swapping summation and integration checks out, implemented the solution and got wrong answer for all samples: I forgot the extra 1/3 that comes from the fact that our circle is of size 1/3 instead of 1, and thus had 3^k instead of 3^k+1 in the formula. The contest time was running out, and I've almost given up hope, but still started to make small changes to the code expecting that I have some issue in that vein, 3^k-1 didn't help but 3^k+1 did, and I very happily submitted with just 1 minute left in the round :)

Thanks for reading, and check back for more!

A close to third week

TopCoder SRM 753 opened the Mar 18 - Mar 24 week in competitive programming (problems, results, top 5 on the left, analysis). Just ecnerwal and mnbvmar solved all three problems, and ecnerwal was so much faster that the challenge phase did not really matter. Congratulations on the victory!

AtCoder Grand Contest 032 took place on Saturday (problems, results, top 5 on the left, analysis). ksun48 solved problem F in just 30 minutes, and tourist solved problem E in just 15 minutes, but nobody was able to solve both during the round. Therefore the advantage went to contestants who went for F, and ksun48 was by far the fastest of those. Well done!

The hardest problem F had a very simple-looking statement. We pick n independent uniformly random points on a circle, and then find two points the (circular/angular) distance between which is as close to 1/3 of the circle as possible. What is the expected value of the difference between that distance, expressed as a fraction of the circle, and 1/3? n is up to 10⁶, and you need to compute the answer using division modulo 10⁹+7.

Open Cup 2018-19 Grand Prix of Moscow was the last Open Cup round before the ICPC 2019 World Finals (results, top 5 on the left). Moscow SU team was setting the problems, but many other top ICPC teams competed. Three future gold medalists appear on the screenshot on the left :) Team Past Glory was head and shoulders above everybody, being the only team to finish all 13 problems, and doing it in just 3:40. Amazing dominance!

Thanks for reading, and check back for more.

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!

ICPC 2019 World Finals mirror stream

ICPC 2019 World Finals take place tomorrow on Thursday at approximately 11:30 Porto time (click for other timezones). Just like last two years, we'll try to solve it in parallel with tourist and Endagorion, and stream the process, assuming the problems will be available for submission on Kattis.

Tune in on Youtube!

A painful week

TopCoder SRM 752 was the first round of the last week (problems, results, top 5 on the left, analysis). rng_58 maintained his advantage in the race for the third TCO19 spot and was quite close to increasing his lead even further as he was just 4 points behind the first place before the challenge phase, and pashka was outside the top 10. However, tourist found 100 challenge points and won (congratulations!) and pashka found 50 challenge points and jumped into exactly 10th place, meaning that both rng_58 and pashka got 4 tournament points for this round.

Codeforces held its Round 545 early on Friday (problems, results, top 5 on the left, analysis). Only sunset was able to solve very tricky problem F, so even exceeding the memory limit in problem C (thanks to implementing an asymptotically optimal solution but with a huge constant both for time and memory) did not change the outcome. Congratulations on the win!

Open Cup 2018-19 Grand Prix of China wrapped up the week (results, top 5 on the left, analysis). All problems were solvable in this round, but all of them required quite a bit of thinking and quite a bit of coding, and also, as zeliboba quite succinctly formulated, had a few somewhat unnecessary corner cases. Team Past Glory still prevailed in those tricky conditions with the last problem accepted at 4:59. Well done!

Problem E in this round reminded me of my earlier post where I tried to describe a way to find dynamic programming states semi-automatically. The problem went like this: 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 idea to use dynamic programming is on the surface, but it's completely unclear how to achieve a manageable number of states. Do you see a way to find a small state space algorithmically?

Thanks for reading, and check back next week!

An oracle week

Last week had an Open Cup round for the fourth week in a row. Open Cup 2018-19 Grand Prix of America allowed teams from all over the world to participate in NAIPC 2019 (problems, results, top 5 on the left, NAIPC results, analysis). Just 3.5 hours were enough for team Past Glory to wrap the problemset up, a good 40 minutes before other teams could do the same. Congratulations on the win!

In my previous summary, I have mentioned two (in some sense three :)) problems. The first group was from the AtCoder World Tour Finals: consider an infinite 2D grid, where each cell can be either black or white. Initially, exactly one cell was black, and then we repeatedly applied the following operation: take some integers x and y, and invert the color of three cells: (x, y), (x+1, y) and (x, y+1). You are given the set of black cells in the final state of the grid. There are at most 10⁵ black cells in C1 and at most 10⁴ in C2, and each black cell has coordinates not exceeding 10¹⁷ by absolute value. Your goal is to find the coordinates of the only cell that was black originally. In problem C1 you know that its y-coordinate was 0, and in C2 there are no further constraints.

A typical idea in this type of problem is to come up with an invariant that is not changed by the operation and that can be efficiently computed for source and target positions. A typical invariant that plays well with inversions is boolean or bitwise xor. Let's say that a white cell is a 0, a black cell is a 1, let's also pick some set of cells S, then our invariant will be their bitwise xor (in other words, the parity of the number of black cells in S).

Not any set S works, though: we must make sure that for each invertible triple (x, y), (x+1, y) and (x, y+1) either 0 or 2 cells belong to S, to make sure the xor does not change when we invert the triple. Suppose that for some row y=y₀ the set S contains exactly one cell (x₀,y₀). The triple (x₀,y₀), (x₀+1,y₀), (x₀,y₀+1) must have 0 or 2 cells in S, and since (x₀,y₀) is in S but (x₀+1,y₀) is not, (x₀,y₀+1) must be in S. Applying a similar argument, we find that in the row y=y₀ exactly two cells must be in S: (x₀,y₀+1) and (x₀-1,y₀+1). Then we can compute which cells must be in S in the row y=y₀+2, and so on.

We can realize by looking at the resulting pattern, or by understanding what the process really is, that in general a cell (x₀-k,y₀+n) is in S if and only if C(n,k) is odd. And that, in turn, is true if and only if n&k=k, where & denotes bitwise and. There are still multiple ways to extend the set S to rows with y<y₀, so to avoid thinking about that we will always pick very small y₀ that is below all interesting points.

Now it is very easy to compute our invariant for the input set of cells: we need to count the parity of the number of such (x,y) in the set that (y-y₀)&(x₀-x)=x₀-x. But we know that the operations do not change the invariant, and that initially we had only one cell (x_A,y_A). This means that we have an oracle that can tell us whether (y_A-y₀)&(x₀-x_A)=x₀-x_A for any two numbers x₀ and y₀ such that y₀<=y_A.

In problem C1, we know that y_A=0, so we can just pick y₀ in such a way that -y₀ has all bits set except one, and then the oracle will effectively tell us the corresponding bit of x₀-x_A, so we can determine x_A in logarithmic number of queries.

In problem C2 the things are not so simple. However, suppose we have found some x₀ and y₀ such that (y_A-y₀)&(x₀-x_A)=x₀-x_A, in other words we made our oracle return 1. Now we can go from the highest bits to the lowest bit, and by calling our oracle 3 additional times checking what happens if we add 2^k to x₀ and/or subtract 2^k from y₀, we can determine the k-th bit of y_A-y₀ and x₀-x_A, then setting both to 0 and proceeding to the lower bits, and eventually recovering y_A and x_A.

The tricky part lies in the initial step of making the oracle return 1 for something: the probability of n&k=k for random n and k is roughly 0.75^{number_of_bits}, which is way too low to just stumble upon it. This is how far I got during the contest, so the remaining magic is closely based on the official editorial and my conversations with Makoto.

Instead of running the oracle for the set S with just one cell (x₀,y₀) in the row y=y₀, we will run it with the set S which has all cells (x₀,y₀) in the row y=y₀ where x₀ mod 3=u, l<=x₀<=r, where y₀, u, l and r are the parameters of the oracle. This requires counting the number of x₀ satisfying the above criteria and also the constraint (y-y₀)&(x₀-x)=x₀-x for each black cell in the input, which can be done by a relatively standard dynamic programming on the bitwise representation of x₀.

As we know, this will give us the parity of the amount of such x₀ that x₀ mod 3=u, l<=x₀<=r, and (y_A-y₀)&(x₀-x_A)=x₀-x_A. A crucial observation is: no matter what y₀ we pick, if l is very small and r is very large, then for at least one u from the set {0, 1, 2} this oracle will return 1! This can be proven by induction by y_A: when y_A=y₀, (y_A-y₀)&(x₀-x_A)=x₀-x_A only when x₀=x_A, so the oracle will return 1 when u=x_A mod 3 and zero in the other two cases. When y_A increases by one, given our C(n,k)-like propagation, every x₀ for which the oracle returns 1 contributes one to itself and x₀+1, which means that we go from parities (a, b, c) for the three remainders modulo 3 to parities (a+b, b+c, a+c), so from (1, 0, 0) to (1, 0, 1), and then to (1, 1, 0), and then to (0, 1, 1), and then to (1, 0, 1) and so on, and never get (0, 0, 0).

This means that in at most three attempts we can make this complex oracle return 1. Now (more magic incoming!) we can do a binary search: if for (y₀, u, l, r) the oracle returns 1, then it must return 1 for exactly one of (y₀, u, l, m) and (y₀, u, m+1, r). This way we can find a single cell (x₀,y₀) for which the oracle returns 1 in a logarithmic number of requests to the complex oracle, and then switch to using the simple oracle and proceed with reconstructing the answer as described above, completing the solution of C2.

I have also mentioned an Open Cup problem: you have some amount x of money between 0 and 1. You're playing a betting game where in one turn, you bet some amount y, and with probability p (p<0.5) your amount of money becomes x+y, and with probability 1-p it becomes x-y. Your bet must not exceed your current amount of money. Your goal is to reach amount 1. So far this setup is somewhat standard, but here comes the twist: your bets must be non-decreasing, in other words at each turn you must bet at least the amount you bet in the previous turn. In case you don't have enough money for that, you lose. What is the probability of winning if you play optimally? More precisely, what is the supremum of the set of probabilities of winning of all possible strategies? Both x and p are given as fractions with numerator and denominator not exceeding 10⁶, and you need to return the answer using division modulo 998244353.

You can find my approach to solving it in this Codeforces comment.

Thanks for reading, and check back for this week's summary!