# PAIRSUM2 - Editorial (Unofficial)

Author: Hasan
Editorialist: Darshan Sen

EASY

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;
}

4 Likes

Tell me one thing is it allowed that the editorialist can give the contest

what a question!

1 Like

He isnâ€™t officialâ€¦ Otherwise they arenâ€™t (ofc).

My solution : https://www.codechef.com/viewsolution/26827759

Ohâ€¦I think itâ€™s official â€¦so I said

Sorry, its unofficial. @vijju123 thanks for correcting me.

Can someone please tell me, what is wrong in my code?
#include <bits/stdc++.h>

using namespace std;

int main(){
int t,n,p,q,Q,ans,a,e,h,j;
cin>>t;
while(t--){
cin>>n>>Q;
int b[n];
for(int i=0;i<n-1;i++){
cin>>b[i];
}
for(int i=0;i<Q;i++){
cin>>p>>q;
if((p-q)%2==0)
cout<<"UNKNOWN\n";
else if((p-q)==1)
cout<<b[min(p,q)-1]<<"\n";
else{
p-=1;
q-=1;
ans=0;
a=min(p,q);
e=max(p,q);
//cout<<a<<" "<<e<<"\n";
h=1;
j=e-1;
while(j!=a){
if(h==1){
ans+=b[j];
}
else ans-=b[j];
h=!(h^0);
//cout<<h<<"fejif"<<ans<<"j\n";
j-=1;
}
ans+=b[a];
cout<<ans<<"\n";
}
}
}
return 0;
}

do you need to HTML and CSS to write editorials?

Nope, itâ€™s mostly just markdown and latex and learning by clicking the buttons right on top of the editorial editor.

If the Editorialist has edited their post, you can click on the Edit icon (the little orange pencil), click â€śRawâ€ť and see the â€śraw source codeâ€ť of the Editorial.

For example, if you want to know how to get the neat â€śhorizontal curly braceâ€ť thing, you can click on the Edit icon in this post and find out

2 Likes

Yea, its a nice way to learn. I learned how to add the details section from one of your posts actually.

1 Like

Guys, you all should check out the first qn of Div-2, its harder than first 2 questions of Div-1 according to me (due to its screwed up explanation)

4 Likes

Sure. Will do.

when N is odd we can determine every value of A since sum of elements in B = 2*(A1+â€¦AN-1)+AN; A1+â€¦AN-1=sigma(B2i-1); this way you can compute all As and hence uniquely determine every sum â€¦ your given test case was wrong that way â€¦ please correct me if i am wrong.

Hereâ€™s a little editorial-like solution to the problem.

Solution
	#include <iostream>
#include <unordered_set>

int A[1'000];
int N, M;

bool solve (void ) {

/* An order of feeding cats
is fair iff we feed the cats
in batches, i.e., where each
cat is fed only once. */

/* We can divide the feeding
order, A from the beginning
into equal sized batches of
size N and check whether
every cat is unique in
all such batches. */
for (int i = 0; i < M; i += N) {
/* i iterates over
the beginning indices
of each batch */

// S stores the cat indices as we come across each
std::unordered_set<int> S;

for (int j = 0; j < N and (i + j) < M; ++j) {
if (S.find(A[i + j]) == S.end()) {
/* If element A[i + j] is unique
in this batch, we simply insert it
into the set S and move forward */
S.insert(A[i + j]);
} else {
/* If element A[i + j] is not unique
in this batch, we simply return false */
return false;
}
}
}
/* Now we return true because
the array satisfies the condition */
return true;
}

int main (void ) {

int T;
std::cin >> T;
while (T--) {
std::cin >> N >> M;
for (int i = 0; i < M; ++i)
std::cin >> A[i];
std::cout << (solve() ? "YES" : "NO") << std::endl;
}

return 0;
}

1 Like
#include <iostream>
using namespace std;
int main() {
int t, *p;
cin >> t;
while(t--){
int n, q;
cin >> n >> q;
p = new int[n - 1];
for (int i = 0;i < (n - 1);i++)
cin >> p[i];
while (q--) {
int a, b;
cin >> a >> b;
int k;
k = a - b;
k = abs(a - b);
if (k ==1 ) {
int m;
a < b ? m = a : m = b;
cout << p[m-1] << endl;
}
else if (k % 2 == 0) {
cout << "UNKNOWN" << endl;
}
else {
int res=0;
int* e = NULL ;
a < b ? e = &p[a-1] : e = &p[b-1];
for (int h = 1;h < k;h++)
e++;
for (int s = 0;s < k;s++) {
if (s % 2 == 1) {
res = res - (*e);
}
if (s % 2 == 0) {
res = res + (*e);
}
e--;
}
cout << res << endl;
}
}
}
}


I tried my best to find for which test-case my solution is wrong ? But couldnâ€™t . Can anyone point to the error or just give the cases for which i should check to find the error ?
Thanks:smile:

In the else if you are checking that whether p,q difference is one

I think you are assuming that p>q but in the sample test case we can see that p<q
1 rd query

so we have to use else if(abs(p-q)==1)