787 - Maximum Sub-sequence Product

All about problems in Volume 7. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

User avatar
@ce
Learning poster
Posts: 71
Joined: Mon May 28, 2012 8:46 am
Location: Ranchi, India

Re: 787 - Maximum Sub-sequence Product

Post by @ce » Mon May 20, 2013 12:01 pm

Getting RE....my code is working for the test cases in this discussion thread...plzz help

Code: Select all

AC
If you are using Java, the class name should be Main. Otherwise u'll get RE.
Last edited by @ce on Tue May 21, 2013 5:53 am, edited 1 time in total.
-@ce

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 787 - Maximum Sub-sequence Product

Post by brianfry713 » Tue May 21, 2013 3:46 am

Check input and AC output for thousands of problems on uDebug!

User avatar
@ce
Learning poster
Posts: 71
Joined: Mon May 28, 2012 8:46 am
Location: Ranchi, India

Re: 787 - Maximum Sub-sequence Product

Post by @ce » Tue May 21, 2013 5:51 am

@brianfry713...thanks a lot for pointing out...
-@ce

sdipu
New poster
Posts: 23
Joined: Sun May 19, 2013 1:50 am

Re: 787 - Maximum Sub-sequence Product

Post by sdipu » Thu Sep 19, 2013 2:15 am

I have checked all possible i/o for this problem. But found no mistake in my code. But OJ showed WA every time I submitted. Please tell me what is wrong here.

Here is my code -

Code: Select all

stupid code removed
Last edited by sdipu on Thu Sep 19, 2013 9:40 pm, edited 1 time in total.
Check out UVA Arena - a software build for UVA solvers @ http://dipu-bd.github.io/UVA-Arena/

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 787 - Maximum Sub-sequence Product

Post by brianfry713 » Thu Sep 19, 2013 9:30 pm

while(!feof(stdin)) won't work as you intended if there is a newline char at the end of the last line in the input.
Check input and AC output for thousands of problems on uDebug!

sdipu
New poster
Posts: 23
Joined: Sun May 19, 2013 1:50 am

Re: 787 - Maximum Sub-sequence Product

Post by sdipu » Thu Sep 19, 2013 9:43 pm

brianfry713 wrote:while(!feof(stdin)) won't work as you intended if there is a newline char at the end of the last line in the input.
Thanks brianfry713. after all the hard work I can't believe it's just the stupid new line character. :-? I will be more carefull from now on.
Check out UVA Arena - a software build for UVA solvers @ http://dipu-bd.github.io/UVA-Arena/

AmirAz
New poster
Posts: 8
Joined: Tue May 20, 2014 12:34 pm

787 - TLE problem with big numbers

Post by AmirAz » Fri Aug 15, 2014 9:20 pm

my algorithm runs on O(n^2) for long long int but I should use strings, so it exceeds the time limit for some inputs like this:

Code: Select all

-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 
Here is my code, I wish you could help me get AC by introducing a new structure to store big numbers in C++. Here is my code:

Code: Select all

#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <set>
#include <algorithm>
#include <ctype.h>
#include <map>
#include <vector>
#include <stack>
#include <climits>
#include <functional>
#include <sstream>
#include <math.h>

using namespace std;
#define lli long long int
#define llu long long unsigned
#define ii pair<int, int>
#define vii vector<ii>
#define vi vector<int>
#define log2(n) log10(n) / log10(2)
#define _left(a) (a<<1)
#define _right(a) _left(a) + 1
#define getMid(a, b) (a + b) /2;
#define mii map<int,int>
#define ll long long int 

string sum(string s1, string s2){
	if (s1 == "0") return s2;
	if (s2 == "0") return s1;
	string result = ""; ll store = 0; ll len = max(s1.size(), s2.size());
	for (ll i = 0; i < len; i++){
		ll pos1 = s1.size() - i -1, pos2 = s2.size() - i-1;
		if (pos1 >= 0) store += s1[pos1] - '0';
		if (pos2 >= 0) store += s2[pos2] - '0';
		result = to_string(store%10) + result;
		store /= 10;
	}
	if (store) result = to_string(store) + result;
	return result;

}

string multiply(string s1, string s2){
	if (s1 == "0" || s2 == "0") return "0";
	string result = "0";
	for (ll i = s2.size() -1; i >= 0; i--){
		ll x = s2[i] - '0'; ll store = 0;
		string extra = "";
		for (ll j = 0; j < s2.size() - i -1; j++) extra+= "0";
		for (ll j = s1.size() -1; j >= 0; j--){
			ll y = s1[j] - '0';
			store += x * y;
			extra = to_string(store % 10) + extra;
			store /= 10;
		}
		if (store) extra = to_string(store) + extra;
		result = sum(result, extra);
	}
	return result;
}
int main(){
	
	string s;
	while (getline(cin, s)){
		stringstream stream(s);
		
		ll x[102]; int size = 0;
		do {
			stream>>x[size];
			size++;
		}while (x[size-1] != -999999);
		size--;
		string max = to_string(abs(x[0]));
		bool maxgre = x[0] >= 0;
		for (int i = 0; i < size; i++){
			string product = "1"; bool progre = true;
			for (int j = i; j < size; j++){
				progre = (x[j]>=0) == progre;
				product=multiply(product, to_string(abs(x[j])));
				if (!x[j]) j = size;
				if (max.size() <= product.size()){
				if (max.size() < product.size()){
					max =product;
					maxgre = progre;
				}
				else if (progre && !maxgre){
					max =product;
					maxgre = progre;
				}
				else if (progre == maxgre &&  progre){
					ll k = 0;
					while (product[k] == max[k] && k != product.size()) k++;
					if (k != product.size() && product[k] > max[k]){
						max =product;
						maxgre = progre;
					}

				}
				else if (progre == maxgre && !progre){
					ll k = 0;
					while (product[k] == max[k] && k != product.size()) k++;
					if (k != product.size() && product[k] < max[k]){
						max =product;
						maxgre = progre;
					}
				}
				}
				

			}
		}
		if (!maxgre) cout << "-";
		cout << max << "\n";
	}
	
	return 0;
}

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 787 - Maximum Sub-sequence Product

Post by brianfry713 » Mon Aug 18, 2014 9:57 pm

Next time post in the existing thread.
Read this thread for ideas to speed up your code.
Check input and AC output for thousands of problems on uDebug!

Repon kumar Roy
Learning poster
Posts: 96
Joined: Tue Apr 23, 2013 12:54 pm

Re: 787 - Maximum Sub-sequence Product

Post by Repon kumar Roy » Sun Sep 21, 2014 7:00 pm

For those getting WA

Input :

Code: Select all

0 -999999
-1 0 -1 0 -999999
0 0 0 -1 0 -999999
-1 -2 -3 -999999
1 2 0 -1 7 -999999
Output:

Code: Select all

0
0
0
6
7

groawr
New poster
Posts: 1
Joined: Sun Nov 15, 2015 3:16 pm

Re: 787 - Maximum Sub-sequence Product

Post by groawr » Sun Nov 15, 2015 3:21 pm

I've tried all the test cases here and also the critical Input and random Input on uDebug with same answer. But I still get WA. Any idea? Here is my code : http://ideone.com/pei4hI
Tried to use the O(n) solution

Post Reply

Return to “Volume 7 (700-799)”