July 2, 2022 Single Round Match 832 Editorials

FridayTheThirteenth

We can copy the month lengths from the statement straight into our code. Then we add isLeap to the number of days in February and we are ready to simulate. As a year only has a few hundred days (365 or 366), we can simply iterate over all months, for each month over all its days, and keep track of the day of the week that corresponds to the current day. Each time we are on the 13th of a month and the current day of the week is 5 = Friday, we increment the counter for that month. (Or simply set it to 1: a month cannot have more than one 13th.)

public int[] count(int firstDay, int isLeap) {
    int[] daysInMonth = new int[] { -1, 31, 28, 31, 30, 31, 30, 
                                        31, 31, 30, 31, 30, 31 };
    daysInMonth[2] += isLeap;
    int[] answer = new int[12];
    int currentDay = (firstDay+6) % 7;
    for (int m=1; m<=12; ++m) {
        for (int d=1; d<=daysInMonth[m]; ++d) {
            currentDay = (currentDay + 1) % 7;
            if (d == 13 && currentDay == 5) answer[m-1] = 1;
        }
    }
    return answer;
}

MaximumLottery

If we have N balls and draw K of them, there are (N choose K) equally likely outcomes.

The ticket cost we are looking for can be, in theory, computed by looking at each of those outcomes, computing the prize we get, and taking the average of all those prizes. The only problem with doing this is that it would take forever. We need to compute the same thing but in a more efficient way.

Suppose we order the balls according to the prize on them. (If there are ties, we break them arbitrarily but consistently: the ball that ends later in the sorted order is now considered greater from the previous one.)

For each draw one of the N balls is the largest one drawn. For each ball in the sorted order we can ask the following question: in how many of the possible draws is this ball the largest one drawn?

This question is easy to answer: we must select this ball and exactly K-1 of the smaller balls. If our ball is at 0-based index X in the sorted order, there are exactly X smaller balls and thus there are exactly (X choose K-1) draws in which ball X is the maximum.

Thus, the sum of prizes gained in the (N choose K) possible draws can be computed as the sum of prize[X] * (X choose K-1), over all x. To get the average (i.e., our return value) we then simply divide the sum by (N choose K).

public double ticketPrice(int[] balls, int K) {
    int N = balls.length;

    double[][] binomial = new double[N+1][N+1];
    for (int n=0; n<=N; ++n) for (int k=0; k<=n; ++k) {
        if (k==0 || k==n) binomial[n][k] = 1.;
        else binomial[n][k] = binomial[n-1][k-1] + binomial[n-1][k];
    }

    Arrays.sort(balls);

    double answer = 0;
    for (int n=0; n<N; ++n) answer += binomial[n][K-1] * balls[n];
    answer /= binomial[N][K];
    return answer;
}

CastleGuard

Simulating the process from the problem statement step by step is obviously too slow. There are many ways to speed it up, some more annoying to implement than others. The solution described below doesn’t have the best possible time complexity but it’s easy to implement and fast enough.

We’ll start by ignoring the initial visit to guard house 0 and simulating one sequence of commands. As the output of that simulation we will get the number V[x] of visits for each guard house x and additionally also the number D of the guard house where we end.

How to do this simulation easily: Maintain a counter of full circles made by the guard. (For these, direction does not matter, so one counter is enough. Each full circle simply increments the count for each guard house by 1.) Whenever simulating a command with absolute value X, add (X div N) full circles to the counter and then simulate the remaining steps sequentially. Once done, add the full circles counter to each guard house. This simulates a sequence of C commands in O(NC) time.

Each repetition of the sequence of commands will have the same effect, only rotated by D. One easy way to apply all R repetitions efficiently looks as follows: make an array of N zeros. For each repetition, increment the counter at the index where it starts. That is, increment 0, D, 2D, 3D, …, (R-1)*D. This only takes O(R) time, and once we do that, we know for each guard house the number of times we start the sequence of commands there. We can now take the array V that describes the effect of one sequence of commands and for each possible start we add a rotated copy of V, multiplied by the number of those starts, to the final result. This last step takes O(N^2) time.

int walkOnce(int N, int[] commands, long[] visits) {
    // simulate one sequence of commands, starting from guard house 0
    // return the final location
    long fullCircles = 0;
    int where = 0;
    for (int cmd : commands) {
        int step = 1;
        if (cmd < 0) { cmd = -cmd; step = -1; }
        fullCircles += cmd / N;
        cmd %= N;
        while (cmd-- > 0) {
            where = (where + N + step) % N;
            ++visits[where];
        }
    }
    for (int n=0; n<N; ++n) visits[n] += fullCircles;
    return where;
}

public long[] walk(int N, int R, int[] commands) {
    long[] visitsOnce = new long[N];
    int delta = walkOnce(N, commands, visitsOnce);
    
    long[] startHere = new long[N];
    int where = 0;
    for (int r=0; r<R; ++r) {
        ++startHere[where];
        where = (where + delta) % N;
    }

    long[] fullVisits = new long[N];
    ++fullVisits[0];
    for (int n=0; n<N; ++n) for (int i=0; i<N; ++i)
        fullVisits[ (n+i)%N ] += startHere[n] * visitsOnce[i];
    return fullVisits;
}

SparseOnes

This is a fairly standard counting exercise. 

First, we can reduce the task “sum [a,b)” to the task “sum [0,b) and then sum [0,a) and subtract it”. This gives us a potentially easier task in which we start at the beginning. Now we need to come up with a way of counting the numbers in large enough batches so that our solution runs in time.

Before we start, we can handle the 0 at the beginning: if A=0, set it to A=1 (we can just ignore the zero) and now discard the zero from the sequence, decrement A, decrement B and pretend the string starts with the first 1.

The numbers with no consecutive ones in binary are closely related to Fibonacci numbers. They will (soon) come up when we count them. Another nice connection is Fibonacci base representation: for any positive integer there is a unique way of expressing it as a sum of distinct non-consecutive Fibonacci numbers, and these sums map directly onto sequences of 1s and 0s with no consecutive 1s.

The primary way of dividing the given sequence of blocks is simply by length. The first block is 1, the second block is 10, the third is 100|101, and so on. For each block we can precompute its length and the total number of 1s it contains. Once we do so, when computing the sum for some [0,n) we can take as many full blocks as we can. Once we do so, we know how many digits we have left and we know the length L all those numbers have in binary.

The math for full blocks isn’t hard. Each number ends in 0 or 1. Before the 0 can be anything that doesn’t have consecutive 1s, before the 1 must be a 0 and then anything. Thus, starting from the third block, we can tell that each number is either a number from the previous block + 0, or a number from two blocks ago + 01. This gives us their count (a Fibonacci number), their total length, and also the total number of 1s they contain.

Another way of counting the same thing is by looking at the beginning of the numbers in a block instead of their end. This will be useful for the last, partially-used block. The numbers in a block all start 10. What follows are the numbers from all previous blocks (including the initial 0), just padded with zeros to the same length. For example, the block of length-6 numbers begins 100000|100001|100010|100100|100101|… Thus, we can now do the same thing recursively: among our length-6 numbers, do we still have all made from numbers in length-1 block? length-2? and so on. Just remember to add the extra 1s for the common prefix of each processed number.

Finally we may be left with a number of which we only take the first few binary digits. If we know both the block and the offset, we can explicitly construct the number and examine its bits.

PopChartDominance

The key trick towards an easy solution is to realize that if a range contains five occurrences of an artist (at a, b, c, d, e), the distance e-a we seek can also be expressed as (e-d)+(d-c)+(c-b)+(b-a), i.e., as a sum of distances between all pairs of consecutive occurrences that fall into our range.

In other words, imagine that we have points 0 to N-1 on a line, and that for each artist we draw a line segment between each pair of consecutive points that belong to this artist. This gives us a collection of O(N) line segments. Each query then becomes “what is the sum of lengths of all segments that fully lie within this interval?”

We will answer all queries while iterating through A once from left to right. Whenever we encounter the end of a segment, we’ll store its length at its input coordinate. And whenever we encounter the endpoint of a query [lo,hi), we need to compute the total length of all segments that started at lo or later and already finished. This answer is simply the sum of all lengths remembered at coordinates >=lo, and we can get it efficiently by remembering these lengths in a Fenwick tree.

The final time complexity is O((N+Q)*log N).