A power of two week

There were no contests that I'd like to mention this week, but we still have two cool problems C from the previous summary to discuss. First, let us talk about a Codeforces problem: you have a set S of integers between 1 and M (M<=500). In one operation, you pick an element of the set uniformly at random, and increment it by 1. If the incremented element coincides with another element of the set, we keep only one copy, so the size of the set decreases by 1. If the incremented element exceeds M, we discard it, so the size of the set also decreases by 1 in that case. We are given the starting set S, and need to find the expected number of steps before it becomes empty.

When I was thinking about this problem, I have convinced myself that any solution will need to keep track of the number of elements in the set S as we divide the probabilities by that number on each step, and unlike multiplication, division does not lend itself to some nice linearity of expectation arguments. Well, it turns out it does :)

Consider two adjacent numbers from the initial set S. How do they move? Well, either the lower number increases by 1, in which case it might actually merge with the higher number, or the higher number increases by 1, in which case it might disappear if it exceeds M, and then the lower number will also disappear after a few more steps. What is the expected number of steps that the lower number makes? Here comes the stunning observation: we do not actually need to know anything about the rest of the set S to compute this expected number of steps! No matter what happens to the rest of the set, every time one of those two numbers moves, it will be the lower number with probability 50%, and the higher number with probability 50%. So we can implement a relatively standard dynamic programming to compute the expectation.

And then, as you have probably guessed by this point, thanks to the linearity of expectation the answer to the problem can be computed as the sum of those expected numbers of steps over all pairs of adjacent numbers in the input, plus the expected number of steps for the highest number (which is just M+1 minus that number).

The really unexpected aspect of this solution for me is that we end up only ever dividing by 2, even though on the surface it looks like we need to divide by numbers up to |S|. Having learned this from the editorial, I immediately remembered one thing that I considered doing during the contest: can we try to reconstruct the answers to the sample cases in the fraction form from the values modulo 1000000007 that are given in the problem statement (750000009, 300277731 and 695648216)? Knowing the solution, I realized that those fractions would have a power of two in the denominator, and that might have been just the clue I needed to solve this problem.

I've tried doing this now, and it turns out this reconstruction is not so easy. Just trying to find a fraction with the smallest numerator and denominator yields:

750000009 = 15/4
300277731 = 26062/39247
695648216 = 35459/32906

Which is clearly incorrect for the last two cases, as the answer cannot be less than 1 or so close to 1. Adding some reasonable boundaries on the value of the fraction (it must be between 10 and 50 for the last two cases), we get:

750000009 = 15/4 = 3.75
300277731 = 133137/8642 = 15.40580884054617
695648216 = 133345/10938 = 12.19098555494606

Which actually looks plausible, but is still incorrect as we know from the above. However, we know from the problem statement that the denominator cannot have prime factors greater than |S|, which in our case is 5. Adding that constraint produces:

750000009 = 15/4 = 3.75
300277731 = 1241063/65536 = 18.937118530273438
695648216 = 582323/32768 = 17.771087646484375

Which looks even more plausible, to the point that it might be correct (I did not check), and in any case might have delivered the key hint about only ever dividing by 2.

Now, some questions to the reader :) Do you routinely try to convert the sample answers from the "modulo prime" form to the fraction form? Did it ever help you solve a problem? Do you have some tricks on how to do this more reliably? If the problemsetters are reading this, did you consider this trick when choosing the samples for this problem?

Now, on to an AtCoder problem: you are given N<=1000 pairs of integers (A_i,B_i), each integer between 0 and 10⁹. In one operation, you choose two integers x<y between 0 and 10¹⁸, and replace each A_i with (A_i+x) mod y (note that you apply the same x and y to all A_i). You need to make it so that A_i=B_i for all i after at most N operations, or report that it is impossible.

During the round, I guessed correctly that this is almost always possible, except for the cases like A₁=A₂, but B₁≠B₂. However, I could not find a nice way to reorder the numbers. I was thinking mostly about operations where y is bigger than the biggest number, to have at least some control over what is happening. In that case, by choosing the appropriate x, we can split the numbers into two parts and interleave those parts, but that does not give us enough control to achieve an arbitrary ordering.

One other thing that came to mind when thinking about this interleaving operation is that it can only make the numbers closer to each other, but not pull them apart. However, when no interleaving actually happens, in other words when we just do a cyclic shift of the numbers, then we are not reordering, but we can pull the two halves apart as much as we'd like.

This is how far I've got during the round, and it turns out that this is the right direction, but I missed one final trick. Here is a working plan: in the first N-1 operations, we do N-1 cyclic shifts, which allows us to create almost arbitrary gaps between pairs of adjacent numbers, but still keeps the cyclic order intact. And then in the N-th operation we do a massive reodering and everything falls into place.

Knowing the plan, it is relatively easy to figure out the details. Assuming the last operation uses x=0 and some y=Y that is bigger than all B_i, we just need to make A_i=Y*k_i+B_i. And now we can choose k_i in such a way that the cyclic order of those A_i coincides with the initial cyclic order of A_i, moreover we can choose any particular cyclic shift of this cyclic order, which then makes planning the first N-1 operations easy. You can find more details in the editorial.

However, it is still unclear to me how I could have arrived at this final trick without just "seeing" it out of nowhere. Even though the operation used in this problem is simple, the space of ways to use it is endless, and it was hard for me to somehow narrow down the search. For many problems, it is more or less clear where the difficulty lies and that you must use a certain resource optimally to arrive at the solution, and this helps cut less promising directions quickly when trying to solve the problem. However, in problems like this one, one cannot be sure that the direction is correct until they see a full solution.

To the 174 people who solved this problem during the round: how did you arrive at the solution? Is there some intermediate reasoning step that makes the last leap of faith smaller, or is it just small enough for you as it is?

Thanks for reading, and check back next week!