PAIRSUM2 Help needed

general
1

Help needed to know why I am getting WA in subtask 1

https://www.codechef.com/viewsolution/26826304

2

I think it should be for j in range(c+1,d-1,2)

1 Like
3

The j loop should run for every alternate value, i.e, a jump of 2.
Basically you had to do alternate operations of plus(+) and minus(-).
From c to d-1 starting with addition(+).
Hope this helps!

4

t=int(input())
for _ in range(t):

n,q = map(int,input().split())

a=list(map(int,input().split()))

for p in range(q):
    
    c,d=map(int,input().split())
    
    if(c>d):
        c,d=d,c
    
    if((d-c)%2!=1):
        print("UNKNOWN")
    else:
        sn=0
        for i in range(c,d):
            sn+=a[i-1]
            
        for j in range(c+1,d-1, 2):
            sn-=2*a[j-1]
            #print(sn,a[j-1])
            
        print(sn)
1 Like
5

why j should have jump of 2 ?

6

@archisman_dey @ajaymalik @s_anand98
why j should have a jump of 2?

7

Basically, it should be alternative plus , minus.
As you initially add all the values,
you should only subtract the alternative values by double its value.

1 Like
8

I have passed the subtask1 but getting TLE in subtask2.
LINK of my solution: CodeChef: Practical coding for everyone
Plz help me for AC. thanks :slight_smile:

9

Because you have to subtract every alternate value. What you did before was to substract every value.

10 
#define crap ios_base::sync_with_stdio(0);cin.tie(0)
#define ll long long
#define pb push_back
#define ff first
#define ss second
using namespace std;
  
int main()
{ 
  #ifndef ONLINE_JUDGE
  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);
  #endif
  crap;
  int t; cin>>t;
  while(t--)
  {
    int n,q; cin>>n>>q;
    ll B[n];
    ll A[n];
    B[0]=0;
    A[0]=0;
    for(int i=1;i<=n-1;i++) {cin>>B[i]; A[i]=B[i];}
    for(int i=2;i<=n-1;i++)  B[i]+=B[i-1];
    for(int i=3;i<=n-1;i++) A[i]+=A[i-2];
    while(q--)
    {
      int a,b; cin>>a>>b;
      if(a>b) swap(a,b);
      ll ans=0;
      if((b-a)%2!=1)
        cout<<"UNKNOWN"<<endl;
      else{
        ans+= B[b-1]-B[a-1];
          ans-= 2*(A[b-2]-A[a-1]);
          cout<<ans<<endl;
      }
      
      
    }

  }
}```
optimization using prefix sum
11

Have a look at my solution.
Used prefix array sum approach.
https://www.codechef.com/viewsolution/26820612

12

see the sum of pair only exists if

Ai ,Aj pair have fabs(j-i)%2==1 or fabs(i-j) is odd only…

Therefore this was tricky part of the proble rest by above explanations you can getwhat else is required and the answer finally is
Ai+Aj=Bi+Bj-(Bi+1 - Bi+2 +Bi+3 -Bi+4 …Bj-1)
alternatively…

So final solution link is
solution based on prefix sum approach

13 
#include <iostream>
using namespace std;
int main() {
	int t, *p;
	cin >> t;
	while(t--){
		int n, q;
		cin >> n >> q;
		p = new int[n - 1];
		for (int i = 0;i < (n - 1);i++)
			cin >> p[i];
		while (q--) {
			int a, b;
			cin >> a >> b;
			int k;
			k = a - b;
			k = abs(a - b);
			if (k ==1 ) {
				int m;
				a < b ? m = a : m = b;
				cout << p[m-1] << endl;
			}
			else if (k % 2 == 0) {
				cout << "UNKNOWN" << endl;
			}
			else {
				int res=0;
				int* e = NULL ;
				a < b ? e = &p[a-1] : e = &p[b-1];
				for (int h = 1;h < k;h++)
					e++;
				for (int s = 0;s < k;s++) {
					if (s % 2 == 1) {
						res = res - (*e);
					}
					if (s % 2 == 0) {
						res = res + (*e);
					}
					e--;
				}
				cout << res << endl;
			}
		}
	}
}

Can anyone please give the case for which i get WA?