11059 - Maximum Product

All about problems in Volume 110. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
User avatar
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

11059 - Maximum Product

Post by Martin Macko » Sun Aug 06, 2006 12:41 am

Why the maximal N is so small? Just 18 as written in the problem statement...

There is an O(N) algorithm, so the N could be much bigger to make people use optimal algorithm.... 8)

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Sun Aug 06, 2006 12:46 am

I guess the low limit was used because otherwise the result would not fit into 64-bit integer.

User avatar
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Post by Martin Macko » Sun Aug 06, 2006 12:54 am

Adrian Kuegel wrote:I guess the low limit was used because otherwise the result would not fit into 64-bit integer.
Oh right... that's could be the point... I didn't notice it :oops:

User avatar
arsalan_mousavian
Experienced poster
Posts: 111
Joined: Mon Jan 09, 2006 6:19 pm
Location: Tehran, Iran
Contact:

Post by arsalan_mousavian » Sun Aug 06, 2006 1:51 am

i 've got many WA on this problem , i have used long long to store the result
and multiply it by each input , whenever the result is greater than zero , i compare it with max , and finaly print it , where is my mistake
In being unlucky I have the record.

User avatar
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Post by Martin Macko » Sun Aug 06, 2006 1:55 am

arsalan_mousavian wrote:i 've got many WA on this problem , i have used long long to store the result
and multiply it by each input , whenever the result is greater than zero , i compare it with max , and finaly print it , where is my mistake
Try the following input:

Code: Select all

1
-47

1
47

The correct answer is:

Code: Select all

Case #1: The maximum product is 0.

Case #2: The maximum product is 47.


mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Sun Aug 06, 2006 1:56 am

Try

Code: Select all

2
-1 1
The output should be 1.

User avatar
arsalan_mousavian
Experienced poster
Posts: 111
Joined: Mon Jan 09, 2006 6:19 pm
Location: Tehran, Iran
Contact:

Post by arsalan_mousavian » Sun Aug 06, 2006 2:12 am

thanks mf , i'll check my code soon , my program doesn't give the right answer to your Input, but my program gives the right output for martin macko's IO

NOW I GOT ACCEPTED , THANKS A LOT
In being unlucky I have the record.

Wei-Ming Chen
Experienced poster
Posts: 122
Joined: Sun Nov 13, 2005 10:25 am
Location: Taiwan

Post by Wei-Ming Chen » Sun Aug 06, 2006 6:16 am

How about the outputs of these inputs?

Code: Select all

3
1 0 2

4
5 -9 -7 -8

2
1 0

2
-1 0

6
4 8 0 -9 6 -1

5
-8 -8 -7 5 1

2
0 0

1
0

1
-1

I got WA on this problem again....

mamun
A great helper
Posts: 286
Joined: Mon Oct 03, 2005 1:54 pm
Location: Bangladesh
Contact:

Post by mamun » Sun Aug 06, 2006 7:12 am

Output:

Code: Select all

Case #1: The maximum product is 2.

Case #2: The maximum product is 315.

Case #3: The maximum product is 1.

Case #4: The maximum product is 0.

Case #5: The maximum product is 54.

Case #6: The maximum product is 280.

Case #7: The maximum product is 0.

Case #8: The maximum product is 0.

Case #9: The maximum product is 0.


temper_3243
Experienced poster
Posts: 105
Joined: Wed May 25, 2005 7:23 am

Post by temper_3243 » Sun Aug 06, 2006 9:02 am

1) what is the o(n) algorithm for this problem. please describe it.

2) What if they say maximum product of any elements. Then what is the complexity. Can anyone throw some light on it. My approach is sort it.

Compare the number of "negative numbers" , check if any zeros (remove them), product of positive number. if negative numbers are odd (2n +1) multiply first 2n negative and the other positive product. Can anyone tell me if it is right , if not multiply negative product * positive product.


I used o(n^2) algo.
i used unsigned long long and flag to keep track of sign. it got accepted.

chrismoh
New poster
Posts: 35
Joined: Mon Dec 10, 2001 2:00 am
Location: Singapore; Cambridge, MA

Post by chrismoh » Sun Aug 06, 2006 11:33 am

Consider the list as being a sequence of shorter lists that are simply separated by zeros.

We can compute the maximal product of each list in linear time by simply going through all numbers sequentially and storing the maximum (in terms of absolute value) positive and negative products that can be obtained by ending at the current list element ( as you iterate through the list ).

e.g. for sequence 1 -2 4 -3 -1
At element 1: Max positive = 1, max negative = undefined
At element 2: Max positive = undefined, max negative = -2
At element 3: Max positive = 4, max negative = -8
At element 4: Max positive = 24, max negative = -12
At element 5: Max positive = 12, max negative = -24

So overall the answer is the highest max positive = 24 (there can be no max positive ever if there is only one negative element in the list - and this case can be handled easily)

Clearly the max positive and max negative can be obtained from previous elements.

Product of any elements is simple. No sorting needed (because that is O(n log n) time). But the rest of your algorithm is correct. You can just multiply all non-zero numbers, and remove the smallest negative number if the number of negative numbers is odd.

ytsejam
New poster
Posts: 3
Joined: Tue Aug 01, 2006 5:27 pm

Post by ytsejam » Sun Aug 06, 2006 5:20 pm

chrismoh wrote:Consider the list as being a sequence of shorter lists that are simply separated by zeros.

We can compute the maximal product ....
I tried to write a program using your algorithm:

Code: Select all

AC, thanks Martin Macko
I also tried the test cases in this thread and the prog give the right answer, but I submitted it and got WA
Can someone explain me why?
Last edited by ytsejam on Sun Aug 06, 2006 9:53 pm, edited 1 time in total.

User avatar
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Post by Martin Macko » Sun Aug 06, 2006 9:30 pm

ytsejam wrote:I tried to write a program using your algorithm:

I also tried the test cases in this thread and the prog give the right answer, but I submitted it and got WA
Can someone explain me why?
Consider this change:
main() wrote:......if(elem[0] > 0){
.........pos[0] = elem[0];
.........neg[0] = 0;
.........best = elem[0];
......} else {
.........pos[0] = 0;
.........neg[0] = -elem[0];
.........best = 0;
......}

w k
Learning poster
Posts: 74
Joined: Wed Apr 14, 2004 11:14 pm

Post by w k » Thu Aug 10, 2006 2:39 pm

Try
Code:
2
-1 1


The output should be 1.
I've doubts whether this is correct. In accordance to the problem wording we've to find the maximum positive product. In the quoted case the only product we can obtain is -1 so the correct output should be 0!

Wojciech

User avatar
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Post by Martin Macko » Fri Aug 11, 2006 12:07 am

w k wrote: I've doubts whether this is correct. In accordance to the problem wording we've to find the maximum positive product. In the quoted case the only product we can obtain is -1 so the correct output should be 0!

Wojciech
IMHO the degenerated case of a product of just one factor is perfectly legal. 8)

Post Reply

Return to “Volume 110 (11000-11099)”