# PROBLEM LINK:

Practice

Contest[Division 1]

Contest[Division 2]

* Author:* Hasan

*Darshan Sen*

**Editorialist:**# DIFFICULTY:

EASY

# PREREQUISITES:

Basic Math

# PROBLEM:

Given a sequence B_1,B_2,...,B_N\__1, s.t. a set of sequences of the form A_1,A_2,...,A_N can be generated according to the relation:

B_i=A_i+A_i _+ _1 , \forall i \in [1, N)

*uniquely determine* A_p + A_q for the queried pairs p and q if possible.

# QUICK EXPLANATION:

The sum can be *uniquely determined* iff |p - q| is an odd number and the result can be computed by generating a possible sequence A in a deterministic way by keeping any one of its elements fixed.

# EXPLANATION:

Letâ€™s find the relation between some A_i with a few other preceding elements:

A_i = B_i\__1 - A_i\__1

\implies A_i + A_i\__1 = B_i\__1

. . . [unique valueof A_i + A_i\__1 found ]

\implies A_i = B_i\__1 - A_i\__1

\implies A_i = B_i\__1 - B_i\__2 + A_i\__2

. . . [uniquely valueof A_i + A_i\__2 not found ]

\implies A_i = B_i\__1 - B_i\__2 + B_i\__3 - A_i\__3

\implies A_i + A_i\__3 = B_i\__1 - B_i\__2 + B_i\__3

. . . [unique valueof A_i + A_i\__3 found ]

. . .

We see that, to *uniquely determine* the sum A_i + A_i\__r, the term A_i\__r must be preceded by a - ve sign when it is to the right hand side of the above equations. Noticing the pattern, we can say that it is possible only when r is odd.

Now, we can fix any element of A and generate a possible sequence and determine the sum A_p + A_q by simply adding the elements at the p^{th} and q^{th} indices.

# SOLUTIONS:

## Editorialist's Solution

```
#include <iostream>
#define MAXN 1'00'005
int32_t N;
int64_t B[MAXN];
int64_t A[MAXN];
void generate_possible_sequence (void ) {
/* We can generate a possible sequence for A
by fixing the 0-th(any) element by 0(any) */
A[0] = 0;
for (int i = 1; i < N; ++i)
A[i] = B[i - 1] - A[i - 1];
}
int main (void ) {
signed T;
std::cin >> T;
while (T--) {
int32_t Q;
std::cin >> N >> Q;
int32_t N_minus_1 = N - 1;
for (int32_t i = 0; i < N_minus_1; ++i)
std::cin >> B[i];
generate_possible_sequence();
while (Q--) {
int32_t p, q;
std::cin >> p >> q;
// adjustment for 0-based array indexing
--p;
--q;
/* A_p + A_q can only be uniquely determined
iff the distance between p and q is an odd number */
int32_t distance = abs(p - q);
if (1 & distance) {
// possible
std::cout << (A[p] + A[q]);
} else {
// impossible
std::cout << "UNKNOWN";
}
std::cout << std::endl;
}
}
return 0;
}
```