Maximum Product?
Contest: Codeforces Global Round 21
Difficulty rating: 3500
Tags: brute force, combinatorics, dp, greedy, implementation, math, two pointers

You are given a positive integer $$$k$$$. For a multiset of integers $$$S$$$, define $$$f(S)$$$ as the following.

- If the number of elements in $$$S$$$ is less than $$$k$$$, $$$f(S)=0$$$.
- Otherwise, define $$$f(S)$$$ as the maximum product you can get by choosing exactly $$$k$$$ integers from $$$S$$$.

More formally, let $$$|S|$$$ denote the number of elements in $$$S$$$. Then,

- If $$$|S|<k$$$, $$$f(S)=0$$$.
- Otherwise, $$$f(S)=\max\limits_{T\subseteq S,|T|=k}\left(\prod\limits_{i\in T}i\right)$$$.

You are given a multiset of integers, $$$A$$$. Compute $$$\sum\limits_{B\subseteq A} f(B)$$$ modulo $$$10^9+7$$$.

Note that in this problem, we distinguish the elements by indices instead of values. That is, a multiset consisting of $$$n$$$ elements always has $$$2^n$$$ distinct subsets regardless of whether some of its elements are equal.

Input format:
The first line of input contains two integers $$$n$$$ and $$$k$$$, where $$$n$$$ is the number of elements in $$$A$$$ ($$$1\le k\le n\le 600$$$).

The second line of input contains $$$n$$$ integers $$$a_1,a_2,\dots,a_n$$$, describing the elements in $$$A$$$ ($$$-10^9\le a_i\le 10^9$$$).

Output format:
Output $$$\sum\limits_{B\subseteq A} f(B)$$$ modulo $$$10^9+7$$$.

Constraints:
Time limit: 1.5 s
Memory limit: 512.0 MB

Note:
Consider the first sample. From the definitions we know that

- $$$f(\varnothing)=0$$$
- $$$f(\{-1\})=0$$$
- $$$f(\{2\})=0$$$
- $$$f(\{4\})=0$$$
- $$$f(\{-1,2\})=-2$$$
- $$$f(\{-1,4\})=-4$$$
- $$$f(\{2,4\})=8$$$
- $$$f(\{-1,2,4\})=8$$$

So we should print $$$(0+0+0+0-2-4+8+8)\bmod (10^9+7)=10$$$.

In the second example, note that although the multiset consists of three same values, it still has $$$8$$$ distinct subsets: $$$\varnothing,\{1\},\{1\},\{1\},\{1,1\},\{1,1\},\{1,1\},\{1,1,1\}$$$.

Example input:
3 2
-1 2 4

Example output:
10

Example input:
3 1
1 1 1

Example output:
7

Editorial:
First, we describe a strategy to find the answer for a single subset. If the whole subset is negative, the answer is the product of the $$$K$$$ maximum numbers in it. Otherwise, take $$$K$$$ numbers with the maximum absolute value. If there is an even number of negative numbers in those numbers, we're done. Otherwise, find the smallest positive element and change it to the absolute-value-maximum negative element unchosen, or find the largest negative element and change it to the maximum positive element unchosen. We either do the first change or do the second change.
This gives a direct dp solution. Take all $$$a_i$$$ and sort them into two arrays consisting of positive and negative ones (0 goes to arbitary one), $$$pos$$$ and $$$neg$$$, sorted by absolute values. By calculating $$$fpos(i,k)$$$: the sum of the product of the largest $$$K$$$ numbers of all subsets of $$$pos[1\dots i]$$$ that contain $$$pos_i$$$, and $$$fneg(i,k)$$$ similarly, and $$$gneg(i,k)$$$, the sum of the product of the absolute value smallest $$$K$$$ numbers of all subsets of $$$neg[i\dots |neg|]$$$ that contain $$$neg_i$$$, and enumerating the following, we can solve the original problem in $$$O(n^5)$$$:
- the number of positive elements in the $$$K$$$ numbers with the maximum absolute value in our calculating subset, $$$p$$$. - the smallest positive element in the $$$K$$$ numbers with the maximum absolute value, $$$pos_i$$$. - the greatest negative element in the $$$K$$$ numbers with the maximum absolute value, $$$neg_j$$$. - (if $$$p$$$ is odd) the greatest positive element not in the $$$K$$$ numbers with the maximum absolute value, $$$pos_k$$$. - (if $$$p$$$ is odd) the smallest negative element not in the $$$K$$$ numbers with the maximum absolute value, $$$pos_l$$$.
The contribution to the answer can be represented as the sum of product of $$$fpos,fneg$$$, and powers of two. I left the details as an exercise.
However, notice that the "enumerating $$$k,l$$$" part has nothing to do with $$$p$$$, so we can pre-calculate the contribution of $$$k,l$$$ for every pair $$$(i,j)$$$, giving an $$$O(n^4)$$$ algorithm.
What's more, for fixed $$$i,j,k$$$, the $$$l$$$-s that we do the first change is a prefix/suffix of all $$$l$$$, and $$$l$$$-s that we do the second change is a prefix/suffix of all $$$l$$$. So with two pointers and prefix sums, we can pre-calculate the contribution of every $$$(i,j)$$$ in $$$O(n^3)$$$, which is fast enough.
You might be afraid that $$$600^3$$$ is too slow for 1.5 seconds. However, the two $$$O(n^3)$$$ parts of the algorithm actually run in $$$O(n\times cntpos\times cntneg)$$$ ($$$cntpos,cntneg$$$ are the number of positive/negative integers in the array), leading to an at most $$$1/4$$$ constant factor. Thus, the algorithm actually runs very fast (less than 0.25 seconds). However for similar constant factor reasons, the $$$O(n^4)$$$ solution only takes about 6.5 seconds on Codeforces, so we had to set a seemingly-tight limit.