That's a part of final editorial. I'm sorry for delay. Please, report me about mistakes and unclear moments in solutions and in my english.

A div2

Task was to find the least digit, that is not contained in the given number and compare with given k.

B div2

Good sequence may contain only zeroes or contain some positive number. In the second case such a sequence is not longer than sequence {0, 1, 1, 2, 3, 5, 8, ..., x, y} where y > 10⁹ and x ≤ 10⁹. That's possible to find it using dummy algorithm. In the first case you may use binary search of two pointers.

A div1

Let's notice that sum in the rectangle (x1, y1, x2, y2) is sum(x1, x2)·sum(y1, y2). Where sum(l, r) = s_l + s_l + 1 + ... + s_r. Then, we have to calc sum(l, r) for every pair (l, r) and count how many segments give us sum x for any possible x (0 ≤ x ≤ 9·|s|). In the end we should enumerate sum on segemnt [x1, x2] and find . There is corner case a = 0.

B div1

We may assume that John may exchange any subset of his items x to any other subset y, such as s(x) + d ≥ s(y) (it does not matter if x intersects y). We can find all possible sums in subset of elements of the given set of items using standard dp (knapsack problem). John should always exchange all his current set of items to another, because if he had exchanged some subset of x (current set) z to y, we can say that he had exchanged x to . So, we have to find shortest sequence of sets a, such as s(a_i + 1) - d ≥ s(a_i) for any possible i and a₀ = {}. This subtask could be solved using following greedy algorithm. a_i, i > 0 is maximal correct sum such as a_i ≤ a_i - 1 + d. Consider optimal answer c and our answer a. Let k is the first position where a_k ≠ c_k obiviously a_k > c_k (because a_k selected as maximal as possible). Then consider q such as q_i = c_i for i ≠ k and q_k = a_k. q is either optimal. Applying similar operations we will obtain a. So, a is optimal.

C div1

We expected many unproved, but tested solutions. I think that careful prove of my solution with pen and paper is very difficult. So I will use some statistic-based facts.

1. Consider the set of divisors of number k. One can check that it's beautiful set.
2. If factorisation of k has the form where α_i ≥ 3 and p_i is distinct primes, set of divisors of k which is less than is also beautiful.
3. How to prove item 2? Consider set A of pairs of divisors of k (a_i, b_i) such as a_i·b_i = k and a_i < b_i. Obiviously (if k is not complete square) any divisor will be contained only in one pair. It's easy too see that . Consider some element of factorisation of k p^α such as and it is not true that . Let f(x) is maximal number s such as . f(a_i) + f(b_i) = α. For every q such as numbers q, q·p, ..., q·p^α will be divisors of k. That implies that where d is number of divisors of . So in pairs both numbers are divisible by p. So set {a₀, ..., a|A|} is beautiful.
4. But there are some pairs with f(a_i) = α. is equivalent approval.
5. It's always possible to find such k as number of it's divisors is bigger than 2·w where w is number of elements in required set. You may write following dp to find it.
6. dp[i][j] is minimal k which is constructed of first i primes ans has j divisors.
7. About 10 primes is enough to cover all k.
8. Now we can construct beautiful sets with more than k elements.
9. Using item 4 we will understand that constructed answer is very beautiful (about 60% of elements divisible by every possible p) and we can always delete extra elements.

Last items is not strict, but one can check it with his computer.

D div1

1. Consider random element a_r of a. With probabillity where g is ghd of a.
2. Let x_i = gcd(a_i, a_r). There are no more than d distinct x_i where d is number of divisors of a_r.
3. We can find number of a_i such as for every k in O(d²). (D is set of divisors of a_r)
4. Repeat item 1 x times we will get correct solution with probabillity 1 - 2^- x.

There is the way to solve this problem O(n·plog + d·2^plog) for iteration where plog is the maximal number of distinct primes in factorisation of a_r.

E div1

1. Let's find number of rectangles whick consist k ones and intersect in cartesian coordinate system.
2. It's possible to do it in n²·k. We need to find closest k ones on the top and on the bottom of the and enumareate all segments [l, r] such as 1 ≤ l ≤ r ≤ n and find closest k ones on the top and on the bottom of the segments merging results for rows.
3. If we have k closest ones on the top and on the bottom of the segment we will find number of rectangles consists k ones and cross on [l, r] in O(k).
4. Then we should find number of rectangles, which don't cross . Let's rotate table by 90 degrees, solve similar problem for two halfs of the table and so on.
5. for square-shaped tables.

At the picture 1 two closest ones on the top (black cells) lying on the 4'th and 2'nd horizontals. Closest ones on the bottom lying on the 5'th and 7'th. Then if k = 2 there are zero correct rectangles with two "ones" on the tom. There are four rectangles which consist one "one" on the top and one "one" on the bottom. You can see how segment grows up at the pictures 2, 3 and 4. Every time you should merge closest k ones of the added row with closest k ones of the current segment.