A power of two week

This week's contests were concentrated on the weekend. First, Yandex.Algorithm 2018 Round 1 has brought back the "open/blind" submission format on Saturday (problems with Yandex login, results, top 5 on the left, my screencast, analysis). It turned out that it doesn't really matter whether to choose open or blind if one gets all problems correct from the first try, and is the only one to solve everything :) Congratulations to tourist!

Problem E has a deceptively easy solution in the analysis, and yet it seems really hard to come up with. You are given a sequence of 100000 positive integers up to a billion. You need to find any integer k such that it's possible to transform our sequence into a strictly increasing sequence of positive integers by subtracting some of its elements from k (in other words, by replacing x_i by k-x_i for some set of i's). Can you see why this problem is actually quite simple?

On Sunday Codeforces hosted its Round 468 (problems, results, top 5 on the left, my screencast). It was V--o_o--V's turn to be head and shoulders above the competition, finishing all problems in less than an hour. Well done!

The hardest problem E involved finding an appropriate dynamic programming angle that allows "coordinate compression" to work. Consider an unknown binary string of length k, k is up to a billion. You're given up to 100000 segments [a_i,b_i], and know that each of those segments contains at least one 0. In a similar vein, you're also given up to 100000 segments [c_i,d_i], and know that each of those segments contains at least one 1. How many such binary strings exist, modulo 10⁹+7?

Last week, I have mentioned a TopCoder combinatorics problem: find the sum of 2^x₁ (two to the power of the minimum number) over all possible ways to choose k distinct positive integers up to n: 1<=x₁<x₂<...<x_k<=n, where n is up to a billion, and k is up to a million.

The key idea is: instead of summing 2^x₁ for each combination, which seems hard to do, we will further subdivide each combination into 2^x₁-1 different objects, so that we just need to count the number of objects and multiply by 2. More specifically, if we have k distinct positive integers, and the smallest is x₁, then there are exactly 2^x₁-1 ways to add some subset of numbers between 1 and x₁-1 to it. As a result, we get a set of at least k distinct positive integers. And moreover, we can obtain all such sets: each such set can be obtained by subdividing the set of k its largest numbers. So we need to return 2 times the number of ways to choose at least k objects out of n, which is much easier to compute.

Thanks for reading, and check back next week!