### _Chaitanya1999's blog

By _Chaitanya1999, history, 6 weeks ago,

If you want to directly access the problem you can click here

Problem Statement
You are given array a of n integers. You need to split the array into 2 arrays (one of which may be empty) such that sum of product of these 2 arrays is maximum.
Formally, you need to find l such that sum of a1⋅a2⋅⋯⋅al and al+1⋅al+2⋅⋯⋅an is maximum over all valid choices for l.
Note that an empty array has a product of 0.

Output
Print the maximum sum of product of the arrays mod 1e9+7.

Constraints
1≤n≤1e5 , 1≤|ai|≤1e9

I tried to solve this problem by pre-calculating prefix product and suffix product modulo M(1e9+7) and taking the maximum among every i (1<=i<=n).But still its showing me WA for large inputs of a[i]. Can anyone suggest me where am I making a mistake ?


• -5

 » 6 weeks ago, # |   0 Auto comment: topic has been updated by _Chaitanya1999 (previous revision, new revision, compare).
 » 6 weeks ago, # | ← Rev. 2 →   +23 (x % n) >= (y % n) doesn't imply x >= y
 » 6 weeks ago, # |   +24 Comparing two numbers modulo M is a bad idea, because it can and almost certainly lead to wrong results: for example, let's compare 2 and 1e9 + 8. Obviously, 2 < 1e9 + 8, but if you were to compare these numbers in modulo 1e9 + 7, you get 2 > 1, so you get that 2 > 1e9 + 8. Instead of using modulo, you can calculate these prefix and suffix products under a logarithm, so instead of storing the product itself, you store its logarithm. This way, you can still correctly compare these numbers by comparing their logarithms.
•  » » 6 weeks ago, # ^ | ← Rev. 2 →   0 How do you store a negative number in some base's exponent? isn't the exponent a complex number?
•  » » » 6 weeks ago, # ^ | ← Rev. 2 →   +3 Since you can determine the sign of the product just by looking at how many negative numbers there are, you can take the logarithm of the absolute value (i. e. $|a[i]|$), then you just look at the number of negative numbers to find out the sign of the product.
•  » » » » 6 weeks ago, # ^ | ← Rev. 2 →   0 But exponents may be fractional. I mean won't there be any precision issues?
•  » » » » » 6 weeks ago, # ^ |   +3 If you use long double, which allows a precision of at least 19 decimal places, it should be OK.
 » 6 weeks ago, # |   0 Im not sure but it looks like you need take a whole array except cases a[0] == 1 || a[n — 1] == 1
•  » » 6 weeks ago, # ^ |   0 I think you're right.Let P(i,j) indicate the prodoct from ai to aj.Then if there exist a L which make P(1,L)+P(L+1,n)>P(1,n) hold, we can get 1/P(L+1,n) +1/P(1,L) > 1 by dividing P(1,n).Since even 1/2 + 1/2 = 1, inequality above holds if and only if P(1,L)==0||P(L+1,n)==0.
•  » » » 6 weeks ago, # ^ |   0 it's not absolutely right bcs we have negative numbers (didnt see it before). so we need check some cases when cnt_of_negative is over or odd
•  » » » » 6 weeks ago, # ^ |   0 Not see it before too lol
•  » » » » 6 weeks ago, # ^ | ← Rev. 3 →   0 If the product of all elements is positive, your ideia works, because if a[0] > 1, its obvious better to put a[0] in the product, if a[0] < 0, if we remove a[0] of the product, the answer become negative, so the only case that worth remove a[0] is when a[0] = 1,(the same logic works for a[n-1]).If the product of all elements is negative, i thought in this ideia:Let $a_i$ be the first negative element of the array, and $a_j$ be the last negative of the array.Let $B = a_1 \ * \ ... \ * \ a_i$, $C = a_j \ * \ ... \ * \ a_n$The answer will be $a1 \ * \ ... \ * \ a_{j-1} + C$ if $|B| >= |C|$, or $B + a_{i+1} \ * ... \ * \ a_n$, otherwise.However i don't know to compare B and C because of the mod, maybe my ideia is completely wrong.
•  » » » » » 6 weeks ago, # ^ |   0 to compare u can calculate product under a logarithm, so instead of storing the product itself, you store its logarithm.
•  » » » » » » 6 weeks ago, # ^ |   0 i tried logarithm, i got WA (i can't see if its was really a WA instead of other erro).
•  » » » » » » » 6 weeks ago, # ^ |   0 There was a bug in my code. I got AC with my ideia using logarithm after solved the bug.
 » 6 weeks ago, # | ← Rev. 2 →   +20 If I click the original problem link, it says "Not allowed to view the contest".
•  » » 6 weeks ago, # ^ |   0 oops my bad! You have to register so that u can access the problem You can register here now if u like to.
•  » » 6 weeks ago, # ^ |   0 I can read the problem without doing anything.
 » 6 weeks ago, # | ← Rev. 2 →   0 My code for this problem https://ideone.com/bHjauL
•  » » 6 weeks ago, # ^ |   0 Your solution gives 0 points.[submission:105020822]
 » 6 weeks ago, # | ← Rev. 3 →   +1 _Chaitanya1999 what's the solution? I saw you got AC.UPD: I get AC
•  » » 6 weeks ago, # ^ |   0 Can you share your code?
•  » » » 6 weeks ago, # ^ |   0 Thats the link submision: [submission:105025756].If you can't see the submission (i don't know how gym works): Spoiler#include using namespace std; #define pb push_back #define eb emplace_back #define mk make_pair #define fi first #define se second #define mset(a,b) memset(a, b, sizeof(a)) #define dbg(x) cout << "[" << #x << "]: " << x << endl; #define forn(i,n) for(int i=0; i < n;i++) #define each(val, v) for(auto val : v) #define abs(u) (u >= 0 ? u : -u) using ll = long long; using pii = pair; using vi = vector; using vl = vector; const int MAXN = 2e5 + 5; const int INF = 0x3f3f3f3f; const int MOD = 1e9+7; void solve(){ ll n; cin >> n; vl a(n); vector logs(n); ll neg = 0; forn(i,n){ cin >> a[i]; if(a[i] < 0){ neg++; } } if(n== 1){ a[0] = (a[0] + MOD)%MOD; cout << a[0] << endl; return; } if(neg%2 == 0){ ll ans = 1; for(int i = 1; i < n-1 ; i++){ ans = (ans*a[i])%MOD; ans = (ans + MOD)%MOD; } if(n == 1){ ans = (ans*a[0])%MOD; ans = (ans + MOD)%MOD; }else{ if(a[0] == 1){ ans = (ans*a[n-1])%MOD; ans = (ans + MOD)%MOD; ans = (ans + 1)%MOD; }else if(a[n-1] == 1){ ans = (ans*a[0])%MOD; ans = (ans + MOD)%MOD; ans = (ans + 1)%MOD; }else{ ans = (ans*a[0])%MOD; ans = (ans + MOD)%MOD; ans = (ans*a[n-1])%MOD; ans = (ans + MOD)%MOD; } } cout << ans << endl; }else{ vector esq; vector dir; ll last1 = -1; forn(i,n){ esq.pb(a[i]); if(a[i] < 0){ last1 = i; break; } } ll last2 = -1; for(int i = n-1; i >= 0; i--){ dir.pb(a[i]); if(a[i] < 0){ last2 = i; break; } } long double x1 = 0; long double x2 = 0; int n1 = esq.size(); int n2 = dir.size(); esq[n1-1] = -esq[n1-1]; dir[n2 -1] = -dir[n2-1]; sort(esq.begin(), esq.end()); sort(dir.begin(), dir.end()); forn(i,n1){ x1 += log(esq[i]); } forn(i,n2){ x2 += log(dir[i]); } ll ans = 1; if(x1 >= x2){ ll ans1 = 1; forn(i, last2){ ans1 = (ans1*a[i])%MOD; ans1 = (ans1 + MOD)%MOD; } ll ans2 = 1; for(int i = last2; i < n;i++){ ans2 = (ans2*a[i])%MOD; ans2 = (ans2 + MOD)%MOD; } ll ans = (ans1 + ans2)%MOD; ans = (ans + MOD)%MOD; cout << ans << endl; }else{ ll ans1 = 1; forn(i, last1 + 1){ ans1 = (ans1*a[i])%MOD; ans1 = (ans1 + MOD)%MOD; } ll ans2 = 1; for(int i = last1 + 1; i < n;i++){ ans2 = (ans2*a[i])%MOD; ans2 = (ans2 + MOD)%MOD; } ll ans = (ans1 + ans2)%MOD; ans = (ans + MOD)%MOD; cout << ans << endl; } } } int main(){ ios::sync_with_stdio(false); cin.tie(NULL); solve(); return 0; } 
•  » » » » 6 weeks ago, # ^ |   0 Thanks. I didn't handle the case where an array of size 1 with a negative number well. If anyone somehow wants the code Code#include #include const int N = (int) 1e5, M = (int) 1e9 + 7; int arr[N]; int main() { std::ios_base::sync_with_stdio(0); std::cin.tie(0); int n, pref, suff, neg = 0; pref = suff = 1; std::cin >> n; for(int i = 0; i < n; i++) { std::cin >> arr[i]; neg ^= (arr[i] < 0); pref = 1ll * pref * arr[i] % M; } if(n == 1 || !neg) { if(n > 1 && (arr[0] == 1 || arr[n - 1] == 1)) ++pref; std::cout << (pref + M) % M << '\n'; } else { long double B = 0.0L, C = 0.0L; pref = 1; int l, r; for(l = 0; ;l++) { B += logl(std::abs(arr[l])); if(arr[l] < 0) break; } for(r = n - 1; ;r--) { C += logl(std::abs(arr[r])); if(arr[r] < 0) break; } if(B >= C) { for(int i = 0; i < r; i++) pref = 1ll * pref * arr[i] % M; for(int i = n - 1; i >= r; i--) suff = 1ll * suff * arr[i] % M; } else { for(int i = 0; i <= l; i++) pref = 1ll * pref * arr[i] % M; for(int i = n - 1; i > l; i--) suff = 1ll * suff * arr[i] % M; } std::cout << ((pref + suff) % M + M) % M << '\n'; } }