PROBLEM LINK:
Practice
Contest[Division 1]
Contest[Division 2]
Author: Hasan
Editorialist: Darshan Sen
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 value of 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 value of 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 value of 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;
}