787 - Maximum Sub-sequence Product

[@ce]

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.

[brianfry713]

Use class Main.
http://uva.onlinejudge.org/index.php?op ... &Itemid=30

[@ce]

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

[sdipu]

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

[brianfry713]

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.

[sdipu]

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.

[AmirAz]

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]

Next time post in the existing thread.
Read this thread for ideas to speed up your code.

[Repon kumar Roy]

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]

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