Task authored, prepared, and editorial written by: Timur Degteari
The key observation (1) for this problem is that each power of can be composed as sum of smaller powers of .
Since the order of elements of doesn't matter we can sort it in decreasing order and pretend that is sorted.
Using the observation (1) we can make the observation (2) — for some array of length with b_i \geq b_{i+1} for all 1 \le i \le k-1, let S = 2^{b_1} + 2^{b_2} + \dots + 2^{b_n}. Then each of 2^{b_1}, 2^{b_1 + 1}, \dots, 2^{\lfloor \log2(S) \rfloor} can be composed as prefix sum of .
Let S = 2^{a_1} + 2^{a_2} + 2^{a_3} + \dots + 2^{a_n}.
Let denote the smallest possible largest sum of 2^{a_j} in one category (in other words, denote the optimal value of what we want to minimize).
If S < k \cdot 2^{a_1}, then the Ans(a) = 2^{a_1} since at least one category will contain 2^{a_1}, and for every other category we can keep adding elements from (in decreasing order) to it until we compose 2^{a_1} as their sum, or run out of elements in , (which is possible by the observation (2)).
If S \geq k \cdot 2^{a_1}, then consider some optimal partition of the elements of into categories. Without loss of generality, first category has the largest sum. From each category, take some subset of elements that sums up to 2^{a_1} (or all elements from the category if the sum is less than 2^{a_i} and erase them from . Denote the resulting array as a^{\prime}. Clearly, the first category still has the largest sum, and clearly Ans(a) = 2^{a_1} + Ans(a^{\prime}), since otherwise it'd be possible to rearrange the elements over categories to make the equality true in either direction. Additionally, if for some category its elements sumed up to less than 2^{a_1}, then a^{\prime} must be empty, because otherwise it contradicts the optimalty of the partition.
At the same time, we can observe from this, that by denoting M = Ans(a), S = \sum_{i=1}^n 2^{a_i} for the original array , and repeatedly applying a := a^{\prime}, we eventually arrive into situation where 2^{a^{\prime}_1} \cdot k > \sum 2^{a^{\prime}_i} \implies Ans(a^{\prime}) = 2^{a^{\prime}_1}, and therefore M = \frac{(S - \sum 2^{a^{\prime}_i})}{k} + 2^{a^{\prime}_1}, hence it's optimal to minimize the largest element of a^\prime, for which it suffices to use the prefix of to form categories with sums 2^{a_1}.
This way we get a greedy solution which proceed as follows:
Sort decreasingly, and while it is not empty, if the sum of 2^{a_i} is less than k \cdot 2^{a_1}, assign categories in such way that no sum exceeds 2^{a_1} and terminate. Otherwise, partition the prefix of into categories with sums exactly 2^{a_1}, remove this prefix, and proceed.
The final time complexity of this solution if implemented correctly is O(n log n).