Problem: There exists an Array A with at least 2 elements and at most 100000 elements. We don’t know the elements of this array. We are given another Array B. This array has the following property.
B[0] = A[0] + A[1]
B[1] = A[1] + A[2]
B[k] = A[k] + A[k+1]
B[n-1] = A[n-1] + A[n]
Let me explain this with an example:
Array A[5] = [1, 2, 3, 4, 5]
Array B[4] = [3, 5, 7, 9]
But we are only given the array B.
So lets do some math.
Let us say that A[0] = X
That means A[1] = B[0] - X = c1 - X
Further, A[2] = B[1]-A[1] = B[1] - B[0] + x = (B[1] - B[0]) + X = c2 + X
Further A[3] = B[2] - c2 - X = c3 - X
Generalising
The array A can be written as [0+X, c1-X, c2+x, c3 -X, c4+x…]
If we are to add A[11] and A[6]. We will get C6 + X + C11 - X. This leads to C6+C11
But if we are to add A[12] and A[4]. We will get C4+X+C12+X. This leads to C4+C12+2X. We dont know X so we cannot find A[12]+A[4].
How can we represent Array A.
Let us use a two dimensional Array DP[n][2].
Such that DP[k][0] represents sign of x
and DP[k][1] represents Ck
Now that we have resolved A reasonably, we are ready to solve queries:
A query has two inputs p and q. We have to calculate A[p]+A[q]
How do we resolve this query?
If DP[p][0] and DP[q][0] have the same sign (1,1) or (-1,-1). Then we cannot calculate A[p]+A[q]
If they have opposite signs (1,-1) or (-1,1). Then X will cancel out. The final answer is DP[p][1]+DP[q][1].
Here is my implementation: CodeChef: Practical coding for everyone