PAIRSUM2 - Editorial (Unofficial)

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

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

:joy: :joy: what a question!

1 Like

He isn’t official… Otherwise they aren’t (ofc).

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

Read from line 305 :slight_smile:

Oh…I think it’s official …so I said

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

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

@ssrivastava990 can you please explain your approach :slight_smile:

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. :slightly_smiling_face:

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 :slight_smile:

Or try and find it in this page.

2 Likes

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

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 :stuck_out_tongue: (due to its screwed up explanation)

4 Likes

Sure. Will do. :slightly_smiling_face:

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)