PROBLEM LINK:
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