PAIRSUM2 - Editorial (Unofficial)

editorial
, , ,
1

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
2

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

3

:joy: :joy: what a question!

1 Like
4

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

5

My solution : CodeChef: Practical coding for everyone

Read from line 305 :slight_smile:

6

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

7

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

8

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

@ssrivastava990 can you please explain your approach :slight_smile:

10

do you need to HTML and CSS to write editorials?

11

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

12

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
13

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

1 Like
14

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
15

Sure. Will do. :slightly_smiling_face:

16

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.

17

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
18 
#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:

19

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)