Contest Duration: - (local time) (100 minutes) Back to Home
Official

## C - Gap Existence Editorial by en_translator

For a fixed $$j$$, the value $$A_i$$ such that $$A_i-A_j=X$$ is unique, so it is sufficient to determine if $$A$$ has such a value. Naively scanning the array costs at worst an $$\Omega(N)$$ time each, for a total of $$\Omega (N^2)$$ time, exceeding the execution time limit. Same applies if you use find for a vector in C++, in for a list in Python, and contains for a list in Java. Beware of the complexities of the standard libraries, too.
If you maintain $$A$$ in a set, it costs an $$O(\log N)$$ time each, for a total of $$O(N\log N)$$ time, fitting in the time limit.

Sample code (C++)

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

int main(){
int n,x;
cin >> n >> x;

set<int>s;
for(int i=0;i<n;i++){
int t;
cin >> t;
s.insert(t);
}

for(auto a:s){
if(s.find(a+x)!=s.end()){
cout << "Yes" << endl;
return 0;
}
}
cout << "No" << endl;
}


You can also use the sliding window trick to solve it in a linear time except for sorting.
We sort $$A$$ in ascending order, as it does not affect the answer. When searching for $$i$$ for a fixed $$j$$, if you iterate $$j$$ in ascending order, the corresponding $$i$$ also increases monotonically, so you can scan all $$j$$ in a linear time.

Sample code (C++)

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

int main(){
int n,x;
cin >> n >> x;
vector<int>a(n);
for(int i=0;i<n;i++)cin >> a[i];
sort(a.begin(),a.end());

int i=0;
for(int j=0;j<n;j++){
while(i<n&&a[i]-a[j]<x)i++;
if(i<n&&a[i]-a[j]==x){
cout << "Yes" << endl;
return 0;
}
}
cout << "No" << endl;
}


posted:
last update: