POSITNEG - Editorial

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: rajat397
Tester & Editorialist: iceknight1093

DIFFICULTY:

1526

PREREQUISITES:

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();
    }



	
}