PROBLEM LINK:
Author: Kevin Atienza
Testers: Sergey Kulik and Vasya Antoniuk
Translators: Vasya Antoniuk (Russian), Team VNOI (Vietnamese) and Hu Zecong (Mandarin)
Editorialist: Kevin Atienza
DIFFICULTY:
Simple
PREREQUISITES:
Greedy
PROBLEM:
Given an array A of length N, and a number K, find the maximum product of any K-element subsequence, modulo 10^9 + 7.
QUICK EXPLANATION:
Sort the numbers by increasing absolute value. If the product of the last K numbers is nonnegative, then that’s the answer.
Otherwise, if all elements of A are not positive, the answer is the product of the first K numbers.
Otherwise, you have (at most) two candidates.
- Take the last K numbers, and replace the first positive number in them (if it exists) by the last negative number before them (if it exists).
- Take the last K numbers, and replace the first negative number in them (if it exists) by the last positive number before them (if it exists).
If neither candidate exists, then the answer is the product of the first K numbers. Otherwise, the answer is the candidate with the larger product, which is guaranteed to be positive. Also, to compare these two candidates without using big integers, you only need to compare the two numbers that you changed.
EXPLANATION:
The problem is easy if none of the elements of A are negative: simply take the largest K elements! Unfortunately, the negative numbers make this problem a little harder than that. Specifically, adding a negative number to the subsequence flips the sign of the product.
But not all is lost. Suppose we sort the numbers by increasing absolute value. If the product of the K numbers with the highest absolute values is not negative, then that must be the answer. Indeed, that is the largest absolute value of the product of any length-K subsequence, and since it’s not negative, it must be the highest overall. This is exemplified by the second sample case, where the two elements with the highest absolute values are negative, yet yield the best possible product: (-5)\cdot (-6) = 30.
But if their product is negative, then we need some adjustments. For example, if we can find any subsequence with a nonnegative product, then that is already better than the product of the last K elements. But if a nonnegative product exists, then we can actually show that we can form an optimal subsequence by taking the last K elements and replacing exactly one element! To see why, suppose we have a subsequence with the highest possible product S, and it differs from the last K elements by at least two elements. By assumption, the product of the values in S is nonnegative, while the product of the last K elements is negative.
Let A_i and A_j be two of the last K elements that are not in S, and let A_{i'} and A_{j'} be two of the elements in S that are not in the last K elements. Then it follows that |A_{i'}|, |A_{j'}| \le |A_i|, |A_j|. Also,
- If A_{i'} and A_{j'} have differing signs, or if A_i and A_j have differing signs, then one of the pairs (A_{i'},A_i), (A_{i'},A_j), (A_{j'},A_i), (A_{j'},A_j) must have the same sign, so we take that pair, and replace the first one by the second one in S and yield a product with the same sign (not negative) but with a higher absolute value, which means a (possibly) higher product than the product of S! Since S has the highest possible product, it means the new sequence must have the highest possible product too.
- If A_{i'} and A_{j'} have the same sign, and if A_i and A_j have the same sign, then A_{i'}A_{j'} must have the same sign as A_iA_j (both not negative), so we can replace both A_{i'} and A_{j'} by A_i and A_j in S, and the product’s sign doesn’t change. But the product of the last K elements is negative, which means the product of S must have been negative too, which contradicts our assumption. So this case is impossible.
We can repeatedly apply this until our sequence only differs from the last K elements by just one element. After doing so, we will have a sequence with the highest possible product, yet only differs from the last K elements by just one element.
So how can we use this to find an answer? We need to know which value to replace and what value to replace it with. But since the product of the last K elements is negative, we must replace some value in such a way that flips the sign of the product. It means either:
- Replace a positive number by a negative number, or
- Replace a negative number by a positive number.
But we want the absolute value of the product to be as high as possible, so only two candidates remain:
- Replace the positive number with the smallest absolute value, say A_i where i > N-K, with the negative number with the highest absolute value, say A_{i'} where i' \le N-K.
- Replace the negative number with the smallest absolute value, say A_j where j > N-K, with the positive number with the highest absolute value, say A_{j'} where j' \le N-K.
The answer must be one of these candidates; specifically, the one with the higher product!
But there are a couple of problems with this:
- It may happen that the values we’re looking for don’t exist! For example, A_i cannot exist if the last K values are all negative.
- If they both exist, then how do we compare their products? It’s not easy because the product is usually too large to fit in any variable. We can’t really reduce them modulo 10^9 + 7 because that would mess up the comparison: (a \bmod m) < (b \bmod m) doesn’t imply a < b!
To handle the first problem:
- If exactly one candidate exists, then the answer must be that candidate. Thus, we can skip the comparison.
- If no candidate exists, then we can show that either the remaining elements are all zero, or all values are not positive. But in this case, there’s a simple answer: since we can’t have a positive product in any way, we can just as well choose the product with the lowest possible absolute value, that is, the product of the first K elements!
To prove the second one, suppose no candidate exists. Suppose also that not all remaining elements are zero. Then we want to show that none of the elements are positive. To see why, notice that the product of the last K elements are negative, so at least one negative element A_i, i > N-K exists. For the first candidate to not exist, all nonzero values A_{j'}, j' \le N-K must be negative too. But then for the second candidate, j' exists, so for it to not exist, all elements A_i, i > N-K must be negative. This proves that none of the elements are positive!
Finally, if both candidates exist, then we can’t compare them directly because the products are too large. Luckily, the candidates have products that don’t differ a lot from the product of the last K elements. Specifically, if P is the product of the last K elements, then:
- The first candidate has product P\cdot \frac{A_i}{A_{i'}}.
- The second candidate has product P\cdot \frac{A_j}{A_{j'}}.
Which means we must do the comparison P\cdot \frac{A_i}{A_{i'}} > P\cdot \frac{A_j}{A_{j'}}. But here, we can cancel the P! Specifically, this comparison has the same result as the comparison \frac{A_i}{A_{i'}} < \frac{A_j}{A_{j'}}. Notice that the inequality direction changed, because P is negative by assumption. Finally, by multiplying A_{i'}A_{j'} to both sides, we find that that comparison has the same result as A_iA_{j'} > A_jA_{i'}. Notice that the inequality direction changed again, because A_{i'}A_{j'} is negative. The last comparison doesn’t need more than 64-bit variables, so it can now be done!
We can summarize the algorithm here. Note that in this algorithm, we have avoided using numbers that don’t fit in 64-bit variables.
Sort A[1..N] by increasing absolute value
If there are an even number of negative numbers in A[N-K+1..N], or one of them is zero:
return the product of the last K elements mod 10^9+7
Let i1 be the first index > N-K such that A[i1] > 0
Let i2 be the last index <= N-K such that A[i2] < 0
Let j1 be the first index > N-K such that A[j1] < 0
Let j2 be the last index <= N-K such that A[j2] > 0
If i1 or i2 doesn't exist, and j1 or j2 doesn't exist:
return the product of the first K elements mod 10^9+7
If i1 or i2 doesn't exist:
return the product of the last K elements except A[j1] and including A[j2], mod 10^9+7
If j1 or j2 doesn't exist:
return the product of the last K elements except A[i1] and including A[i2], mod 10^9+7
If A[i1] * A[j2] < A[i2] * A[j1]:
return the product of the last K elements except A[i1] and including A[i2], mod 10^9+7
else:
return the product of the last K elements except A[j1] and including A[j2], mod 10^9+7
When computing the product of a list of numbers, be sure to reduce intermediate values modulo 10^9 + 7!
Time Complexity:
O(N \log N)
