MMPROD - Editorial

editorial
greedy
mmprod
simple
snckpb16

#1

PROBLEM LINK:

Contest
Practice

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)

AUTHOR’S AND TESTER’S SOLUTIONS:

setter
tester


#2

EXPLANATION:

The problem is easy if none of the elements of A are positive: simply take the largest K elements!

I think it should be :

The problem is easy if none of the elements of A are positive negative: simply take the largest K elements!


#3

I did the question using log (base 10 ) , as i thought computation with log can be easier in this question.

If all the N elements are non positive , divide this in 2 subtasks:-
( Also keep count of all zeroes . Let this value be Z )
a) when K is odd - just check if Z is not equal to 0 . If not , print 0 as answer. However if Z is zero , then sort the N negative numbers on the basis of log of the absolute value in increasing order . As K is odd, their product is bound to be negative , so take the product of first K values.
b) when K is even - In this case , sort the N negative numbers on the basis of log of the absolute value in decreasing order . As K is even , their product is bound to be positive , so take the product of first K values.

If N=K, just take product of all elements.

If however , all the N elements are neither positive or negative, just a basic logic works .
Make 2 separate arrays - one containing log of positive integers , the other containing log of absolute value of negative integers .
Sort each of them in decreasing order of log values.
Now for some K , we have few options like -

  • Take product of first K positive numbers only
  • Take product of first 2 negative numbers and first K-2 positive numbers.
  • Take product of first 4 negative numbers and first K-4 positive numbers.

– Take product of first K negative integers only.

Among all the above options choose the one which fetches maximum value ( this can be easily done by comparison of summation of log values ) .

Apart from these , there are some corner case which can be easily handled.

This is the link to by submission -
Submission

Hope it helps :slight_smile:


#4

I am getting a WA link : https://www.codechef.com/viewsolution/10487137
My logic was: If k is odd, take a single element from the right of the sorted array, and recurse with k=k-1. If k is even, take the maximum of the product of the two leftmost elements, or the product of the two rightmost elements, then recurse into k=k-2
Please look into the solution and let me know the corner cases i missed.


#5

I have been trying to reach to this problem in practice mode from last 10 hrs. Link to practice on top is not working fine, always popping out with an alert that problem is not visible now please try again later. Can you please resolve the issue @admin


#6

I cant understand why i am getting WA.Someone please help
soln link https://www.codechef.com/viewsolution/10473467


#7

can anyone help me with this:I am not able to figure out the flaw
https://www.codechef.com/viewsolution/10515847


#8

Hello,
@ashish1729 and @menikhilpandey. I used the same logic . I made a separate case for all negative numbers whereby I will choose last k numbers. For a mix of negative and positive,(if k is even) I am sorting array in increasing order and putting counter i on 0 and counter j on n-1. I will check whose product is greater-of elements on i and i+1 or those on j and j-1. That one will be multiplied to product and its index is updated. This will continue until I choose k elements. If k is odd, I will choose rightmost element and j will be n-2. same process then!
I couldnot find any failing test case. Please help me. I have given a lot of time to this:(
Link to my solution:-https://www.codechef.com/viewsolution/10489066


#9

After learning to solve maximum sum subarray problem, it’s time for you to solve the maximum product subsequence.

Why is it mentioned in the problem? Does the author want to deviate us towards “maximum product subarray problem”?? :stuck_out_tongue:

I was thinking of big number multiplication, then after a few minutes I realised it’s subsequence, not subarray. :smiley:


#10

In the above algorithm, there is no need to check the condition for existence of j1, because j1 will always exist.

If j1 does not exist, it means : there are no (i.e. even number of) negative numbers in A[N-K+1…N] & for that case :

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


#11

can we use itertools module to solve this problem in python.


#12

Why cant the solution be like.
1.sort the array
2.while taking the user input for array count the number of negative numbers in the array.
3.if count of negative number is zero then simply find the product of last k elements.
4.if negative numbers are there then count whether they are even in numbers or odd in numbers.
5.if they are odd in numbers then their product will be always negative and hence find the product of last k positive ones(there is a special condition when all the numbers are negative then if k is even take the product of first k and if its odd then take the product of last k)
6.if they are in even numbers then compare the product of first k product and last k product which is maximum will give the answer.
7.now for handling 0’s.
8.if all numbers are either <=0 in array then answer is 0 else if 0 comes both in first k and last k then also answer is 0.
9.else the answer is simply product of last k numbers.


#13

Fixed. Thanks.


#14

ah sorry havent read your solution but try this

-4 -3 -2 -1
if k is 3
you will choose

-4 * -3 * -1 = -12

but that will not work

ans will be -1 * -2 * -3

flaw in logic: assuming rightmost element to be positive


#15

Thanks Ashish i got the flaw :slight_smile: