June 24, 2023 SRM 847 editorial blog post

GivenDigitSum

Let’s first focus on creating the smallest possible number with D digits and the given digit sum S. We can easily create it as follows: imagine that we have D bins (one for each digit). We now need to distribute S marbles into those bins. We need to follow two rules:

• We need to place at least one marble into the bin for the most significant digit (because it must be non-zero).
• We can place at most 9 marbles into each bin (no digit can have a value greater than 9).

As long as we follow the above rules, each possible distribution of the S marbles will give us one possible D-digit number with digit sum S.

When comparing two D-digit numbers, we look for the most significant place where they differ and the one with the smallest digit in that place is the smaller one. As we want to minimize our number, we need to keep the leftmost (i.e., most significant) digits as small as possible. We can achieve this simply by placing the marbles greedily: after we place the one forced marble into the most significant bin, we then take the remaining S-1 marbles and start filling them into bins starting from the least significant one. Only when a bin becomes full we move to the next one.

For example, if D=6 and S=12, we proceed as follows:

• We will start by placing one marble into the most significant bin: {1, 0, 0, 0, 0, 0}.
• Then we place 9 marbles into the least significant bin: {1, 0, 0, 0, 0, 9}.
• Then we place the remaining 2 marbles into the next bin: {1, 0, 0, 0, 2, 9}.

We can use an array of integers to represent the bins, and once we are done, we can easily convert its content into a number. In the above example, we get that the smallest number with 6 digits and digit sum 12 is 100,029.

There is one final step we need: As we need to have digit product zero, we need to have at least one zero digit in our number. This cannot be the most significant digit, so clearly the best we can do is to have the second most significant digit equal to zero. Hence, when we use the algorithm described above, we simply skip the second most significant bin so that it remains at zero.

EraseThird

We can solve this problem using brute force. And we could do that even for much longer strings – as we reduce the length of the string by a constant fraction in each step, the entire process from the original string to a single letter always only requires a number of steps that is logarithmic in the length of the original string.

Probably the simplest possible solution is one that never uses operation ‘2’. A big advantage is that if we only use operations ‘1’ and ‘3’, we can be sure that we never remove an empty part.

We’ll now show that any original string can be reduced to any of its letters using only operations ‘1’ and ‘3’.

Pick the letter you want to end with and imagine that it’s colored red. Now, as long as you have more than one letter left: if the red letter is in the first third of your current string, discard its last third, and otherwise discard its first third. Each such step decreases the length of your current string and keeps the red letter in it. Thus, after finitely many such steps you must end with just the red letter.

We repeat the above process up to 26 times: once for each letter that occurs in the given string. (If a letter has multiple occurrences, we pick an arbitrary one of them to be red.)

Lasso

The first step of the solution is to determine, for each horse, the number of moves it needs to escape the corral.

One option to do this is by using BFS backwards. Start by initializing all cells around the corral to distance zero. Then, from all of them at once start the BFS. This way you will compute for each cell in the corral the minimum number of moves to reach that cell from the outside, and as knight moves are reversible, that’s the same as the minimum number of steps to reach outside from that cell. This approach clearly works and it’s reasonably simple but it still requires quite a lot of typing.

Another, much simpler approach is to realize that we can tell the optimal number of moves for each horse in constant time without the BFS. Take any horse. Count the number of squares it would need to move in each of the four cardinal directions in order to get out of the corral. Let x be the minimum of those four distances. The claim is that this horse needs exactly y=ceiling(x/2) moves to leave the corral. Why? Each move changes each coordinate of the horse by at most 2, so after fewer than y steps both coordinates of the horse must still be inside the corral. And if the horse makes exactly y moves such that in each of them it moves two cells in the direction towards the nearest corral wall, after those y moves it will traverse at least x cells in that direction, and that surely puts it outside the corral.

The rest of the task is now pretty straightforward. We need to make sure that no horse escapes. It is clear that the cowboy can be greedy and catch horses ordered by their escape time. For each horse we now know the order in which we will catch it (breaking ties arbitrarily) and thus we get one inequality L must satisfy: the time at which we catch this particular horse must be less than or equal to the time of its escape. The most strict of those N inequalities gives us the L we should return.

The above can also be done in a compressed form: for each number of moves only the last horse matters. Thus, we can simply iterate over all possible numbers m of moves, and for each of those we know that if there are x(m) horses that can escape within m moves, we need to have L <= m / x(m) to make sure that the last horse which needs exactly m moves to escape gets caught.

NoQuickGrowth

Imagine that the blaster just replaces the blasted item with a wildcard. The claim now is that if the remaining elements of the sequence don’t trigger the “quick growth” condition, we can always fill in the wildcards to get a valid sequence.

This should be easy: wildcards at the beginning can be replaced by +infinity (or, if you prefer, the same value that follows them). And if you have a value x followed by a sequence of wildcards, you can replace them with the largest possible values they have: x+10, x+20, x+30, and so on. It’s easy to verify that the resulting sequence will be valid.

Thus, in order to minimize the number of blaster uses we simply need to maximize the number of elements we don’t blast.

When is a collection of elements we did not blast valid? It shouldn’t be hard to see that what we have here is some slightly more complicated version of a non-increasing subsequence of the original sequence.

The condition S[j] – S[i] <= 10(j-i) can be rewritten as S[j] – 10j <= S[i] – 10i.

Thus, if we create a new sequence T where T[i] = S[i] – 10i, the valid subsets of elements correspond exactly to non-increasing subsequences in T. We can use the standard O(n log n) LIS algorithm on T and we are done.

TwoClassTrip

Let d(n) denote the number of divisors of n.

If we know the class sizes (let’s denote them x and y), how many ways are there to select the team sizes? A valid team size must divide both x and y. In other words, for each class separately the team sizes they can choose are precisely the divisors of gcd(x,y). Thus, each class has d(gcd(x,y)) possible team sizes, which gives us d(gcd(x,y))^2 combinations.

We are therefore interested in the following sum: sum(x=1..n) sum(y=1..x) d(gcd(x,y))^2.

Let’s simplify it. First, instead of the triangle we can sum over the entire square. That’s usually easier to evaluate. Indeed: if we know the value sum(x=1..n) sum(y=1..n) d(gcd(x,y))^2, we can get the sum we want by observing that the terms are symmetric (gcd(x,y) = gcd(y,x)) and thus all we need is add the sum of the main diagonal to the sum of the square and then divide by 2. The main diagonal is easy: that’s just sum(x=1..n) d(x)^2.

So, let’s do the sum over the entire nxn square. We can split the sum into bins according to the value of gcd(x,y). For each z, let’s denote c(z) the number of pairs (x,y) such that 1 <= x,y <= n and gcd(x,y) = z. If we knew the values c(z), we could evaluate our sum easily: it’s simply sum(z=1..n) d(z)^2 * c(z).

And we can indeed compute these values efficiently. One of many possible ways of getting them is from the Möbius inversion formula: c(z) = sum(k=1..n/z) mu(k) * (n div (k*z))^2.

Everything we need (i.e., the values of the divisor function d(1) to d(n) and the values of the Möbius function mu(1) to mu(n) ) can be precomputed efficiently. The limits are such that an O(n log n) solution should be sufficient. Similarly, the time complexity of calculating all the values c(z) using the above formula is O(n log n), as the n-th harmonic number is proportional to log n.

Even though it wasn’t needed, the entire problem can be solved with a better time complexity than O(n log n). What’s the best solution you can get?