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

Chok
New poster
Posts: 48
Joined: Mon Jun 27, 2005 4:18 pm
Location: Hong Kong

Post by Chok » Fri Aug 11, 2006 9:04 pm

Hello chrismoh,
Can u little bit exaplain how ur algo works in the following input
3
-9 -7 -8
May be somthing i missed or misunderstood. Plz explain. Thanks in advance.

Regards,
Chok

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 » Sat Aug 12, 2006 7:53 pm

Chok wrote:Hello chrismoh,
Can u little bit exaplain how ur algo works in the following input
3
-9 -7 -8
May be somthing i missed or misunderstood. Plz explain. Thanks in advance.

Regards,
Chok
At element 1: MaxPositive[1] = undef, MaxNegative[1] = -9
At element 2: MaxPositive[2] = MaxNegative[1]*(-7)=63, MaxNegative[2] = (-7)
At element 3: MaxPositive[3] = MaxNegative[2]*(-8)=56, MaxNegative = MaxPositive[2]*(-8)=-504

Therefore the biggest MaxPositive is 63.

Chok
New poster
Posts: 48
Joined: Mon Jun 27, 2005 4:18 pm
Location: Hong Kong

Post by Chok » Mon Aug 14, 2006 7:22 am

Hi Martin Macko,
Thank u very much for ur explanation. Got Accepted. Thanks again.

ErickNascimento
New poster
Posts: 6
Joined: Fri Dec 16, 2005 11:40 pm

WA

Post by ErickNascimento » Tue Aug 15, 2006 6:55 am

My program has passed all the tests given in this topic, but I still got WA.
Can anyone give me more test cases with correct output. Please Help me! I am getting crazy with this problem. Thanks in advance!

This problem requires long long (64 bit) variables instead of int (32 bit) ?

Here is my code:


Code: Select all


#include <stdio.h>

#define MAXN (18+10)
#define MIN(a,b) ((a)<(b)?(a):(b))
#define MAX(a,b) ((a)>(b)?(a):(b))

int N;

int S[MAXN];

int MaxPosProd(){
  
  int i;
  int P[MAXN]; /* Maximum Positive Product of S[0..N-1] */
  int SPPMax[MAXN]; /* SPPMax[i] = Maximum Positive Product which is Sufix of S[0..i]*/
  int SPNMin[MAXN]; /* SPPMin[i] = Minimum Negative Product which is Sufix of S[0..i]*/
  
  P[0] = ((S[0]<=0)? 0: S[0]);
  SPPMax[0]=((S[0]<=0)? 0: S[0]);
  SPNMin[0]=((S[0]>=0)? 0: S[0]);
  
  for(i=1; i<N; i++){
    if(S[i]==0){
      P[i]=P[i-1];
      SPPMax[i]=0;
      SPNMin[i]=0;
    }else if(S[i]>0){
      if(SPPMax[i-1] != 0){	
	P[i]=MAX(P[i-1], SPPMax[i-1]*S[i]);
	SPPMax[i]=SPPMax[i-1]*S[i];
	SPNMin[i]=SPNMin[i-1]*S[i];
      }else{ /*  SPPMax[i-1] == 0  */
	P[i]=MAX(P[i-1], S[i]);
	SPPMax[i]=S[i];
	SPNMin[i]=SPNMin[i-1]*S[i];	
      }      
    }else{/* S[i] < 0  */      
      if(SPNMin[i-1] != 0){	
	P[i]=MAX(P[i-1], SPNMin[i-1]*S[i]);	
	SPPMax[i]=SPNMin[i-1]*S[i];
	SPNMin[i]=MIN(SPPMax[i-1]*S[i], S[i]); /* detalhe:MIN */
      }else{/* SPNMin[i-1] == 0 */
	P[i]=P[i-1];
	SPNMin[i]=MIN(SPPMax[i-1]*S[i], S[i]);
	SPPMax[i]=0;
      }      
    }   
    
  }
  /*
    for(i=0;i<N;i++){
    printf("S[%d]=%d, P[i]=%d, SPPMax[i]=%d, SPNMin[i]=%d\n", i, S[i],  P[i], SPPMax[i], SPNMin[i]);
    }
  */


  return P[N-1];
  
}

int main(){
  
  int k;
  int iCase=1;
  
  while(scanf("%d", &N)==1){
    for(k=0; k<N; k++)
      scanf("%d", &S[k]);
    printf("Case #%d: The maximum product is %d.\n\n", iCase, MaxPosProd());
    iCase++;
  }
  
  
  
  return 0;
  
}




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

Re: WA

Post by Martin Macko » Tue Aug 15, 2006 11:25 am

ErickNascimento wrote:My program has passed all the tests given in this topic, but I still got WA.
Can anyone give me more test cases with correct output. Please Help me! I am getting crazy with this problem. Thanks in advance!

This problem requires long long (64 bit) variables instead of int (32 bit) ?
Try the following one:

Code: Select all

17
-10 -5 9 -2 -7 -3 -2 -9 4 -4 -7 8 -9 2 -6 2 -7

The correct output:

Code: Select all

Case #1: The maximum product is 460886630400.

Last edited by Martin Macko on Tue Aug 15, 2006 8:27 pm, edited 2 times in total.

ErickNascimento
New poster
Posts: 6
Joined: Fri Dec 16, 2005 11:40 pm

Post by ErickNascimento » Tue Aug 15, 2006 3:19 pm


Try the following one:
Code:
17
-10 -5 9 -2 -7 -3 -2 -9 4 -4 -7 8 -9 2 -6 2 -7

The correce output:
Code:
Case #1: The maximum product is 1191778304.
Macko, my program works for your test, but I still got WA.
What's wrong? Thanks for your time.

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

Post by mf » Tue Aug 15, 2006 3:28 pm

I guess, Martin mistakenly pasted output of your program, instead of the correct output.
Answer for that test should '460886630400' (i.e. the product of all numbers in the sequence.)

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 » Tue Aug 15, 2006 8:25 pm

mf wrote:I guess, Martin mistakenly pasted output of your program, instead of the correct output.
Answer for that test should '460886630400' (i.e. the product of all numbers in the sequence.)
Oops, sorry :oops: I'm going to fix it.

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

Post by w k » Wed Aug 16, 2006 8:31 pm

Who knows :-?

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko » Wed Aug 16, 2006 8:48 pm

It took me a while to figure out what you were referring to, w k. If I am right - yes, product of one number is the number itself, unless specified otherwise. It is one of those conventions that make life easier. It comes from another one - the product of no elements is 1.

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 » Wed Aug 16, 2006 10:22 pm

Darko wrote:It comes from another one - the product of no elements is 1.
which, however, does not apply in this problem. :wink:

User avatar
newton
Experienced poster
Posts: 162
Joined: Thu Jul 13, 2006 7:07 am
Location: Campus Area. Dhaka.Bangladesh
Contact:

Post by newton » Sat Mar 31, 2007 12:04 pm

i have a little missunderstanding about the problem.
please check my code. you can find it but i cant.
so please help me

Code: Select all



int main()
{	
	long int num,num1,i,max_min;
	long res;
	int test = 1;
	while(scanf("%ld",&num)==1)
	{
		res = 1;
		max_min = -100000;
		for(i=0;i<num;i++)
		{

			scanf("%ld",&num1);
			if(num1==0)
					continue;
			if(num1<0)
			{
				if(num1 > max_min)
					max_min = num1;
			}
			res = res * num1;
		}
		if(res<0)
			res /= max_min;
		printf("Case #%d:",test++);
		printf("The maximum product is %ld\n\n",res);
	}
	return 0;
}


newton.................................. simply the best

User avatar
rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Post by rio » Sat Mar 31, 2007 12:23 pm

INPUT

Code: Select all

3
2 0 2
The answer should be 2, but your code outputs 4.

User avatar
newton
Experienced poster
Posts: 162
Joined: Thu Jul 13, 2006 7:07 am
Location: Campus Area. Dhaka.Bangladesh
Contact:

Post by newton » Sat Mar 31, 2007 12:28 pm

why and how 2?
pls

User avatar
rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Post by rio » Sat Mar 31, 2007 12:37 pm

The problem statements say:
Given a sequence of integers S = {S1, S2, ..., Sn}, you should determine what is the value of the maximum positive product involving consecutive terms of S. If you cannot find a positive sequence, you should consider 0 as the value of the maximum product
Consecutive terms mean { Si , Si+1, Si+2, .., Si+k } (1 <= i, i + k <= n, k >= 0), and its product menas Si * Si+1 * Si+2 * ... * Si+k.

Post Reply

Return to “Volume 110 (11000-11099)”