DIFFICULTY:
2709
Let’s first see how to check if we can split a given set of powers of 2 into two groups with the same sum.
If some 2^K appears at least 3 times, then some 2 of these appearances will be in the same group, so we can replace two of them by 2^{K+1}. Let’s do this process until no 2^K appears more than two times.
Let the current array of appearances be [A_0, A_1, A_2, \ldots, A_M]. I claim that we can split it only if and only if there is no such i that A_i = 0, A_{i+1} = 1.
-
If there exists such i, then the sum of all powers \ge 2^{i+1} gives remainder 2^{i+1} mod 2^{i+2}, so when these are split, one group will have sum divisible by 2^{i+2}, and other will have remainder 2^{i+1}. Powers smaller than 2^i can’t have a sum larger than 2(2^i - 1), so they won’t be able to correct the balance.
-
If there is no such i, we can always divide into two groups with equal sums. Divide the nonzero elements of A into segments of form [2, 1, 1, \ldots, 1]. We can divide any such segment into two groups: place the largest element in one group, and all remaining in the other.
Now, let’s show that the smallest number of operations needed to fix the array is equal to the number of i such that A_i = 0, A_{i+1} = 1.
-
We can definitely fix this in this number of operations: just add one to any such A_{i+1}.
-
It remains to show that we can’t decrease the number of such indexes by more than 1 in a single operation. Suppose we are adding 1 to A_i. If A_i \le 2, then it can fix at most 1 pair: (i-1, i) or (i, i+1) (depending on whether A_i is 1 or 0. If A_i = 2, then let j be the smallest integer \ge i such that A_j<2. Then, we will replace all A_k from A_i to A_{j-1} by 1, and increase A_j by 1. Clearly, this can fix only pair (j, j+1), so the conclusion holds again.
Now, how to solve the problem? We need to find the sum of the numbers of pairs (A_i, A_{i+1}) = (0, 1) over all possible sequences A after making the procedure described in the second paragraph. It’s not hard to simulate from the left to the right: basically, we are maintaining vector cur^k, where cur^k_i is the number of ways to choose first k elements so that A_{k+1} will be increased by precisely i after this process. Note that no number will ever increase by more than 5000. Then, we can move from cur^k to cur^{k+1} in O(max(A)), and here is how:
First, we calculate the array sum^{k+1}, where $sum_{i}^{k+1} represents the number of ways to choose the first k+1 elements so that A_{k+1} + the number added to A_{k+1} is precisely i, this can be done with prefix sums. From this array it’s easy to get array cur^{k+1}.
For each k we need to add to the answer sum^k_0 \cdot \lfloor \frac{A_{k+2} + 1}{2} \rfloor (where \lfloor \frac{A_{k+2} + 1}{2} \rfloor represents the number of ways to choose A_{k+2} so that it’s 1 after reduction), multiplied by \prod_{i>k+2} (A_i + 1).
,