*lack*of communication as information as well. As a result, the people organizing the mirror (such as myself) did not try to figure out more information about the origins of this problem even though we knew from Polygon that it was prepared a bit earlier, assuming that other organizers who are closer to the beginning of this communication chain know the problem better and therefore are in a better position to judge if it is appropriate to use, so if they say nothing, all is good. But this line of reasoning fails to account for the fact that the people closer to the beginning of the communication chain have a different context (might not even be aware that there's a public mirror, for example) and different perceptions of what is OK.

In my previous summary, I have mentioned a Codeforces problem. You are given two integers

*n*and

*k*. Your goal is to create a (multi-)set of positive integers such that among its sub(-multi-)sets we can find ones which sum to any integer between 1 and

*n*, except

*k*. n is at most 10

^{6}, and the set you create must have at most 25 elements.

The first part of the solution is somewhat clear/standard: we need to be able to represent all numbers between 1 and *k*-1, but not the number *k*. For this, we can take all powers of two less than *k: *1, 2, 4, ..., 2^{i}, such that 2^{i}<*k*<=2^{i+1}, but then in order to not overshoot *k* we should replace 2^{i} with *k*-2^{i}: then the sum of all numbers is *k*-1, and clearly all numbers between 1 and *k*-1 are still representable.

Then, as long as all other numbers that we take into our set are at least *k*+1, *k* will still not be representable. But how do we cover all numbers between *k*+1 and *n*? After trying to come up with something concrete on paper unsuccessfully for some time, I've decided to just run a dynamic programming that remembers which numbers are representable, and repeatedly take the smallest non-representable number. It is not obvious why this will have at most 25 elements, but it is very easy to try.

Here is the output of this approach for n=1000000, k=5:

21

1 2 1 6 11 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 262144 524288

And for n=1000000, k=6:

21

1 2 2 7 13 19 38 76 152 304 608 1216 2432 4864 9728 19456 38912 77824 155648 311296 622592

Now we can notice a pattern: the numbers we add in the second phase are *k*+1, 2*k*+1, 3*k*+1, 2(3*k*+1), 4(3*k*+1), 8(3*k*+1), ... We can now both be more confident that it will always fit under 25 elements, and also try to prove that this pattern always works. Or just submit.

My submission in the actual contest is more complex than that, and even includes some randomization :) The reason for that is that I had a bug in the implementation of the simple dynamic programming which made me think it produces more than 25 elements sometimes, adding randomization helped fit under 25 but did not fix the bug, and after fixing the bug I did not check if randomization was still needed.

Thanks for reading, and check back next week!

good

ReplyDeletehow to be red

ReplyDelete