# POSITNEG - Editorial

Author: rajat397
Tester & Editorialist: iceknight1093

1526

None

# PROBLEM:

You’re given an array B of length N consisting of 1's and -1's.
Consider a new array C, such that C_i = 2^{i-1}\cdot B_i for each 1\leq i \leq N.

Suppose P subarrays of C have a strictly positive sum and Q of them have a strictly negative sum.
Find |P - Q|.

# EXPLANATION:

Consider a subarray [L, R]. A little observation should tell you that:

• If B_R = 1, then C_L + C_{L+1} + \ldots + C_R \gt 0
• If B_R = -1, then C_L + C_{L+1} + \ldots + C_R \lt 0
Proof

Suppose B_R = 1, so C_R = 2^{R-1}

Recall that the powers of two satisfy 2^0 + 2^1 + \ldots + 2^{R-2} \lt 2^{R-1}, which (by removing a few terms) also means 2^{L-1} + \ldots + 2^{R-2} \lt 2^{R-1}.
This can be rearranged to 2^{R-1} - 2^{R-2} - 2^{R-3} - \ldots - 2^{L-1} \gt 0, and the LHS of this equation is the minimum possible sum of C_L + C_{L+1} + \ldots + C_R (attained when B_L = B_{L+1} = \ldots = B_{R-1} = -1)

The minimum possible sum is positive, so clearly any sum is also going to be positive.

A similar proof holds for the B_R = -1 case.

This makes the problem quite simple:

• If B_i = 1, then all the subarrays ending at i have positive sum. There are exactly i such subarrays (in 1-indexing).
• Similarly, if B_i = -1, then all i subarrays ending at this index have a negative sum.

This allows us to compute P and Q both in \mathcal{O}(N) time (if B_i = 1, add i to P; otherwise add i to Q), after which |P - Q| is easily found.

You may also note that, if we let d = P - Q, then each index i adds exactly B_i \cdot i to d.
So, a simple way to write down the answer is \displaystyle\left|\sum_{i=1}^N i\cdot B_i\right|.

# TIME COMPLEXITY

\mathcal{O}(N) per test case.

# CODE:

Editorialist's code (Python)
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
ans = 0
for i in range(n):
ans += a[i] * (i+1)
print(abs(ans))


Can Anyone tell on which test case my code fails…
#include <bits/stdc++.h>
using namespace std;

int main() {
int t;
cin>>t;
while(t–){
int n;
cin>>n;
int sum=0;
int total=n*(n+1)/2;
for(int i=0;i<n;i++){
int a;
cin>>a;
if(a==-1) sum+=(i+1);
}
cout<<abs((total-sum)-sum)<<endl;;
}
return 0;
}

Your code uses int to hold its sums and answer, but for large inputs, |P-Q| can exceed the maximum value, 2^{31}-1, representable in an int. So, it will fail on an input like  1 100000 1 1 … 1 where, in the third line, there are 10^5 1s.

What if I use long long int instead of int?
Would there be any overflow issue for storing n*(n+1)/2??
I used long long int for the exact same code but still got WA for test case 2 & 3.

------MY CODE------

#include<bits/stdc++.h>
using namespace std;
#define int long long int

int32_t main()
{

int t;
cin >> t;

while (t--)
{
int n;
cin >> n;
int a[n], b[n];
int base = 1;

for (int i = 0; i < n; i++)
{
a[i] = base;
base = base<<1;
}

for (int i = 0; i < n; i++)
{
int temp;
cin >> temp;
b[i] = temp;
}

int c[n];
for (int i = 0; i < n; i++)
{
c[i] = a[i]*b[i];
}

int q = 0;
for (int i = 0; i < n; i++)
{
if(c[i]<0) {
q+=(i+1);
}
}

int ans = (n*(n+1))/2 - 2*q;

if(ans>=0) {
cout << ans << endl;
}
else {
cout << -ans << endl;
}
}
return 0;


}

a[i] = base;
base = base<<1;


Looks like you’re attempting to actually create the A array with powers of 2.
That won’t work because N is way too large.
For example if N = 10^5 then the largest number you’ll create is 2^{99999}, while the limit for long long is about 2^{63} which is several orders of magnitude smaller.

Your code is on the right track though: notice that C_i \lt 0 is possible if and only if B_i \lt 0.
So if (c[i] < 0) in your code can be replaced by if (b[i] < 0) and then it’ll work fine (with the added bonus of there being no need to create the a or c arrays).

1 Like

Why am i getting wa?

#include <iostream>
#include <bits/stdc++.h>

using namespace std;

#define ll          long long
#define vi          vector<int>
#define vll         vector<ll>
#define pll         pair<ll, ll>
#define pii         pair<int, int>
#define ld          long double
#define ff          first
#define ss          second
#define vs          vector<string>
#define vpll        vector<pll>
#define vb          vector<bool>
#define mp          make_pair
#define pb          push_back
#define endl        '\n'
#define takeinput(arr,n)    for(int i = 0;i<n;i++)cin>>arr[i];
#define print(arr)  for(int i =0;i<arr.size();i++){cout<<arr[i]<<" ";cout<<endl;}

void solve()
{
int n;
long long  q = 0;
cin>>n;
vector<int>b(n);
takeinput(b,n);
for(int i = 0;i<n;i++)
{
if(b[i]==-1)q = q+i+1;
}
long long  ans = (n*(n+1))/2;

cout<<llabs(ans-2*q)<<endl;

}
int main() {
int t;
cin>>t;
while(t--)
{
solve();
}

}