ZCO15002 - Editorial

editorial
, ,
1

PROBLEM LINK

ZCO15002

DIFFICULTY

Easy

PREREQUISITES

Simple Logic

PROBLEM IN SHORT

The problem statement is simplistic enough.

SOLUTION

The first thing to note is that we have to take the absolute value of the difference of the two
elements. This simply means that the order in which we discover the elements, (a_{i}, a_{j}) satisfying
the condition, (a_{i} - a_{j} >= k) doesn’t matter. Also, the constraints are small enough to allow sorting. So, we just sort the array.

Now that the array is sorted, we can naively check for the left most element a_{1} , how many a_{j}
satisfy the given condition. This can be done in O(n^2). But this is not good enough to pass the
second sub-task.

Taking it a step further - as the elements are sorted - we can see that a sliding window would do
the job in O(n) time.

In this, we’ll iterate over the array maintaining two indices, a and b starting from the leftmost part of the array. The basic aim is to find the first a[j] for a particular i, such that it’s the smallest element, where a[j] - a[i] >= k. This can be done by incrementing i, if a[j] - a[i] >= k, else increment j. For a particular I, the number of matching pairs will be N - j. The sum of matching elements for all i is the answer.

TIME COMPLEXITY

Sorting takes O(n log n), and the sliding window works in O(n) time, so overall complexity is O(n log n) which will pass the constraints.

EDITORIALIST’s SOLUTION

#include <bits/stdc++.h>
using namespace std;

int a[65007], n, k;

int main() {
	scanf("%d %d", &n, &k);
	for (int i = 0; i < n; i++)
		scanf("%d", &a[i]);
	sort(a, a + n);
	long long ans = 0;
	int i = 0, j = 0;
	while (i < n) {
		if (j < i)
			j = i;
		else if (j >= n)
			break;
		if (a[j] - a[i] >= k) {
			i++;
			ans += n - j;
		}
		else
			j++;
	}
	printf("%lld", ans);
	return 0;
}
1 Like