May 16, 2022 Single Round Match 829 Editorials

GameShowTotal

With N questions there are 2^N possible patterns of correct and incorrect answers. The key observation in to take a closer look at the last incorrect answer. After this answer the bank is sure to be empty – and that means that everything that happened earlier does not matter. And what happens after that moment? Well, as this was the last incorrect answer, the remaining ones must all be correct, meaning that the player will get the money for all those questions.

Hence, each possible total is the sum of some suffix of the given sequence A. Notably, this includes both the empty suffix (the last answer was wrong and the player gets nothing) and the full sequence A (there were no incorrect answers, the player takes all the money).

Our implementation runs in O(N), but the constraints were so low that you could also sum each suffix separately.

public String verify(int N, int[] A, int W) {
    if (W == 0) return "possible";
    int total = 0;
    for (int n=N-1; n>=0; --n) {
        total += A[n];
        if (total == W) return "possible";
    }
    return "impossible";
}

NonbinarySearch

This is one of those problems that challenge you to decide how much you trust your intuition. The best solution is to always look into the middle, so when we are forbidden to do that, intuitively we should look as close to the middle as allowed. And this is indeed the correct strategy, so if you trusted your gut, you could have an easy and quick solution.

Of course, there are various ways to solve the problem, all the way to writing a solution that uses dynamic programming to essentially examine all possible strategies (but that one then needs to be pruned to fit into the time limit for larger values of N). Or, if you don’t trust your intuition, you can use the DP to locally test your greedy solution instead.

In this writeup we will explain why the greedy solution works.

Let B[x] be the optimal number of queries for nonbinary search on an array of size x.

Main theorem: The sequence B is non-decreasing.

Proof: By examining the first few values by hand we can verify that the first ten values of B are non-decreasing.

Now we proceed by doing a proof by contradiction. Let N >= 10 be the smallest value such that B[N] > B[N+1]. 

For an array of size N one option we have is to make the first query as close to the center as possible. As N is the smallest counterexample, we know that after we make that query, the worst case is that we are left with the longer of the two parts. The length of that part is K = (N div 2) + 1. Theoretically there could be an even better solution for N, but we can still make the conclusion that B[N] is at most B[K]+1.

But here’s the catch: regardless of what valid first query we make for N+1, the longer of the two remaining segments will contain at least K candidates. And again remember that N is the smallest counterexample, and all these lengths are at most N. Thus, for each of them we need at least B[K] additional queries, and hence B[N+1] is at least B[K]+1. And that’s the contradiction we were looking for.

Corollary: As we know that B is non-decreasing, we can now deduce that we should always make our query as close to the center of the array as allowed. (The worst case is always the case when we are left with the bigger “half” of the array, and the smaller we make it, the faster we can solve it. Both these claims directly follow from B being non-decreasing – can you see how?)

public int search(int N) {
    if (N <= 2) return N;
    return 1 + search((N+2)/2);
}

SnookerScoring

N=1 is solved by {1} and N=2 by {2}.

A single red followed by a single color can give us any value in the range [3, C+2].

Two reds followed by two colors give us anything in the range [6, 2C+4].

And so on.

For C >= 3 all these ranges touch or overlap, so with up to R reds we can produce anything in the range [3. R*(C+2)]. For C=2 we have a single gap at N = 5, but that is easily solved by {1,3,1}. 

All that remains are values greater than R*(C+2). These must include the “final cleanup”, i.e., playing some colors after all reds are gone.

Note that conveniently R is at least 10 and thus the range of values doable using (red, color)^k sequences is much longer than 10. We can construct the full solution for any N > R*(C+2) by first greedily playing colors until we get to or below R*(C+2), and once that happens, we prepend the (red, color) sequence that scores the rest we need.

OK. Now we have shown that all sums can be constructed, but it still pays off to think a little more about the problem – in particular, to find a nice way how to construct a sequence of (red, color) balls with a given sum. In the solution below we do this by first finding the shortest length that works and then decreasing the colors’ values until the sum fits.

To conclude this writeup, note that the number of valid inputs is quite small, so you can stress-test your solution locally to make sure that it returns a solution in all possible cases.

def doRedColor(N, C):
    # produce N using (red, color) pairs only
    answer = []
    while sum(answer) < N: answer.extend([1, C+1])
    while sum(answer) > N:
        for i in range(len(answer)//2):
            if answer[2*i+1] > 2:
                answer[2*i+1] -= 1
                break
    return answer

def scoreN(N, R, C):
    if N <= 2: return [N]
    if N == 5: return [1,3,1]
    suffix = []
    next_color = 2
    while N > R * (C+2):
        suffix.append(next_color)
        N, next_color = N-next_color, next_color+1
    return doRedColor(N, C) + suffix

QuestionOrder

This task is inspired by an actual game show, namely season 5 of the US version of the show “Are you smarter than a fifth-grader?” This show features exactly the mechanism described in the statement, and finding the right order in which one should play the questions is surprisingly non-trivial.

We can start with two straightforward observations: impossible questions go first, certain questions (100% ones) go last. But how do we order the rest?

Take a look at how the expected value is calculated once we fix some order of questions. Suppose A and P are rearranged to the correct order, with index 0 being the question asked first, and that P are now actual probabilities (with 1 instead of 100 being a certain event). Then:

• We get the A[N-1] for the last question with probability P[N-1].
• We get the A[N-2] for the penultimate question with probability P[N-2] * P[N-1].
• And so on: for each question we get its money if and only if we answer all questions from that point to the end of the game correctly. The probability of that is the product of the individual probabilities.
• The expected amount of money earned from a question is its value multiplied by the probability that we get that money. By linearity of expectation, the total expected amount is the sum of that over all questions.

A very useful trick to discover a greedy solution when one exists is to start with the following observation (that’s true in all order optimization problems, not only those that are actually solvable greedily): In an optimal solution swapping two adjacent elements can never improve the solution.

Let’s observe what happens if we swap two consecutive questions x and x+1. Clearly, this has no influence on questions asked later. The important thing to notice is that it also does not influence the questions asked earlier: for those, we have to correctly answer both x and x+1, regardless of their order. Thus, only the expected profit from x and from x+1 will change.

If they are asked in their current order, we will get A[x]*P[x]*P[x+1]*Q + A[x+1]*P[x+1]*Q money from these two questions. (Here, Q is the product of probabilities for all following questions.)

After the swap, we would get A[x+1]*P[x]*P[x+1]*Q + A[x]*P[x]*Q money in expectation. When is the second value greater?

We can simplify that comparison to the following form: 

A[x] + A[x+1]/P[x] < A[x+1] + A[x]/P[x+1]

(we just divided both sides by P[x]*P[x+1]*Q)

And that can be further rearranged to get: A[x+1] * P[x+1] / (1 – P[x+1]) < A[x] * P[x] / (1 – P[x]).

Now we have only values associated with question x+1 on the left, and the same formula using only values associated with question x on the right. And that means we are lucky: this ordering happens to be (quite obviously) transitive. Thus, we just discovered that in order to maximize our profit, all we need to do is to answer all questions ordered according to A[x] * P[x] / (1 – P[x]).

void swap(int[] A, int[] P, int y) {
    int t;
    t = A[y]; A[y] = A[y+1]; A[y+1] = t;
    t = P[y]; P[y] = P[y+1]; P[y+1] = t;
}

public int maxExpProfit(int[] A, int[] P) {
    int N = A.length;
    for (int x = 0; x < N; ++x) {
        for (int y=0; y < N-1; ++y) {
            if (P[y] > 0 && P[y+1] == 0) { swap(A,P,y); continue; }
            if (P[y] == 100 && P[y+1] < 100) { swap(A,P,y); continue; }
            if (A[y] * P[y] * (100 - P[y+1]) > A[y+1] * P[y+1] * (100 - P[y])) {
                swap(A,P,y); continue; 
            }
        }
    }

    long answer = 0, probAlive = 1, mod = 1_000_000_007;
    for (int n=N-1; n>=0; --n) {
        answer *= 100;               answer %= mod;
        probAlive *= P[n];           probAlive %= mod;
        answer += A[n] * probAlive;  answer %= mod;
    }
    return (int)answer;
}

UpdownNumbers

The key tool here is one specific algorithm to compute the longest increasing subsequence: the algorithm where we process the input sequence online and maintain a vector of values: for each length x, the smallest possible value v[x] that can appear at the end of an increasing subsequence of length x. This vector contains all useful information about the prefix we already processed. And notably the vector is always sorted, so there can only be at most 2^10 such vectors: each of the values 0 to 9 either does or does not appear.

We can now do dynamic programming. The states will be triples (the number of digits we already processed, the current state of the LIS algorithm, and the analogous current state of the LDS algorithm). For each such state we will compute the number of ways in which it can be reached. The cleanest way to do this is to do a forward DP, starting from the nine one-digit number. For each reachable state we then try appending each of the 10 possible digits and for each of them we simulate the next step of the LIS and LDS algorithm to find their next states.

This algorithm is already fast enough to conveniently precompute answers to all test cases.

Alternately, we can make two additional observations: first, we can merge all states in which the LIS/LDS is already long enough into a single state “we are done”, and second, we can note that not all combinations (stateLIS, stateLDS) are possible. In fact, in the worst case (S = 10) only about 170k out of the theoretically possible 1M combinations of states are reachable. If we precompute those states and do DP over those states only, the solution becomes fast enough to run within the time limit without the need for precomputing answers.