787 - Maximum Sub-sequence Product

[konsept]

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[i] );
if ( num[i]==-999999 )
break;

m=1;
for ( j=i; j>=0; j-- ){
m*=num[j];
k=max(k,m);
}
i++;
}

printf( "%dn", k );
}

return 0;
}

[junjieliang]

You can get a integer overflow.

[konsept]

I don't think integer overflow is a causing the problem because when I changed the answer from an "int" to a "long long" (64 bits) I still got a wrong answer.

[Ilham Kurnia]

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>

[konsept]

hmm.
I was hoping it wouldn't come to this, but this problem obviously requires special big integer methods.

thanks.

[Jorge Pinto]

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>

[chrismoh]

I haven't solved it yet, but I have thought of an O(n) algorithm which I am sure is correct.

Its just very irritating to implement big numbers...

[Jorge Pinto]

well.. you just have to do it once in a life time, the next time you need it, just copy/paste or adapt the code.

you don't have to reinvent the wheel everytime

anyway, shoot the ideia, i would like to know what you think about it

[konsept]

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[i]*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).

[Ilham Kurnia]

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>

[Jorge Pinto]

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

[chrismoh]

Storing P[1],P[2],...P[n] is unnecessary. That algorithm still runs in O(n^2) time.

Linear time solution uses a sorta "greedy" method.

[Ilham Kurnia]

please elaborate...
i'm very interested in correct greedy approach.

[chrismoh]

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...

[Red Scorpion]

Hi, after rejudged why I got TLE ?
can anyone tell me what's they change ?

Thanks,
RS