787 - Maximum Sub-sequence Product

Moderator: Board moderators

does anyone know what input can cause TLE ?
Red Scorpion
Experienced poster

Posts: 192
Joined: Sat Nov 30, 2002 5:14 am

TLE, does anybody know?
Red Scorpion
Experienced poster

Posts: 192
Joined: Sat Nov 30, 2002 5:14 am

What complexity do you have? If O(n^2) and using long arithmetic then TL is for sure
I used O(n^2) and long arithmetic, BUT with an effective prunning...
Dmytro Chernysh
Experienced poster

Posts: 146
Joined: Sat Apr 26, 2003 2:51 am

Before I got TLE, I solved it using method like greedy. The complexity is O(n), and I think that won't cause TLE.

Maybe you've some test case that will cause TLE, dima?

Huge Thanks.
RS
Red Scorpion
Experienced poster

Posts: 192
Joined: Sat Nov 30, 2002 5:14 am

I got AC again.
Thanks Dima.
Red Scorpion
Experienced poster

Posts: 192
Joined: Sat Nov 30, 2002 5:14 am

787 WA..

I made my own bignumber class. (Also tested) And I use it for this problem...

I use O(n) algorithm to find positive production range ( the range with positives and even number of negatives.)

I wanna check my input and output...

Sample Input

-22165 26479 -30519 20570 21926 5461 -21760 19738 36 27996 26762 -21056 30496 -27578 -6652 -27655 -20486 -31160 -28640 11541 14781 21432 23522 26284 -8197 -7811 3018 -28177 26892 14295 -31414 6973 10577 -3631 16027 27842 27069 0 -22384 -20330 0 16401 30008 30633 -14477 -30858 18218 -17872 2837 7162 -11021 17405 -2486 9615 13879 -28512 18646 -1848 1640 -19757 15290 25717 -7745 31105 12707 12384 18951 22423 -20775 -31483 0 15212 22839 0 -30427 -329 2251 -22681 -22867 -29718 26530 -10644 18488 -29655 -19421 -11108 -6057 -7607 17735 0 -9881 31161 19245 8341 -2859 -5528 6160 -24326 18318 -4336 -999999
-12322 -31146 23548 24491 16532 3482 13181 -21641 -17745 -5503 -20940 6887 16502 24447 -29545 -9168 18961 -13417 31742 -21060 -29726 7202 -20215 29383 -16062 -27474 28252 -18989 6329 1610 -31729 -18340 -10294 -1337 -30863 -9730 0 3394 -8002 15081 -22972 11779 23548 29783 -32501 -2386 18170 17087 -24231 0 -26651 -26379 -28607 -30161 21351 17374 -29223 17373 27731 6793 -21493 4524 20322 28483 17977 -16283 11095 15433 -5808 -4936 14355 -14502 -18488 -29311 4017 -16961 -29585 32613 17892 -14119 -27733 -482 22927 18969 -26169 -19027 -23717 -7768 5765 31088 -28227 -13999 -3537 -22907 25355 -962 -17921 13481 -14275 7573 -999999
8322 21717 -10797 -29791 20678 -6242 -5160 1168 28413 0 16393 -669 23285 0 9035 -19076 6160 16721 -14563 26099 -1460 3678 7577 23569 18219 -16947 17835 8024 30656 -24612 738 -14144 23251 11361 0 -18950 -5016 29529 25918 -14165 0 18555 -9183 29628 -342 21040 31547 -15098 23254 -19545 -9742 8273 -28635 -22595 14795 -2412 31055 -11644 10756 -8647 29249 17600 20869 -13497 -10401 25636 -14768 -30400 -4666 -30848 0 12844 20477 -29911 -25775 1171 0 -23297 2993 -16334 -16114 0 -4576 12891 -25672 -14711 -15353 -29261 6576 -32488 -3103 3660 27136 -26808 -22005 -16303 -22470 26824 3803 15235 -999999
-12292 27008 13550 -9724 28115 7259 5702 -24353 -13365 -28595 29803 -5298 0 -14174 32373 -18365 -15496 -2676 0 21579 23838 31103 -15289 9818 32038 -1544 -9397 11039 -29208 12825 -23786 570 -5824 -2784 -19083 21611 -1643 828 14674 -20608 32766 -20420 -13623 -27007 -26453 4632 2417 16916 -221 -24428 -8109 28989 17268 28241 15245 3123 -23680 0 -28961 -24436 0 -10194 26697 -5795 1310 -26326 11345 -4449 28457 30756 -20499 -6512 22024 16704 31188 19172 5089 -270 29024 -9080 -28119 24741 27271 30575 20263 -1877 30685 10185 8838 -32245 8621 1449 -26041 -28017 -23869 -3846 21364 -1172 0 4249 -999999
18193 -4599 27598 19215 0 24293 -6260 8487 -19551 -13394 -21763 -24006 -6237 1046 -24059 -12109 18970 -18668 -15543 -24140 -11028 -9073 2718 28017 6724 8947 -21398 1659 -8002 -4474 -8395 -10336 7064 -3863 10145 700 13925 2156 22774 10876 -24118 21628 -19612 5067 32032 -1459 17686 -32060 -15137 -14904 18321 14393 -27320 -30578 1061 31403 -31683 -23767 2636 -9706 -4248 -14844 1442 -12007 4453 21466 -32478 5015 0 26605 -26811 28362 2613 31378 14806 15011 32714 -21234 5682 3330 -20078 -8478 -8786 -2775 -28936 -3332 13775 -18614 -23259 26582 -13559 10090 17603 -22199 8355 30649 30385 -25255 -30808 -29049 -999999
-18788 6576 -19105 -18899 -23657 11601 -4011 29909 -15444 -14890 -10785 24126 30015 -9449 -10825 -9604 -19843 -14452 -12128 10538 9397 -29015 -817 -27968 -13028 8815 19452 -10554 9232 24279 -28805 2293 -19437 21778 -2682 -27910 28120 -1914 777 -13893 -21785 -3560 -13761 26778 -14682 19620 13737 0 29382 -10129 -15436 260 19117 5627 17800 23888 22068 -8221 -13429 -10896 6712 -19371 16680 -5916 25393 0 -13137 -15130 -9496 25324 -8960 29201 -25391 -10921 -23105 7062 11877 3217 5015 -16757 4401 -11126 27531 -31295 19568 -22570 -23426 -17426 -21479 16493 -22235 0 31723 15610 5624 9732 19073 2566 -12229 2325 -999999
14818 15694 6475 19563 31299 -27199 -14388 -28500 28147 3605 26703 -13900 -29311 -10724 -19531 30503 -26632 -19436 -25269 -12927 -4834 0 86 -16361 8707 -4015 -2462 -1005 -1457 15065 10692 -1520 -32205 -25042 9342 4196 -16465 24939 -27995 13602 14933 8569 -13659 11768 29002 0 -16537 14210 7390 28552 -30249 -22778 -24117 -20453 16801 32064 -18458 22120 2121 5154 -7559 17545 452 14514 -30760 -23023 -25935 -15346 14392 22595 -4921 5316 18074 -23098 30370 24849 -1338 18908 7032 -25656 2470 -538 -13485 11961 -32231 -26511 3773 23330 17317 -1173 -10847 3128 13690 0 -25882 16769 -18628 13980 27475 19603 -999999
-433 -7498 -30936 -28318 0 -1770 13581 -26849 -27583 -2357 -11289 14258 -12863 -32450 23706 -692 -18981 21246 20040 -970 16947 -21803 42 -31434 12111 4591 0 12900 -27495 -9815 17161 -32003 8541 30594 8540 -31216 11699 9999 16637 -7921 20591 0 -26960 5887 -10148 28335 10399 12415 23465 29968 9871 21773 1959 -25583 -31115 -2974 7048 -5478 11795 -25089 21729 30104 22648 -24080 24397 26879 23253 27674 -16137 -24058 -6992 30351 25041 -21910 -9874 -4844 -29177 -28571 -31363 28649 -18382 17882 30026 28897 -5422 -8884 9348 -8833 10085 24302 28867 29875 -23370 29363 -24905 26061 -8090 1514 -29701 2805 -999999
-8596 3001 -17869 8663 -32725 13657 -1757 6026 0 -31665 -19954 26547 842 -5368 23813 -5944 13439 7857 -32184 -19599 -16013 -10306 18678 12222 31511 0 -14527 7512 -16947 -19532 -4526 -13068 29936 12194 -888 -14259 -6956 30546 -26104 0 -27883 23408 3600 12039 0 6941 0 -20464 -24219 11431 -16028 -29999 13184 27392 4429 24637 -6102 -12308 0 -10022 -16639 -833 -7922 -3268 19244 18910 10297 3979 15974 5264 12697 1176 12304 -15840 -32627 26934 -16323 3895 -21509 0 -454 28048 14783 -27461 18608 20083 26882 6408 -12764 7686 21237 26077 -30033 -31716 -484 -26475 -27515 -22548 -19350 -16501 -999999
-14821 2870 21674 -5668 1078 31729 11824 0 0 -8053 -23174 -1922 28125 0 -30049 -21546 -15989 21760 -15987 2394 8076 -4189 -1941 0 -8888 -27348 -31865 -2906 -8912 17825 0 9817 -26408 -30111 -22781 -15338 16383 -3966 5105 -398 -17324 11788 0 29911 19947 24348 -17462 12152 20698 28953 -1543 -28242 18164 18705 30199 -7052 24827 -4051 24314 -30803 -12632 3180 4641 -21410 -29852 20247 -28600 -25679 -8757 -15722 11936 0 -31479 -10539 0 602 -16662 -9148 5914 -16332 -26848 12412 -22308 -27516 -11276 23889 -31477 25224 28260 -12357 -21284 -13486 7143 -19678 -6932 0 0 -27820 11178 -21790 -999999
0 -999999
1 -999999
-1 -999999
0 0 -999999
1 2 3 -999999
-1 2 3 -4 -999999
-1 2 -3 4 -5 6 -7 -999999

Sample Output

660186924239300256381331965323884123873139906107331665003767312706724979159613907582932273035154653533755587464919791869709718460459040781631488000000
6355560515408507362219170874059270132704493845218762747178041418961748542996137556871354827133525531059205389180298673935708618324452505879348190709889774752594581051538872881382560943640893145738117120000000
1229556356276566700688120448874948287779852414764266483733354720315268895704334831375446375513723353093583667200000000000
148145008991443564691425237116514446573916621976027617080411504174283740339788649727781333741254885659696913661447305265331428326923902857833873408000000
2419441812276434370864857986522664117329216166463717838690027606303743023681089339896893297338473333122864934955436115986232376504861595470429145033350623321320866424363292680929903765672699250536968094209137835964043934023930215653363941376000000000000
22883970382617495241466466478795923488314338164748097500630109045177339572256803048946032246085652882746890496670809428753662281687280346794087564999491679393082101419789516800000000000000
1117984860563396802973841750545641928238064132554190192024113442440893015392223312998823609111883539956548997305668096781653150238943192716129363270212836598139288620697124864000000000000
46488791307504980095808885780656216406273082607273964872648172970572968594055539306884883780978407049848001128961722222122569647582775501439753896263218688375580964768009778065215934341978907551071378568839935986870763126784000000000000000
2649134326913650238460143823061232532241960872710763107953771109199878553600000
6807191240356465934497464421360453774160405998158666609044829647508500903382879498959387161950195076300800000
0
1
-1
0
6
24
5040

A farmer learns more from a bad harvest than a good one.
Sanghack
New poster

Posts: 16
Joined: Wed Jul 17, 2002 5:55 pm
Location: Seoul, Korea

My output is exactly the same as yours, except the 9th data set.
Code: Select all
`96284946097802076178041482872981052895428626344934586000760301922703074918400000`

and yours:
Code: Select all
`2649134326913650238460143823061232532241960872710763107953771109199878553600000`

Good Luck!
LittleJohn
Learning poster

Posts: 83
Joined: Wed Feb 27, 2002 2:00 am
Location: Taiwan

OH... Thanks...

I found that...

[cpp]bool isBiggerThan(UnsignedBigNum dest){
if(size > dest.size){
return true;
}
else if(size==dest.size){
for(int i=0;i<size;i++){
if(num[i] > dest.num[i])
return true;
}
return false;
}
else
return false;
}[/cpp]

[cpp]bool isBiggerThan(UnsignedBigNum dest){
if(size > dest.size){
return true;
}
else if(size==dest.size){
for(int i=0;i<size;i++){
if(num[i] > dest.num[i])
return true;
if(num[i] < dest.num[i])
return false;

}
return false;
}
else
return false;
}[/cpp]

Oh my poor -_-;[/cpp]
A farmer learns more from a bad harvest than a good one.
Sanghack
New poster

Posts: 16
Joined: Wed Jul 17, 2002 5:55 pm
Location: Seoul, Korea

I am trying to solve the Maximum Sub-sequence Product problem, but I keep on getting WA. My program passes al the test cases I could find and create.
Does anyone have some other test cases or knows about some tricks?

My program uses bignums and dinamic programing.
It's complexity is O( n )

Thank you!
sluga
New poster

Posts: 20
Joined: Sun Jan 22, 2006 10:48 pm
Location: Croatia

787

I spend the whole afternoon in solving the problem but I always got WA.
I tested the Input which i got from some topic in the forum and printed the Right output.

I don't know Why I always got WA.

is there any special points?

Code: Select all
`  Finally I got Ac.  I made a mistake in comparing two big number.`

Last edited by Planeyang on Sun Nov 05, 2006 3:01 pm, edited 1 time in total.
Planeyang
New poster

Posts: 9
Joined: Sun Oct 15, 2006 1:31 pm
Location: China

Try the I/O set. Your code returns wrong.

Input:
Code: Select all
`-100 2 -1 0 101 -999999`

Output:
Code: Select all
`200`

Hope it helps.
Ami ekhono shopno dekhi...
HomePage
Jan
Guru

Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm

Thansk!!

Thank you very much Jan.

I find my mistake.

You're really a great helper
Planeyang
New poster

Posts: 9
Joined: Sun Oct 15, 2006 1:31 pm
Location: China

Ami ekhono shopno dekhi...
HomePage
Jan
Guru

Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm

Re: 787 - Maximum Sub-sequence Product

getting RTE pls help
Code: Select all
`import java.util.Scanner;import java.math.BigInteger;import java.util.*;import java.io.*;public class Main {    public static void main(String[] args) {        BigInteger pro,mx;        int n,i,c,j,k;        int ar[]=new int[200];        Scanner scn=new Scanner(System.in);        while (scn.hasNextInt())        {            n=scn.nextInt();            ar[0]=n;            k=1;            while(scn.hasNextInt())            {                n=scn.nextInt();                if(n==-999999) break;                ar[k++]=n;            }            pro=BigInteger.ONE;            mx=BigInteger.valueOf(ar[0]);            for(i=0;i<k;i++)            {                pro=BigInteger.valueOf(ar[i]);                if(pro.compareTo(mx)>0)  mx=pro;                for(j=i+1;j<k;j++)                {                    pro=pro.multiply(BigInteger.valueOf(ar[j]));                    if(pro.compareTo(mx)>0)  mx=pro;                }            }            System.out.println(mx);        }    }}`
Learning poster

Posts: 74
Joined: Fri May 08, 2009 5:16 pm

Re: 787 - Maximum Sub-sequence Product

Jehad Uddin wrote:getting RTE pls help
Code: Select all
`import java.util.Scanner;import java.math.BigInteger;import java.util.*;import java.io.*;public class Main {    public static void main(String[] args) {        BigInteger pro,mx;        int n,i,c,j,k;        int ar[]=new int[200];        Scanner scn=new Scanner(System.in);        while (scn.hasNextInt())        {            n=scn.nextInt();            ar[0]=n;            k=1;            while(scn.hasNextInt())            {                n=scn.nextInt();                if(n==-999999) break;                ar[k++]=n;            }            pro=BigInteger.ONE;            mx=BigInteger.valueOf(ar[0]);            for(i=0;i<k;i++)            {                pro=BigInteger.valueOf(ar[i]);                if(pro.compareTo(mx)>0)  mx=pro;                for(j=i+1;j<k;j++)                {                    pro=pro.multiply(BigInteger.valueOf(ar[j]));                    if(pro.compareTo(mx)>0)  mx=pro;                }            }            System.out.println(mx);        }    }}`

Have you tried the test cases in this thread since I bet you will encounter the RTE again by testing those data.
Have you ever...

Wanted to work at best companies?
Struggled with interview problems that could be solved in 15 minutes?
Wished you could study real-world problems?
If so, you need to read Elements of Programming Interviews.
DD
Experienced poster

Posts: 145
Joined: Thu Aug 14, 2003 8:42 am
Location: Mountain View, California

PreviousNext