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

dipaly
New poster
Posts: 20
Joined: Tue Sep 19, 2006 6:18 pm
Location: bangladesh
Contact:

:)

Post by dipaly » Fri Aug 31, 2007 4:14 pm

thanks :) ....... ac now
everything is so hard to me

turcse143
Learning poster
Posts: 81
Joined: Wed May 09, 2007 9:59 pm
Location: (CSE,DU) Dhaka,Bangladesh

11059 - Maximum Product

Post by turcse143 » Sun Dec 09, 2007 11:55 pm

8)
here my sample input & output i got WA
INPUT:
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

3
2 0 2

2
-1 1

3
-9 -7 -8

12
4 5 5 3 0 7 -3 0 10 2 4 -1

3
-1 0 -1

OUTPUT:

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.

Case #10: The maximum product is 2.

Case #11: The maximum product is 1.

Case #12: The maximum product is 63.

Case #13: The maximum product is 300.

Case #14: The maximum product is 0.
Press any key to continue

I DON'T UNDERSTAND WHAT'S THE PROBLEM.
SOMEONE PLES HELP!!

User avatar
CMG
New poster
Posts: 37
Joined: Sat Dec 08, 2007 5:01 am
Location: ...

Post by CMG » Mon Dec 10, 2007 2:52 am

I just tried doing this problem and I got WA as well. My program has the same output as yours for that set of input. I also submitted a program that gave -1 for case #9 but still WA.

EDIT: Ah needed to use a long to keep maximum product. Got AC now.

turcse143
Learning poster
Posts: 81
Joined: Wed May 09, 2007 9:59 pm
Location: (CSE,DU) Dhaka,Bangladesh

11059, WA,help ples,

Post by turcse143 » Sun Dec 16, 2007 2:36 pm

this my code: i don't know whats the problem. i also use the long long int :cry:
here my code:

Code: Select all

  code removed after accepted
Last edited by turcse143 on Sun Dec 16, 2007 5:47 pm, edited 1 time in total.

ashis.csedu
New poster
Posts: 12
Joined: Sat Aug 18, 2007 11:09 pm
Location: CSE, University of Dhaka

Post by ashis.csedu » Sun Dec 16, 2007 3:01 pm

Turcse,
check your

Code: Select all

maxp[]
indexing. I found your code assigns uninitialized maxp[] values to c in the following code fragment -

Code: Select all

if(c<maxp[i])
	c=maxp[i];
--here verify that all your maxp's are valid or initialized earlier.

Also check the following I/O:
Sample Input:

Code: Select all

3
0 -2 3
2
0 -2
Sample output:

Code: Select all

Case #1: The maximum product is 3.

Case #2: The maximum product is 0.

turcse143
Learning poster
Posts: 81
Joined: Wed May 09, 2007 9:59 pm
Location: (CSE,DU) Dhaka,Bangladesh

WA again help ples!!!!!!!!

Post by turcse143 » Sun Dec 16, 2007 3:25 pm

ashis da i check and correct but again got WA.
This my some other output. ples check it
4
0 -2 -2 3
Case #1: The maximum product is 12.
4

0 -2 3 -2
Case #2: The maximum product is 12.
4

1 -2 0 0
Case #3: The maximum product is 1.
5

0 -2 0 0 1
Case #4: The maximum product is 1.
5

0 -2 0 0 -1
Case #5: The maximum product is 0.

IS output format correct

ashis.csedu
New poster
Posts: 12
Joined: Sat Aug 18, 2007 11:09 pm
Location: CSE, University of Dhaka

Post by ashis.csedu » Sun Dec 16, 2007 4:33 pm

turcse143,
I found your approach is somehow wrong. Consider the following samples -

Sample Input:

Code: Select all

5
1 2 -1 3 5
18
1 2 3 4 5 -1 2 2 3 4 5 7 4 2 1 0 -3
You are keeping two information - maxn[] the maximum negative values and maxp[]: the maximum positive values, right?

But you reinitialized the maxp[] in a wrong way as I found in the above two simulations.

Think of the first sample
your approach is
maxp[] = 1, 2, ******, 6, 30

You continue keeping maxp[] after getting a negative number, so this sample input fails. Keep reinitialize maxp[] correctly.

I am giving sample output for the given two inputs:

Code: Select all

Case #1: The maximum product is 15.

Case #2: The maximum product is 13440.

turcse143
Learning poster
Posts: 81
Joined: Wed May 09, 2007 9:59 pm
Location: (CSE,DU) Dhaka,Bangladesh

Post by turcse143 » Sun Dec 16, 2007 5:45 pm

Thanks ashis da i got AC

Obaida
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am
Location: (BUBT) Dhaka,Bagladesh.

Re: 11059 - Maximum Product

Post by Obaida » Tue May 27, 2008 8:09 am

I don't know how many times i got WA. and don't know how many time i wasted for it. :-?
But i think I am in a wrong way and thats why I am getting WA...
Can someone specify this.

Code: Select all

Thanks Robert.
Last edited by Obaida on Tue May 27, 2008 10:34 am, edited 1 time in total.
try_try_try_try_&&&_try@try.com
This may be the address of success.

Robert Gerbicz
Experienced poster
Posts: 196
Joined: Wed May 02, 2007 10:12 pm
Location: Hungary, Pest county, Halasztelek
Contact:

Re: 11059 - Maximum Product

Post by Robert Gerbicz » Tue May 27, 2008 9:10 am

Obaida wrote:I don't know how many times i got WA. and don't know how many time i wasted for it. :-?
But i think I am in a wrong way and thats why I am getting WA...
Your algorithm fails on:

Code: Select all

2
-1 -1

a96374177
New poster
Posts: 1
Joined: Sat Aug 16, 2008 8:55 am

Re: 11059 - Maximum Product

Post by a96374177 » Sat Aug 16, 2008 9:01 am

Help!!!
I tried many sample input and got the correct answer.
But I still got WA.
THX~

Code: Select all

#include<iostream>
using namespace std;

long long subseq(int* seq,int number,int nz,int zero);

int main()
{
	int n,*seq,nz,*pos,count=0,zero,x;
	long long max,tmp,prod;
	while(cin>>n){
		x=n;
		++count;
		seq=new int[n];
		zero=max=nz=0;
		prod=1;
		for(int i=0; i<n; i++)
			seq[i]=-20;
		int j=-1;
		for(int i=0; i<n; i++){
			cin>>tmp;
			if(tmp==0){ 
				if(seq[j]==0) continue;
				zero++;
				nz++;
				seq[++j]=0; 
				prod=1; 
			}
			if(tmp<0){ 
				seq[++j]=tmp; 
				nz++; 
				prod=1; 
			}
			if(tmp>0){ 
				if(i==0 || prod==1) ++j;
				prod*=tmp; 
				seq[j]=prod; 
			}
		}
		for(int i=0; i<n; i++)
			if(seq[i]==-20){ x=i; break; }
		if(nz<=1 || (nz==2 && zero!=0) || !zero){
			max=subseq(seq,x,nz,zero);
			cout<<"Case #"<<count<<": The maximum product is "<<max<<"."<<endl<<endl;
			continue;
		}
		int a,b;
		max=nz=a=0;
		for(int i=0; i<x; i++){
			if(seq[i]==0 && a<i){
				tmp=subseq(&seq[a],i-a,nz,0);
				if(tmp>max) max=tmp;
				a=i+1;
				nz=0;
			}else if(seq[i]<0)
				nz++;
		}
		if(a!=x){
			tmp=subseq(&seq[a],x-a,nz,0);
			if(tmp>max) max=tmp;
		}
		cout<<"Case #"<<count<<": The maximum product is "<<max<<"."<<endl<<endl;
	}
	return 0;
}

long long subseq(int* seq,int n,int nz,int zero)
{
	int *pos;
	long long max=0,prod=1;
	if(nz<=1 || (nz==2 && zero!=0)){
		for(int i=0; i<n; i++)
			if(seq[i]>max) max=seq[i];
		return max;
	}
	pos=new int[nz];
	for(int i=0; i<nz; i++)
		pos[i]=-1;
	int j=0;
	for(int i=0; i<n; i++)
		if(seq[i]<=0) pos[j++]=i;
	prod=1;
	if(!(nz%2)){
		for(int i=0; i<n; i++)
			prod*=seq[i];
		max=prod;
		return max;
	}else{
		max=0;
		prod=1;
		for(int i=0; i<pos[nz-1]; i++)
			prod*=seq[i];
		max=prod;
		prod=1;
		for(int i=pos[0]+1; i<n; i++)
			prod*=seq[i];
		if(prod>max) max=prod;
		return max;
	}
}

sazzadcsedu
Experienced poster
Posts: 136
Joined: Sat Nov 29, 2008 8:01 am
Location: narayangong,bangladesh.
Contact:

WA?11059 - Maximum Product

Post by sazzadcsedu » Sun Feb 22, 2009 11:41 pm

why the output of
4
5 -9 -7 -8
should be 315!!.
is 'nt it 360???
because it is maximum.
can annyone explain plz.
Life is more complicated than algorithm.
http://felix-halim.net/uva/hunting.php?id=32359
For Hints: http://salimsazzad.wordpress.com

User avatar
Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Re: 11059 - Maximum Product

Post by Sedefcho » Mon Feb 23, 2009 1:15 am

The problem asks for the maximum positive
product involving consecutive terms
. That's
why the answer is 315 in your example.

robz84
New poster
Posts: 3
Joined: Thu Aug 06, 2009 8:28 pm
Location: Hungary

Re: 11059 - Maximum Product

Post by robz84 » Thu Aug 06, 2009 8:50 pm

Hi!

I get WA and i dont know why. i ve read all the post in this topic, i ve tried all the sample input and my program generates correct output.
i tried that no newline after the last output, 1 newline after the last output, two newline....., but i still get WA. its very annoying.
my first algorithm is a simple n^2 brute force alg in java, its so simple, it's tries all the possibilites, so i dont know how i get WA..
the long maximum value in java is : 9223372036854775807 , so there is no overflow problem.
Has anyone a hint?

Code: Select all

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String line = null;
		StringTokenizer st = null;
		int c = 1;
		
		boolean first = true;
		
		while((line = br.readLine())!=null) {
			
			//if (!first) 					// no newline after the last output
			//	System.out.println("\n");
			//first = false;
				
			int n = Integer.parseInt(line);
			int[] S = new int[n];
			st = new StringTokenizer(br.readLine());
			br.readLine();
			
			for (int i = 0; i<n; i++)
				S[i] = Integer.parseInt(st.nextToken());
			
			long product = 1;
			long max = 0;
			
			for (int i = 0; i<n; i++) {
				for (int j = i; j<n; j++) {
					for (int k = i; k<=j; k++)
						product*=S[k];
					if (product>max)
						max = product;
					product = 1;
				}
			}
			System.out.print("Case #"+c+++": The maximum product is "+max+".");
		}
		br.close();
	}

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

Re: 11059 - Maximum Product

Post by mf » Thu Aug 06, 2009 9:08 pm

i ve tried all the sample input and my program generates correct output.
No it doesn't! It outputs

Code: Select all

Case #1: The maximum product is 8.Case #2: The maximum product is 20.
Notice anything wrong with it?


From http://online-judge.uva.es/p/v110/11059.html:
After each test case you must print a blank line.

Post Reply

Return to “Volume 110 (11000-11099)”