11059  Maximum Product
Moderator: Board moderators

 Learning poster
 Posts: 81
 Joined: Wed May 09, 2007 9:59 pm
 Location: (CSE,DU) Dhaka,Bangladesh
11059  Maximum Product
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!!

 Learning poster
 Posts: 81
 Joined: Wed May 09, 2007 9:59 pm
 Location: (CSE,DU) Dhaka,Bangladesh
11059, WA,help ples,
this my code: i don't know whats the problem. i also use the long long int
here my code:
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.

 New poster
 Posts: 12
 Joined: Sat Aug 18, 2007 11:09 pm
 Location: CSE, University of Dhaka
Turcse,
check your indexing. I found your code assigns uninitialized maxp[] values to c in the following code fragment 
here verify that all your maxp's are valid or initialized earlier.
Also check the following I/O:
Sample Input:
Sample output:
check your
Code: Select all
maxp[]
Code: Select all
if(c<maxp[i])
c=maxp[i];
Also check the following I/O:
Sample Input:
Code: Select all
3
0 2 3
2
0 2
Code: Select all
Case #1: The maximum product is 3.
Case #2: The maximum product is 0.

 Learning poster
 Posts: 81
 Joined: Wed May 09, 2007 9:59 pm
 Location: (CSE,DU) Dhaka,Bangladesh
WA again help ples!!!!!!!!
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
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

 New poster
 Posts: 12
 Joined: Sat Aug 18, 2007 11:09 pm
 Location: CSE, University of Dhaka
turcse143,
I found your approach is somehow wrong. Consider the following samples 
Sample Input:
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:
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
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.
Re: 11059  Maximum Product
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.
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.
This may be the address of success.

 Experienced poster
 Posts: 196
 Joined: Wed May 02, 2007 10:12 pm
 Location: Hungary, Pest county, Halasztelek
 Contact:
Re: 11059  Maximum Product
Your algorithm fails on: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...
Code: Select all
2
1 1
Re: 11059  Maximum Product
Help!!!
I tried many sample input and got the correct answer.
But I still got WA.
THX~
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],ia,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],xa,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[nz1]; 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;
}
}

 Experienced poster
 Posts: 136
 Joined: Sat Nov 29, 2008 8:01 am
 Location: narayangong,bangladesh.
 Contact:
WA?11059  Maximum Product
why the output of
4
5 9 7 8
should be 315!!.
is 'nt it 360???
because it is maximum.
can annyone explain plz.
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://felixhalim.net/uva/hunting.php?id=32359
For Hints: http://salimsazzad.wordpress.com
http://felixhalim.net/uva/hunting.php?id=32359
For Hints: http://salimsazzad.wordpress.com
Re: 11059  Maximum Product
The problem asks for the maximum positive
product involving consecutive terms. That's
why the answer is 315 in your example.
product involving consecutive terms. That's
why the answer is 315 in your example.
Re: 11059  Maximum Product
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?
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();
}
Re: 11059  Maximum Product
No it doesn't! It outputsi ve tried all the sample input and my program generates correct output.
Code: Select all
Case #1: The maximum product is 8.Case #2: The maximum product is 20.
From http://onlinejudge.uva.es/p/v110/11059.html:
After each test case you must print a blank line.