Counting Phenomenal Arrays#13032

Counting Phenomenal Arrays (Editorial)

Author:

Anton Trygub

For an array b_1, b_2, \ldots, b_k of integers , define its imbalance as b_1 + b_2 + \ldots + b_k - b_1b_2 \ldots b_k.

Lemma 1: For any integers b_1, b_2, \ldots, b_k, b_{k+1}, all of which are at least , the imbalance of the array [b_1, b_2, \ldots, b_{k+1}] is smaller or equal to the imbalance of the array [b_1, b_2, \ldots, b_k].

Proof: We have to show that b_1 + b_2 + \ldots + b_k + b_{k+1} - b_1b_2 \ldots b_kb_{k+1} \le b_1 + b_2 + \ldots + b_k - b_1b_2 \ldots b_k, or, equivalently, that b_{k+1}(b_1b_2 \ldots b_k-1) \ge b_1b_2 \ldots b_k. This follows as b_{k+1}(b_1b_2 \ldots b_k-1) \ge 2(b_1b_2 \ldots b_k-1) = b_1b_2 \ldots b_k + (b_1b_2 \ldots b_k - 2) \ge b_1b_2 \ldots b_k.

Lemma 2: All elements of any phenomenal array of size don't exceed .

Proof: If there is only one element not equal to , clearly the sum will exceed the product. So, there are at least two such elements, consider two largest of them — and . Suppose that x\ge n+1, y\ge 2, then the balance of is x+y-xy = x+y(1-x) \le x+2(1-x) = 2-x \le -(n-1), so we would have to add at least n-1 ones to it to make the balance (adding elements larger than decreases the balance even more, and adding increases it by one), but we have only n-2 elements remaining.

Note that for k = 1, the balance is always . So, such balance is always nonpositive.

Consider now any phenomenal array of size , and look at its elements which are not equal to — let them be b_1, b_2, \ldots, b_k. It means that the remaining n-k elements are s. This means that the balance of [b_1, b_2, \ldots, b_k] has to be precisely -(n-k). Moreover, each such array b_1, b_2, \ldots, b_k corresponds to some precise number of ones that you have to add to it to make it phenomenal.

So in theory, what we would have to do is to find all arrays b_1, b_2, \ldots, b_k of integers , to calculate their balance , and to add \binom{k+(-bal)}{(-bal)} to the f(k+(-bal)) for each such array. But how would we consider all such arrays?

First, note that we don't have to consider arrays for which k + (-bal) > n. Second, note that we only care about the product and the sum of b_1, b_2, \ldots, b_k.

So, let's implement some recursive algorithm

recurse(int sum, int product, int size, int ways, int iter)

We will keep the sum of the currently chosen elements, their product, the number of chosen elements, and the number of ways to rearrange them, and we will start from recurse(0, 1, 0, 1, 2). For every from to , we will try to add a few elements equal to to the current array, without breaking the condition size + (-bal) \le n. One option is to not add any element equal to at all, from which we will recurse to

recurse(sum, product, size, ways, iter+1).

Another option is to add instances of number , which would lead us to

recurse(sum+iter\cdotcnt, product\cdot iter^{cnt}, size+cnt, ways\cdot \binom{\text{size+cnt}}{cnt}, iter+1). Iterate until the bal + (size + cnt) exceeds .

At each step of recursion, add ways \cdot \binom{size+(-bal)}{size} to f(size + (-bal)).

This recursion runs very fast, as the product increases much faster than the sum does. It runs fast enough even for n \le 10^6 (in under seconds), so you shouldn't have experienced any TL issues if you tried any recursive approach.