You are not logged in. Please login at www.codechef.com to post your questions!

×

MMPROD - Editorial

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

This question is marked "community wiki".

asked 13 Jun '16, 21:19

kevinsogo's gravatar image

7★kevinsogo
1.7k472135
accept rate: 11%

edited 16 Jun '16, 04:37


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!

link

answered 15 Jun '16, 13:10

pankaj_chopra's gravatar image

2★pankaj_chopra
22928
accept rate: 20%

Fixed. Thanks.

(16 Jun '16, 04:37) kevinsogo7★

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 :)

link

answered 15 Jun '16, 13:55

iit2014098's gravatar image

3★iit2014098
11
accept rate: 0%

edited 15 Jun '16, 13:57

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.

link

answered 15 Jun '16, 15:58

menikhilpandey's gravatar image

3★menikhilpandey
1111
accept rate: 0%

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

(16 Jun '16, 06:29) ashish17293★

Thanks Ashish i got the flaw :)

(16 Jun '16, 10:29) menikhilpandey3★

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

link

answered 15 Jun '16, 22:20

magpie's gravatar image

2★magpie
11
accept rate: 0%

edited 15 Jun '16, 22:38

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

link

answered 16 Jun '16, 00:20

skag's gravatar image

4★skag
162
accept rate: 33%

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

link

answered 16 Jun '16, 10:51

akaashhazarika's gravatar image

2★akaashhazarika
1
accept rate: 0%

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

link

answered 17 Jun '16, 15:33

varshika03's gravatar image

3★varshika03
1
accept rate: 0%

"*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"?? :P

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

link

answered 18 Jun '16, 04:45

p.abhinav's gravatar image

3★p.abhinav
213
accept rate: 0%

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

link

answered 18 Jun '16, 18:16

pankaj_chopra's gravatar image

2★pankaj_chopra
22928
accept rate: 20%

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

link

answered 19 Jun '16, 08:57

santh_chi's gravatar image

1★santh_chi
6
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×11,590
×780
×716
×70
×13

question asked: 13 Jun '16, 21:19

question was seen: 3,609 times

last updated: 19 Jun '16, 08:57