FINALSUM - Editorial

PROBLEM LINK:

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

Author: Tejas Pandey
Testers: Nishank Suresh, Takuki Kurokawa
Editorialist: Nishank Suresh

DIFFICULTY:

1145

PREREQUISITES:

Observation

PROBLEM:

You have an array A containing N integers. You are also given Q updates, of the following form:

  • L \ \ R: add 1 to A_L, -1 to A_{L+1}, 1 to A_{L+2}, and so on

Find the sum of A after all Q updates.

EXPLANATION:

Directly performing an update takes \mathcal{O}(N) time, so performing every update would be \mathcal{O}(NQ), which is too slow.

Instead, let’s make a couple of observations about the process.
Let S denote the sum of A. How does S change after an update?

  • If the length of the segment we update is even, then S changes by 1 + (-1) + 1 + (-1) + \ldots + 1 + (-1) = 0
  • If the segment has odd length, S changes by 1 + (-1) + \ldots + 1 + (-1) + 1 = 1

This gives us a rather simple solution that runs in \mathcal{O}(N+Q):

  • Compute S, the initial sum of array A.
  • Then, for each update:
    • If the length of the segment [L, R] is even, S doesn’t change.
    • Otherwise, S increases by 1.
  • Finally, print the value of S.

Note that there are ways to actually simulate all the updates fast enough using lazy segment trees or sweeplines, but they are completely unnecessary to solve this task.

TIME COMPLEXITY

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

CODE:

Editorialist's code (Python)
for _ in range(int(input())):
    n, q = map(int, input().split())
    a = list(map(int, input().split()))
    s = sum(a)
    while q > 0:
        l, r = map(int, input().split())
        s += l%2 == r%2
        q -= 1
    print(s)

Can u explain how is this checking if the subarray length is even ?

sorry to bother u guys but can u find the logical error in my code i m not able to code my thinking i guess.
#include <bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin>>t;
while(t–)
{
int n=0,q=0;
cin>>n>>q;
int a[n];
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
while(q–)
{ int l=0,r=0;
cin>>l>>r;
for(int j=l;j<=r;j++)
{
if(j%2==0)
{
a[j]=a[j]-1;
}
else if(j%2!=0)
{
a[j]=a[j]+1;
}
}

   }
   long long int sum=0;
   for(int k=1;k<=n;k++)
   {
       sum=sum+a[k];
   }
   cout<<sum<<endl;
    
}

}

If the sum is even, you don’t have to add or subtract anything

The length of subarray [L, R] is R-L+1. If this number is odd, then R-L must be even, i.e, L and R must have the same parity. So it’s enough to compare the parities of L and R, which is what that line of code does.

Your code seems to be a plain bruteforce, which for each query changes every element from L to R.
While this approach is logically correct, please do read the first line of the editorial: “Directly performing an update takes \mathcal{O}(N) time, so performing every update would be \mathcal{O}(NQ), which is too slow.”

The crux of solving this problem is finding a way to optimize this approach.

1 Like

yeah i got it , i should have applied more deeper thinking , moreover it was also giving WA also in some cases i dont know y though

can anyone explain how we are selecting sub array from given array

If the sum is even there is no need to add anything as there is equal number of positive and negative one.

i did this p.s. even not needed -

#include
#include
#include
#include
using namespace std;
#define ll long long int
const unsigned int mod = 1e9+7;

int main(){

ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//this is fast I/O (inputput output) use header file <cstdio>
int t;cin>>t;
while(t--){
    int n,q; cin>>n>>q;
    ll a[n+1];
    ll sum = 0;
    for(int i=1; i<=n; i++) {
        cin>>a[i];
        sum+=a[i];
    }
    while(q--){
        int l,r ;cin>>l>>r;
        int count = 0;
        count = (r-l)+1;
        if(l==r) sum+=1;
        else if(count%2==0) sum+=0;
        else if(count%2==1) sum+=1;
    }
    cout<<sum<<endl;
}
return 0;>

}

they aren’t not neede — find the sum of the array and since in the subarray ur add +1 and sub -1 alternatively so if even queries +=0 at the end but if queries (l==r) or are odd then +1 at the end