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 = A + A
B = A + A
B[k] = A[k] + A[k+1]
B[n-1] = A[n-1] + A[n]
Let me explain this with an example:
Array A = [1, 2, 3, 4, 5]
Array B = [3, 5, 7, 9]
But we are only given the array B.
So lets do some math.
Let us say that A = X
That means A = B - X = c1 - X
Further, A = B-A = B - B + x = (B - B) + X = c2 + X
Further A = B - c2 - X = c3 - X
The array A can be written as [0+X, c1-X, c2+x, c3 -X, c4+x…]
If we are to add A and A. We will get C6 + X + C11 - X. This leads to C6+C11
But if we are to add A and A. We will get C4+X+C12+X. This leads to C4+C12+2X. We dont know X so we cannot find A+A.
How can we represent Array A.
Let us use a two dimensional Array DP[n].
Such that DP[k] represents sign of x
and DP[k] 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] and DP[q] 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]+DP[q].
Here is my implementation: https://www.codechef.com/viewsolution/26846147