December 4, 2021 Single Round Match 819 Editorials

As you may be able to tell, one or two of the problems in this SRM are leftovers from the preparation of TCO 2021 onsite finals.

DecimalCoins

Suppose we have A coins worth 1 each. Using these, we can pay any amount from the range [0,A].

If A < 9, the larger denominations are useless: we cannot pay the sum A+1 regardless of what bigger coins we have.

If A >= 9, let’s now look at the coins worth 10 each. One such coin allows us to pay anything in the range [10,10+A], two such coins can be used to pay anything in [20,20+A], and so on. All of these ranges touch (for A=9) or overlap (for A>9). 

For example, if A=13 and B=2, we can pay any amount in [0,13] using only ones, any amount in [10,23] using a 10 and some ones, and any amount in [20,33] using both 10s and some ones. The union of these ranges is the entire range [0,33].

Hence, if we have B coins worth 10 each, we can now pay any sum in the range [0,10*B+A].

And we can continue in the same spirit with the higher denominations. The sum 10*B+A+1 is the smallest sum we cannot pay using tens and ones. If it’s less than 100, we are done. If it’s at least 100, we can also use the coins worth 100.

The implementation shown below implements these steps directly.

public int pay(int[] coins) {
    int[] denominations = { 1, 10, 100, 1000, 10000, 100000, 1000000 };
    int maxPossible = 0;
    for (int i=0; i<=6; ++i) {
        if (maxPossible >= denominations[i] - 1) {
            maxPossible += coins[i] * denominations[i];
        }
    }
    return maxPossible + 1;
}

Catchphrase

This problem can be solved using some ugly casework, but there is also a much more straightforward approach that has almost no special cases.

Note that there is only a small number of possibilities for what happens during the first two regular rounds + the first two bonus rounds. We can iterate through all of them. Each of them will give us one possible score at the end of the second bonus round (along with the number of puzzles player A solved so far).

At this point, both players can only gain points in multiples of 500. Thus, we can easily tell whether the current situation can lead to the given final scores: players cannot have scores bigger than the final ones, and for each player the number of points they still need must be a multiple of 500. And we can also easily tell how many additional puzzles player A will solve: (the number of points player A still needs) divided by 500.

In this way, we iterate over all possibilities for what could happen before round 3, we select those that could have produced the given final scores, and among those we pick the one in which player A solved the most puzzles.

In the program below we use a1, b1, a2, b2 to denote the numbers of puzzles solved by each player in each of the first two rounds, and bonus1, bonus2 are 1 if A got those points and 0 if B got them.

public int reconstruct(int Ascore, int Bscore) {
    int answer = -1;
    for (int a1=0; a1<=9; ++a1) for (int b1=0; a1+b1<=9; ++b1) 
    for (int a2=0; a2<=9; ++a2) for (int b2=0; a2+b2<=9; ++b2) 
    for (int bonus1=0; bonus1<2; ++bonus1) 
    for (int bonus2=0; bonus2<2; ++bonus2) {
        int partialA = 100*a1 + 200*a2 + 500*bonus1 + 1000*bonus2;
        int partialB = 100*b1 + 200*b2 + 500*(1-bonus1) + 1000*(1-bonus2);
        if (partialA > Ascore || partialB > Bscore) continue;
        int Aremain = Ascore - partialA, Bremain = Bscore - partialB;
        if (Aremain % 500 != 0) continue;
        if (Bremain % 500 != 0) continue;
        answer = Math.max( answer, a1 + a2 + bonus1 + bonus2 + Aremain/500 );
    }
    return answer;
}

MagicTrickWithCuts

The cut between the top part and the middle part will (almost) always be somewhere in the segment of hearts. Thus, the spectator’s first card is one of the hearts.

Additionally, if the spectator’s card is the, for example, 9th heart, this means that 8 hearts end in the top part and the remaining 13-8 = 5 hearts are in the middle part.

In the final deck, the original middle part forms roughly the top third, and the original top part forms roughly the bottom third. We cleverly separated them from each other by inserting the original bottom third (that contains no hearts at all) between them. Thus, we can very reliably tell which hearts belonged to which part of the original deck. (For example, “all hearts that are in the top half of the final deck are the ones that belong to the middle part, and all hearts in the bottom half are from the top part” is an almost 100% correct heuristic.)

The spectator’s first card is simply the smallest of the hearts in the original middle part, which is (almost always) the smallest of the hearts in the top half of our deck. Alternately, we can determine the spectator’s first card by counting hearts in either half of the current deck.

Now note that once we know the spectator’s first card, we can use it to determine their second card.

Note that before the cuts there were exactly 10 cards above the first heart. Thus, if we know that the spectator’s first card is the 9th heart, we know that the top part is 8 hearts + 10 non-hearts = 18 cards total. These 18 cards are now on the bottom of the deck, and spectator’s second card is the first of them – that is, the 18th card from the bottom of the deck.

In the code we take care of a special case: sometimes we can be really unlucky and the spectator will make the cut outside our range of hearts. This case is rare enough in terms of “it won’t affect our success rate enough”, but we still have to make sure that our code will not crash if the case occurs.

String solveOne(String deck) {
    int bottom_hearts = 0;
    for (int i=26; i<52; ++i) {
        if (deck.charAt(i) >= 'A' && deck.charAt(i) <= 'M') ++bottom_hearts;
    }
    
    // in the unlikely case where the cut goes below all the hearts,
    // give up, but still give a syntactically correct answer
    if (bottom_hearts == 13) return deck.substring(0, 2);

    char firstCard = (char)('A' + bottom_hearts);
    char secondCard = deck.charAt(42 - bottom_hearts);
    return "" + firstCard + secondCard;
}

public String solve(String[] queries) {
    String answer = "";
    for (String deck : queries) answer += solveOne(deck);
    return answer;
}

BinaryTreeAutomaton

There are two parts to the solution to this task. One is understanding how we can construct a maximum independent set in a tree, the other is learning how to implement such an algorithm using just the very restricted finite automaton we are given.

The key observation about independent sets is that in trees (any rooted trees, not just binary ones) we can construct it greedily by going from the leaves to the root and selecting each node that doesn’t have any selected child.

Proof: Take any optimal solution. Suppose it contains a node X with no selected children that isn’t selected. Then node X must have a selected parent (otherwise we could select it and the solution would not be optimal). But then we can deselect the parent of X and select X instead. We can repeat this process as long as such a node exists. This process is clearly finite (the sum of depths of selected nodes increases), and once it terminates, we must have the solution produced by our greedy algorithm.

Below we show one possible way how to program the automaton to solve this task. The resulting program will not be the shortest and simplest possible – instead, we are aiming for the most straightforward translation of the above algorithm into automaton code.

The automaton will essentially perform a depth-first search of the tree. The initial state (“solve”) is the state in which we want the automaton to construct the greedy solution for the entire subtree rooted in the node where we are. This can proceed as follows:

1. Go to the left child in the state “solve” to solve the left subtree. Use a mark in the current node to note that you already did this.
2. Go to the right child in the state “solve” to solve the right subtree. Use a mark in the current node to note that you already did this.
3. Check whether your left child is selected. If it isn’t, check whether your right child is selected. If it isn’t either, select yourself.
4. Return to your parent.

In step 3 the program shown below uses some extra states to transfer information. For example, when we go to check our left son, we move left and set the state to “checkl”. If we are in the state “checkl”, we check whether the current node is selected, and then we move back to our parent and set the state to “goodl” or “badl” accordingly.

solve
# logic to check whether the left child is selected
solve:bl:checkl::l
solve:bL:goodl::
checkl:s:badl::p
checkl:S:goodl::p
badl:p:solve::p
badl:P:terminate::
goodl:r:checkr::r

# logic to check whether the right child is selected
goodl:R:goodr::
checkr:s:badr::p
checkr:S:goodr::p
badr:p:solve::p
badr:P:terminate::
goodr:p:solve:s:p
goodr:P:terminate:s:

# recursive calls to solve the left and right subtree
solve:aBr:solve:b:r
solve:aBR:solve:b:
solve:Al:solve:a:l
solve:AL:solve:a:

If we are willing to spend a bit more time thinking, we can be awarded by a simpler implementation. We don’t really need all those pesky extra states. What we can do instead is to select the node when we enter it for the first time. Then we continue with the DFS to recursively solve each subtree. And the only extra thing we’ll do is that whenever we are returning up from a node that remained selected, we use an extra state (“unset” below) to tell our parent that they should no longer be selected. The final implementation is quite pretty and straightforward:

solve
unset:s:solve:s:
unset:S:solve::
solve:sbp:unset::p
solve:sbP:terminate::
solve:bp:solve::p
solve:bP:terminate::
solve:ar:solve:b:r
solve:aR:solve:b:
solve:l:solve:sa:l
solve:L:solve:sa:

PaintballFreeForAll

This is a fun little problem. The most fun part isn’t its solution but the fact what happens as N grows to infinity. The probability of having a winner does not converge to any specific value. Instead, it oscillates within a finite interval of values (and if we make the x axis logarithmic, we will get a plot that converges towards periodic oscillations).

There are multiple ways how to compute the required probability in some reasonable polynomial time. Below we explain one of them. 

We will use dynamic programming. The main thing we want to determine is, for each X from 0 to N, what is the probability dp[X] of getting a win if we start the tournament with X players. In order to determine these values, we need the transition probabilities: what is the probability pp[X][Y] that we’ll go from X players to Y in one round?

We can count these probabilities using an inner dynamic programming. Imagine that the players shoot one at a time. Once we have processed some number A of players, the current state can be described by two numbers B and C: the number of already processed players who have been hit, and the number of pending players who have already been hit. Once we know the probability for some state (A,B,C), we can calculate in constant time what can happen when the next person shoots.

First, this person can be already be shot. (The probability of this can be determined from A and C. If they are shot, we have just moved one shot person from the unprocessed to the processed group of people.)

Then, this person targets someone. (We can compute the probability with which they target a person in each group that wasn’t shot yet.) Finally, this person shoots and possibly hits a new person.

One final part of the solution is dealing with the situation where the people are poor shots and nobody gets hit. If P < 10000, there can be rounds in which nobody is removed from the game. But this is a fairly standard complication that is easily resolved: we can simply ignore this possibility and rescale all other probabilities.

For example, suppose we have a random process that is in a state A and in each step it will remain in A with probability pa, go to B with probability pb, and go to C with probability pc. The cases where we eventually go to B and the cases where we eventually go to C clearly have the ratio pb : pc. Thus, the probability of eventually going to B is pb / (pb + pc) and the probability of eventually going to C is pc / (pb + pc). Equivalently, the two probabilities are pb / (1 – pa) and pc / (1 – pa), this is the form that generalizes nicer to more than two options.