An undo week

Google Code Jam 2019 Round 2 was the main event of the May 13 - May 19 week (problems, results, top 5 on the left). The top 1000 all advanced to Round 3, but of course the strongest competitors used this chance to compete for the top spot in a very strong field. mnbvmar came out first with a 15-minute advantage over the second place. Congratulations!

In my previous summary, I have mentioned a TopCoder problem: you are given two sequences a and b of n<=100 elements each, with each element being an integer between 1 and 100, and an integer s between 1 and the sum of all integers in the two sequences. We will permute each of the sequences, and then start taking numbers in the order a₁, b₁, a₂, b₂, ..., until the sum of the numbers already taken is greater than or equal to s, which will happen after taking a number either from a or from b. In how many of the (n!)² possible choices of the two permutations we reach s after taking a number from a? Return the answer modulo 10⁹+7.

Let's iterate over which element x of a will actually cause the sum to exceed s, and the position k at which this element is in the permuted array a. Then we know that the sum p of first k-1 elements of permuted a plus the sum q of the first k-1 elements of permuted b is less than s, and p+q+x is greater than or equal to s. We can use relatively standard dynamic programming to find the number of ways to achieve each sum p with k-1 elements of a without using x and each sum q with k-1 elements of b. We can then iterate over p and q such that s-x<=p+q<s to find our answer.

How quick is this solution? For simplicity, let's use n to denote both the number of items and the maximum value of an item. We iterate over x and k, and then over p and q. There at most n² values of p, and at most n valid values of q for each p, so overall complexity for this part is O(n⁵). We also have to run the dynamic programming for each value of excluded item x and each item being taken, which iterates over k and p to update multiple states, so the complexity for this part is also O(n⁵).

This is a bit too much for n=100, so let's speed up both parts to O(n⁴). In the first part, we can notice that valid values of q for each value of p form a segment, so we can compute prefix sums to be able to find a sum of values for a segment of q's in O(1), making overall running time of the first part O(n⁴).

For the second part, we will avoid recomputing the entire dynamic programming for each excluded item x using a very nice trick. First, let's compute the dynamic programming without excluding any items: now for each k and p we know the number of ways to get p as a sum of k items from a. Now, for each excluded item x we will "undo" one step of this dynamic programming: the number of ways to get p as sum of k items from a without using item x is equal to the number of ways to get p as sum of any k items from a minus the number of ways to get p-x as sum of k-1 items from a without using item x. This allows to handle each value of x in O(n³), and makes the running time of the second part and of the entire solution O(n⁴) overall.

I find this trick particularly nice because normally we compute this dynamic programming in some specific order, and therefore there is only one item for which excluding it from consideration is an undo step. However, since the end result of the dynamic programming does not depend on the order in which we process the items, we can imagine for each item that it was the last to be processed, and undo its addition.

Thanks for reading, and check back for more!