787 - Maximum Sub-sequence Product
Moderator: Board moderators
787 - Maximum Sub-sequence Product
What is wrong with this simple brute force
solution???!
#include <stdio.h>
#include <string.h>
#define max(x,y) ( (x)>(y)?(x):(y) )
int num[101];
int k;
int main( void ){
int i,j,m;
while ( scanf( "%d", &num[0] )>0 ){
k=num[0];
i=1;
while ( 1 ){
scanf( "%d", &num );
if ( num==-999999 )
break;
m=1;
for ( j=i; j>=0; j-- ){
m*=num[j];
k=max(k,m);
}
i++;
}
printf( "%dn", k );
}
return 0;
}
solution???!
#include <stdio.h>
#include <string.h>
#define max(x,y) ( (x)>(y)?(x):(y) )
int num[101];
int k;
int main( void ){
int i,j,m;
while ( scanf( "%d", &num[0] )>0 ){
k=num[0];
i=1;
while ( 1 ){
scanf( "%d", &num );
if ( num==-999999 )
break;
m=1;
for ( j=i; j>=0; j-- ){
m*=num[j];
k=max(k,m);
}
i++;
}
printf( "%dn", k );
}
return 0;
}
-
- Experienced poster
- Posts: 169
- Joined: Wed Oct 31, 2001 2:00 am
- Location: Singapore
-
- New poster
- Posts: 31
- Joined: Sat Nov 17, 2001 2:00 am
- Contact:
think again.
99900 99901 99902 99903 99904 99905 99906
99907 99908 99909 99910 99911 99912 99913
99914 99915 99916 99917 99918 99919 99920
99921 99922 99923 99924 99925 99926 99927
99928 99929 99930 99931 99932 99933 99934
99935 99936 99937 99938 99939 99940 99941
99942 99943 99944 99945 99946 99947 99948
99949 99950 99951 99952 99953 99954 99955
99956 99957 99958 99959 99960 99961 99962
99963 99964 99965 99966 99967 99968 99969
99970 99971 99972 99973 99974 99975 99976
99977 99978 99979 99980 99981 99982 99983
99984 99985 99986 99987 99988 99989 99990
99991 99992 99993 99994 99995 99996 99997
99998 99999 -999999
<font size=-1>[ This Message was edited by: Ilham Kurnia on 2002-01-09 23:39 ]</font>
99900 99901 99902 99903 99904 99905 99906
99907 99908 99909 99910 99911 99912 99913
99914 99915 99916 99917 99918 99919 99920
99921 99922 99923 99924 99925 99926 99927
99928 99929 99930 99931 99932 99933 99934
99935 99936 99937 99938 99939 99940 99941
99942 99943 99944 99945 99946 99947 99948
99949 99950 99951 99952 99953 99954 99955
99956 99957 99958 99959 99960 99961 99962
99963 99964 99965 99966 99967 99968 99969
99970 99971 99972 99973 99974 99975 99976
99977 99978 99979 99980 99981 99982 99983
99984 99985 99986 99987 99988 99989 99990
99991 99992 99993 99994 99995 99996 99997
99998 99999 -999999
<font size=-1>[ This Message was edited by: Ilham Kurnia on 2002-01-09 23:39 ]</font>
-
- New poster
- Posts: 11
- Joined: Wed Jan 09, 2002 2:00 am
- Location: Portugal
just solved the problem, got 320ms .. hmm.. big time
i tried with long long, but got WA
so i used strings got AC
(i wonder if anyone used just doubles or long llong, someone has a hint of "floats" in the solved rank list in pascal)
i think my algorithm is pretty fast using strings... still got big 320ms
anyway, konsept: read the program carefully, the answer in a input of A B C D could be
B C
you just did it straight forward to get the same output
the correct answer for ilham's input is:
95073783634185106058480752069956279199041805151309597685850804143872493687225762724265298696680866720060438572638872338185423558516745575068148747617495637233246533038583138313941279391299861732093898219130183367516764321276544576375955285875947586351401575501779450726582846893999985310435777036870171150461994629508009325776347750386998738990303339348062610266452782201995528321494110278961303062035131223129701746286517127149552121601906172064292436146016461554458887716864000000000000000000000000
hope it helps
Jorge Pinto
<font size=-1>[ This Message was edited by: Jorge Pinto on 2002-01-10 13:20 ]</font>
<font size=-1>[ This Message was edited by: Jorge Pinto on 2002-01-10 13:24 ]</font>
i tried with long long, but got WA
so i used strings got AC
(i wonder if anyone used just doubles or long llong, someone has a hint of "floats" in the solved rank list in pascal)
i think my algorithm is pretty fast using strings... still got big 320ms
anyway, konsept: read the program carefully, the answer in a input of A B C D could be
B C
you just did it straight forward to get the same output
the correct answer for ilham's input is:
95073783634185106058480752069956279199041805151309597685850804143872493687225762724265298696680866720060438572638872338185423558516745575068148747617495637233246533038583138313941279391299861732093898219130183367516764321276544576375955285875947586351401575501779450726582846893999985310435777036870171150461994629508009325776347750386998738990303339348062610266452782201995528321494110278961303062035131223129701746286517127149552121601906172064292436146016461554458887716864000000000000000000000000
hope it helps
Jorge Pinto
<font size=-1>[ This Message was edited by: Jorge Pinto on 2002-01-10 13:20 ]</font>
<font size=-1>[ This Message was edited by: Jorge Pinto on 2002-01-10 13:24 ]</font>
-
- New poster
- Posts: 11
- Joined: Wed Jan 09, 2002 2:00 am
- Location: Portugal
The crappy brute force solution is what I wrote 2 seconds after reading the problem, just as a "warm up". I have a much better algorithm now. (this might be what 'chrismoh' was mentioning, I dont' know)
Anyway, the basic idea is this:
if we keep track of the product of the first n numbers in the input (instead of just the nth number) then we can determine the product
of all numbers from i to j ( 1<=i,j<=n ) in constant time.
lets say the numbers are N[1],N[2],...N[n]. we dont store these numbers, instead we store:
P[1]=N[1]
P[2]=N[1]*N[2]
P[3]=N[1]*N[2]*N[3]
...
P[k]=P[k-1]*N[k]
now, observe that N*N[i+1]*N[i+2]*...N[j-1]*N[j]=P[j]/P[i-1].
so to find the product from i to j we need O(1) time instead of O(j-i+1).
Anyway, the basic idea is this:
if we keep track of the product of the first n numbers in the input (instead of just the nth number) then we can determine the product
of all numbers from i to j ( 1<=i,j<=n ) in constant time.
lets say the numbers are N[1],N[2],...N[n]. we dont store these numbers, instead we store:
P[1]=N[1]
P[2]=N[1]*N[2]
P[3]=N[1]*N[2]*N[3]
...
P[k]=P[k-1]*N[k]
now, observe that N*N[i+1]*N[i+2]*...N[j-1]*N[j]=P[j]/P[i-1].
so to find the product from i to j we need O(1) time instead of O(j-i+1).
-
- New poster
- Posts: 31
- Joined: Sat Nov 17, 2001 2:00 am
- Contact:
hmmm... However, if you do it plainly like
that, you're program might be lot slower than
those using O(N^2) LCS since you must use Big
number routine many times. There's still one
more trick involved. This is when the "float"
thing takes place.
<font size=-1>[ This Message was edited by: Ilham Kurnia on 2002-01-11 09:20 ]</font>
that, you're program might be lot slower than
those using O(N^2) LCS since you must use Big
number routine many times. There's still one
more trick involved. This is when the "float"
thing takes place.
<font size=-1>[ This Message was edited by: Ilham Kurnia on 2002-01-11 09:20 ]</font>
-
- New poster
- Posts: 11
- Joined: Wed Jan 09, 2002 2:00 am
- Location: Portugal
i agree with ilham
the sort of dynamic program you are thinking is fine for int types, trying to do the multiplication just one time.
still, its * and / not + and -
put some big numbers multiplying and dividing
the implementation would be much harder and longer (time).. maybe just maybe you could win a few ms
not worth it, still a good algorithm for int's
i will use it if i find a similar problem with int's
the sort of dynamic program you are thinking is fine for int types, trying to do the multiplication just one time.
still, its * and / not + and -
put some big numbers multiplying and dividing
the implementation would be much harder and longer (time).. maybe just maybe you could win a few ms
not worth it, still a good algorithm for int's
i will use it if i find a similar problem with int's
-
- New poster
- Posts: 31
- Joined: Sat Nov 17, 2001 2:00 am
- Contact:
Ok, let's see...
we know that other than at zeroes, the absolute value of the multiple always increases. So we can store the maximal (absolute value) negative and positive product for that current subsequence (a subsequence started and ended by zeroes, for convenience it is always correct to place an arbitrary zero at the start and the end of the input sequence) - you have to of course reset whenever a 0 is encountered...
Of course, one has to deal with special cases such as no positive numbers in a sequence or subsequence...
and naturally this is assuming O(1) time for multiplying...
Here's an example to illustrate the traps faced by this algorithm:
consider the sequence
6 -6 -6 -7 8
At the start, greatest positive integer: 6, Negative: N/A
Next number: -6
Greatest positive integer, N/A
Negative, -36
Next number: -6
Greatest positive integer, 216
Negative, -6
Next number: -7
Greatest positive integer, 42
Negative, -1512
Next number: 8
Greatest positive integer, 336
Negative, -12096
And of course the answer is 336 for this example...
If the last number was 4, then the answer would be 216...
we know that other than at zeroes, the absolute value of the multiple always increases. So we can store the maximal (absolute value) negative and positive product for that current subsequence (a subsequence started and ended by zeroes, for convenience it is always correct to place an arbitrary zero at the start and the end of the input sequence) - you have to of course reset whenever a 0 is encountered...
Of course, one has to deal with special cases such as no positive numbers in a sequence or subsequence...
and naturally this is assuming O(1) time for multiplying...
Here's an example to illustrate the traps faced by this algorithm:
consider the sequence
6 -6 -6 -7 8
At the start, greatest positive integer: 6, Negative: N/A
Next number: -6
Greatest positive integer, N/A
Negative, -36
Next number: -6
Greatest positive integer, 216
Negative, -6
Next number: -7
Greatest positive integer, 42
Negative, -1512
Next number: 8
Greatest positive integer, 336
Negative, -12096
And of course the answer is 336 for this example...
If the last number was 4, then the answer would be 216...
-
- Experienced poster
- Posts: 192
- Joined: Sat Nov 30, 2002 5:14 am
787-TLE after rejudge
Hi, after rejudged why I got TLE ?
can anyone tell me what's they change ?
Thanks,
RS
can anyone tell me what's they change ?
Thanks,
RS