Reminder: in case of any technical issues, you can use the lightweight website m1.codeforces.com, m2.codeforces.com, m3.codeforces.com. ×

Akin's blog

By Akin, 5 years ago, , I see it sometimes in editorial of CF round and in problems tag ?

But don't know what it is ? I searched and found something like that

Given two arrays (A and B) sorted in ascending order, and an integer x. we need to find i and j, such that a[i] + b[j] is equal to X.

But how to implement it and when it can be implemented for better result ?

Thanks in Advanced :)  Comments (9)
 » Two pointers means that in order to solve the problem, there is an invariant involving two indices. So for your problem above.x = a[i]+b[j]. Since both arrays are sorted, we can use to pointers by using the first pointer to "watch" the first array a, and using the second pointer to navigate b.observe that if b[j] < x-a[i] it means we should move forward on the second array.if b[j] > x-a[i] then for all g > j we can't get the answer so i+=1;Notice how both indices are moving in accord, they depend on each other.Hope this helps.
•  » » 5 years ago, # ^ | ← Rev. 2 →   It is generally a useful technique for resolving a variety of problems. I like your explanation arthurugochukwu . Thanks.
•  » » So your solution is wrong? The following comments prove it.
 » the code, that solves this problem, looks like this: //n - the length of the array A, m - the length of the array B int j=m-1; for (int i=0; i0) && (A[i]+B[j]>x)) { j--; } if (A[i]+B[j]==x) { cout<i1. The following assumption is correct: if (A[i1]+B[j1] == x) and (A[i2]+B[j2] == x) then j2<=j1.So in our code for each i we find the first index j, such as A[i]+B[j]<=x. If (A[i]+B[j]==x), then we find our pair. Otherwise, we continue looking. The total complexity is O(n+m), because i always increases and j always decreases
 » I prefer using only one loop. I think its more beautiful. for(int i = 0, j = m - 1; i < n && j >= 0;) { if(a[i] + b[j] > x) { j--; } else if(a[i] + b[j] < x) { i++; } else { printf("%d + %d = %d\n", a[i], b[j], x); i++; j--; } } The idea is as same as the other people's.
 » Two years later, I am looking for some stuffs on two pointer to send to a friends and I see my name on a comment :)
•  » » Two years and you're still pupil. Nice progress :)
•  » » » •  » » » I don't code on codeforces dumb-ass. I use codechef, you can go check my profile