PAIRSUM2 Editorial

PROBLEM LINK:

Practice
Contest

Author: Hasan Jaddouh
Tester & Editorialist: Hussain Kara Fallah

PROBLEM EXPLANATION

There is a sequence A_1,A_2,…,A_N. We do not know the elements of this sequence, but we know another sequence B_1,B_2,…,B_{N−1} such that B_i=A_i+A_{i+1} for each valid i.
You should process Q queries. In each query, you are given two indices a and b ; your task is to compute A_a+A_b or determine that there is not enough information to uniquely determine this sum.

DIFFICULTY:

Easy

PREREQUISITES:

None

Quick Explanation

The answer for each query (a,b) where a \leq b
If (b-a) is even, we can’t obtain an answer. Otherwise:
ans = {\displaystyle \sum_{i = a}^{i =b-1} -1^{(i -a)}*B_i}

EXPLANATION:

It’s pretty intuitive that you are going to calculate the answer of any query (a,b) by adding some elements and subtracting some other of the array B.
It doesn’t matter which elements you are gonna add or subtract, you can notice something interesting about your total sum. The total number of odd positioned numbers included in your sum (odd positioned in the original array A) is always equal to the number of even positioned numbers included in the sum.
This leads us to a fact that when (b-a) is even, we can’t obtain an answer (because a and b have the same parity).
If (b-a) is odd then:
ans = {\displaystyle \sum_{i = a}^{i =b-1} -1^{(i -a)}*B_i}
Notice that each element between the a_{th} and b_{th} ones gets added and subtracted exactly once (hence having no effect) and ending finally with A_a+A_b
To perform this quickly in O(n) we can keep an array with prefix sums of B with only one trick, before calculating sums we multiply all elements with even index by -1. Afterwards, answering queries is straightforward. You can check my implementation.

AUTHOR’S AND TESTER’S SOLUTIONS:

EDITORIALIST’s solution: Can be found here

5 Likes

The total number of odd positioned numbers included in your sum (odd positioned in the original array A) is always equal to the number of even positioned numbers included in the sum.
can you give an example?

Let us take given example
5 3
4 5 6 7
So make any random array which follow this property
Ex. 0 4 1 5 2 or 1 3 2 4 3 ( any array )

Lets take arr = {0,4,1,5,2}
Now for index l and r ( l < r )
we can’t find sum when ( l - r )%2 == 0
Becz at that time we have n variable and n-1 equation.
So print UNKNOWN otherwise
Ans is arr[l-1]+arr[r-1]

Valid indexes are
1 2
1 4
2 3
2 5
3 4

4 Likes

https://www.codechef.com/viewsolution/26900006
can someone help me figure out why my logic does not work?
I’m taking prefix subtractions and for each query i take sum of numbers at two indexes.
Thanks

Have you tried this ?
I used the same approach but getting wrong answer.What is wrong in this code?
https://www.codechef.com/viewsolution/26927651

Hope someone helps us :frowning:

declare arr[0] with some value ,
i mean arr[0] = 0
and your code is not correct , so please check it again.

just change your temp and arr to long long int and you get the answer.
Bye :raising_hand_man:t2:

1 Like

There is definitely a problem in one test case because even the author’s solution is exceeding the time limit.

Use fast io to avoid TLE.