November 10, 2022 Single Round Match 841 Editorials

DividingCandy

We can use brute force to solve this problem, but we need to be careful not to use too much of it (100,000^2 is too much) and not to forget any corner case. We can proceed as follows:

If all kids share the same type (L=0 or D=0), it’s fairly easy. We have C candies and N=L+D kids, we want to divide the candies evenly. The best we can do is give X = (C div N) candies to everyone. If X = 0 there is no solution, and if X > 100,000, we can only give 100,000 to everyone because of the upper bound.

What can we do if we have kids of both types? We can use brute force to try all possibilities for kids of one type. For example, let’s iterate over all X from 1 to 99,999 and let’s see what happens if each of the kids who don’t care about strawberries get exactly X candies. We can reason as follows:

• We need X*D candies for these kids.
• We are left with R = C – X*D candies.
• If R < 0, we clearly don’t have enough candies, so this option does not work.
• Each of the L candies who like strawberries can get at most Y = (R div L) candies.
• If Y <= X, we don’t have enough candies.
• If Y > 100,000, we can only give them Y = 100,000 candies.
• If we got here, we have a valid solution that distributes X*D + Y*L candies. We pick the best of these solutions over all X.

DhakaBanner

We can always remove everything from the banner (N operations) and add the letters we need (5 operations).

If there is at least one of the letters D, H, A, K on the banner, we can do better: remove the rest (N-1 operations) and add the other four letters (4 operations).

If we want an even better solution, we must reuse at least two letters from the original banner. One good way to find the best such solution is to iterate over all options which two letters to keep. As soon as we decide which two letters we want to keep and which two letters of the final word they are, everything is now uniquely determined: we can compute where the other letters of DHAKA will lie, and for those that are at integer offsets we can check whether they are also available at that exact spot of the banner. If they are, we get to reuse more than two letters. The best solution can be found by iterating over all questions of the form “what happens if I take these two letters?” and picking the one that actually lets you reuse the most.

Here’s how the math works: Suppose we found one option that “DHAKA”[a] = banner and “DHAKA”[b] = banner[d] for some a<b and c<d (such that d-c is at least equal to b-a). If the chosen two letters of “DHAKA” start at coordinates c and d on the banner, where do the other letters of “DHAKA” start?

When we go from letter a to letter b in “DHAKA”, we are moving b-a letters to the right. Thus, on the banner we will make b-a equal jumps. These jumps need to cover the distance d-c. Then, clearly, the length of each jump is x = (d-c)/(b-a).

The first letter of “DHAKA” starts at coordinate c – a*x on the banner. Then, in general, the character “DHAKA”[i] appears at the coordinate c – a*x + i*x. If this is an integer between 0 and length(banner)-1, inclusive, it falls exactly onto one of the existing letters of the banner, and we can check whether it matches what we need. We can keep all the matching letters and only remove and replace the rest.

DiceOperation

Let P[b] be the probability that bit b of the resulting XOR has value 1. Then, with probability P[b] this bit contributes 2^b to the result, and with probability 1-P[b] it contributes nothing. By linearity of expectation, our answer is simply sum( P[b] * 2^b ) over all b. As for b >= 30 we have P[b] = 0 (we cannot roll numbers with that bit set), this is a small finite sum.

Values P[b] are easy to compute.

We can start with a single die and ask what is the probability that an x-sided die rolls a number with bit b set.

Imagine the numbers 0, 1, 2, …, x written in binary. If we focus on bit b and look at them in this order, we’ll see alternating blocks of 2^b zeros and then 2^b ones. Thus, the sequence is periodic with period 2^(b+1). We can divide its length (x+1) by the length of the period to get the number of full periods, and then we can look at the remainder in that division to check whether the incomplete period at the end already reaches the next block of ones. This gives us a simple way of calculating the answer for one die.

There are multiple options for going from there to N dice. As in this problem we have N <= 10, we can actually use brute force: we can generate all 2^N patterns of zeros and ones (choosing which dice will and which ones won’t have this bit set), take those where the total number of ones is odd, and for each of them calculate the probability that this exact pattern will be rolled. Another approach (that is both simpler and faster) is to use a very simple form of dynamic programming. In the beginning we are sure that the bit is zero in the xor if we have no dice. Now we can add the dice one at a time and recompute the probabilities that the bit is zero/one in the xor of the already processed dice. (With the new die there are two ways to have xor contain that bit: either it didn’t and we rolled a 1, or it did and we rolled a 0.)

InTheLead

The current state of a competition can be described by six numbers: the number of problems each team already solved (a,b,c that are at most equal to the elements of solved[]) and the number of times each team was already in the lead (d,e,f that are at most equal to the elements of lead[]). In particular, note that by observing a,b,c we can tell whether some team is currently in the lead (i.e., they are the unique maximum) or not (more than one maximum).

One additional observation needed is that the numbers d,e,f cannot all be large. One possible upper bound is that the SUM d+e+f cannot exceed the MAXIMUM of a,b,c. Why? Because at most one team can be in the lead with 1 problem solved, at most one team with 2 problems solved, and so on. 

With elements of solved[] being <=24 this means that any input with sum(lead) > 24 is impossible. Clearly the worst case now is solved[] = {24,24,24} and lead[]={8,8,8} which leads to 25^3 possible triples (a,b,c) and only 9^3 possible triples (d,e,f). This is only about 11M states (as opposed to the ~244M we would have without this optimization).

We can now do a simple forward dynamic programming: from each state we try appending each possible next action and update the number of ways for each new state reached this way. There are at most three options to consider: each team that still has some problems left to solve can be the one who solves the next problem in chronological order. For each of these choices (i.e., whether to increment a, b, or c) we can also determine whether the corresponding d/e/f is incremented (this happens if a/b/c just became the unique maximum) or not (otherwise).

RouteOrder

Route #0 is simply the lexicographically smallest out of all shortest paths. We can easily find it by running Dijkstra and being careful about the order in which we expand the nodes.

We will now incrementally build all the following routes until we either find the required one or run out of available routes.

Assuming that we already know routes 0 to k-1, what can we tell about route k? In general, it can have some common prefix with the previous routes, but at some point it must start to differ from all of them. Let’s consider the first such moment. At this moment it is already clear that regardless of what we append, the route will be new. Among all such routes we are clearly only interested in one: the one that’s the earliest among these – i.e., the route that now continues by taking the shortest available simple path from its current location to the finish (and of course, the lex min out of those if there are multiple shortest options).

This gives us a polynomial-time approach to find route #k: We will store the already found routes in a trie so that we know what prefixes they share. For each prefix of each previous solution – there are at most O(nk) of these – try all possibilities to take the first step that will make the new solution differ from all previous ones – O(n) options – and then finish that route by taking the shortest available path to the finish. Each of these options will give us at most one candidate, and the best of those (if any) is the route we seek.

Note that we do need to run Dijkstra to find how to finish the path. This is because we cannot just take the global shortest path from where we are to the finish, we need to avoid the vertices already visited by the prefix of our path. However, it is enough to run Dijkstra once for each prefix – backwards from the finish – and then we can test each option for the first new vertex in constant time. This way we can find the first k+1 routes in total time O(k^2 nm log n).

The time limit was intentionally loose so somewhat less efficient implementations with a similar idea should pass. The above solution is not optimal either, it is possible to save more time – e.g., instead of recomputing each new route from scratch we can maintain a sorted set of candidates and each time we add a route, we just add new candidates that are branching off the new part of this new route.