June 9, 2021 2021 TCO Algorithm Round 2B Editorials

AlternateOddEven

The numbers with alternating odd and even digits are easy to count: we have 9 possibilities for the first digit (anything other than zero) and then five possibilities for each of the following digits (the five digits of the opposite parity from the previous one). Thus, there are 9 * 5^(L-1) such numbers of length L.

Once we know this, we can compute the count of our numbers for length 1, 2, … until we have at least K of these alternating numbers. Then we know that the last length we processed is the correct length of the K-th number. We can then subtract the count of all shorter numbers from K to know the ordinal number of our answer among the numbers of the correct length.

For example, there are 9 one-digit, 45 two-digit, and 225 three-digits numbers that alternate odd and even digits. If we are looking for the 62nd number in our list, 9+45 is still less than 62 but 9+45+225 is already enough, so we see that our number has three digits. Now we compute 62 – 9 – 45 = 8, which tells us that we want the 8th smallest three-digit number with our property.

And next we can use the same technique to construct the number from the left (from its most significant digit) to the right.

The first digit is a special case, as all digits from 1 to 9 are eligible. If the current length is L, we know that there are exactly 5^(L-1) numbers beginning with each of these digits. So if the updated K is at most 5^(L-1), our number begins with a 1, else if it is at most 2*5^(L-1) it begins with a 2, and so on.

For each of the following digits we have only five options, and each of those five options starts exactly 5^(L-1-x) numbers, where x is the number of digits we already placed.

To continue our example, there are 25 three-digit alternating numbers that begin with a 1. As our updated K is 8 <= 25, the number we seek starts with a 1.

The second digit can now be 0, 2, 4, 6, or 8. For each of them there are 5 such numbers (i.e., 5 that start “10”, 5 that start “12”, and so on.) As our K is still 8, we see that our number is the third such number in the second block of 5. Thus, the number we seek begins “12” and it is the 8-5 = third such number. One last step will then tell us that our number is 125 (as 5 is the third odd digit).

(Note that after we determined the first digit, we can view the rest of the solution simply as writing K-1 in base 5 and then using its digits to determine the digits of our result.)

ConstantSegment

Clearly, if we want to have (at least) K consecutive robots of some type x, we should not send home any robots of type x. In the optimal solution the robots of type x are still in their original relative order, and thus the optimal solution is surely formed by some K robots of the same type who follow each other in the input sequence if we ignore the other robot types.

If we know the indices x and y of the first and last of those K robots in the original sequence, we know the answer. This is because the range [x,y] contains exactly y-x+1 robots in total, K of those are our robots, and therefore there must be exactly y-x+1-K robots of other types we want to send away.

What this observation tells us is that an equivalent way of stating our problem is “find the shortest segment of the original sequence that contains K robots of the same type”.

Probably the easiest way to solve this problem looks as follows:

• For each robot type, make a sorted list of indices at which we have robots of that type. This can be done in linear time by simply going through the given sequence P and always appending n to the end of the list for type P[n].
• For each robot type (that has at least K robots), look at all possible pairs of robots of this type that start and end a range of exactly K such robots: that is, the first+Kth of these robots, the second+(K+1st), and so on.

The entire solution runs in O(M+N) as in the second step each robot is only considered as the beginning of a segment at most once.

IncorrectCancellation

The constraints in this problem are intentionally not that high, so it should be possible to apply a reasonable amount of brute force. Below we describe one possible approach that has a reasonably small search space and a reasonably simple implementation.

First, generate all possible denominators D2 of the reduced fraction. Each D2 can be obtained by crossing out some but not all digits of D. As the original D has at most seven digits, there are at most 2^7 – 2 = 126 possible D2. Out of those, at most seven have six digits each, and all others are smaller than that. (If you are generating them as strings, make sure to skip options with leading zeros.)

For each D2, try all possible N2 in (0,D2). This gives us at most several million different possibilities for (N2,D2), so we can afford to spend enough time on each of them. This can be optimized even further by only directly iterating over those N2 for which N is an integer, but this optimization should not be necessary.

The equation N/D = N2/D2 gives us N=(N2*D)/D2. Whenever this gives us an integer, we have a candidate pair of fractions we need to check. We already know that we can get from D to D2 by erasing some digits (this is how D2 was generated), all that remains is to check whether we can get from N to N2 by erasing those same digits. This check can be done as follows:

• Count the number of occurrences of each digit in D and subtract their occurrences in D2. This gives you the multiset of digits we are erasing in the denominator.
• Count the number of occurrences of each digit in N and subtract their occurrences in N2. This gives you the multiset of digits we are erasing in the numerator.
• Those two multisets have to be exactly the same. (Note that in some cases we can get a negative count in the second step, if N2 has some digits that are not in N. There’s no need to check for this explicitly, as such an array of counts will never match the array we got in the first step.)
• Check whether N2 appears as a subsequence of N.

Note the last step. This is necessary to make sure that we can actually obtain N2, and not just some other number with the same multiset of digits as N2. For example, consider D = 1285. For this D we will eventually test the pair of fractions N/D = 1028/1285 and N2/D2 = 20/25. The multisets of erased digits match (we are crossing out 1 and 8 from both the numerator and the denominator of the original fraction), but if you actually do cross those digits out, you will get 02/25 and not the 20/25 we need.

(Leading zeros for N2 are not an issue – as we generated all possible N2 and the corresponding N as integers, they don’t have leading zeros.)