PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4
Practice
Setter: Shivansh Agarwal
Testers: Nishank Suresh and Abhinav sharma
Editorialist: Shivansh Agarwal
DIFFICULTY
2891
PREREQUISITES
Number Theory (Properties of GCD), Two-pointers, Segment Tree
PROBLEM
Choose a subarray S of array A such that if we divide this subarray into 2 non-empty subsequences having GCDs GCD_1, GCD_2 respectively, then:
MXDV(S) = max(GCD_1 - GCD_2) \geq K for atleast one pair of subsequences.
Find the smallest possible length of subarray S.
QUICK EXPLANATION
-
GCD_1 - GCD_2 will have a maximum value when the length of first subsequence is 1 and the second subsequence contains the rest of the elements of the parent sequence.
-
The element in the first subsequence can either be the maximum or the second maximum element of the subsequence.
-
We can use two-pointers and maintain a set with pairs of {element, index} for finding the max and second max of the current subarray along with a Segment Tree for range GCD queries.
EXPLANATION
Observation 1
GCD_1 - GCD_2 will have a maximum value when the length of first subsequence is 1 and the second subsequence contains the rest of the elements of the parent sequence.
Proof
GCD of a sequence either decreases or remains same on adding additional elements to the sequence. Hence, you will always try to decrease the length of the first subsequence and increase the length of the second subsequence.
Observation 2
The optimal choice for the first subsequence would always be one of the largest 2 distinct elements of the array.
Proof
Let all the distinct elements in an array A in sorted order be:-
A_1 < A_2 < \ldots < A_{N-1} < A_N. (Here, A_{N-1} is not necessarily the second last element of the array, these are just distinct elements in sorted order)
Now if we take the largest element of this sequence as the first subsequence then,
GCD_1 - GCD_2 = A_N - gcd(A_1, A_2, \ldots A_{N-1})
and we also know that:
A_{N-1} - A_{N-2} \geq gcd(A_{N-1}, A_{N-2}), as A_{N-1} - A_{N-2} > 0 and GCD divides both elements A_{N-1}, A_{N-2}.
\Rightarrow A_{N-1} - A_{N-2} \geq gcd(A_1, A_2, \ldots , A_{N-2}, A_{N-1}), as GCD of a sequence decreases or remains same on increasing length of the sequence.
\Rightarrow A_N - A_{N-2} \geq gcd(A_1, A_2, \ldots , A_{N-2}, A_{N-1}) as A_N > A_{N-1}.
\Rightarrow A_N - gcd(A_1, A_2, \ldots , A_{N-2}, A_{N-1}) \geq A_{N-2}
\Rightarrow A_N - gcd(A_1, A_2, \ldots , A_{N-2}, A_{N-1}) > A_{N-2} - gcd(A_1, \ldots,A_{N-3}, A_ {N-1}, A_N), as we can always say gcd(A_1, \ldots,A_{N-3}, A_ {N-1}, A_N) \geq 1
Hence, it will always be better to choose [A_N] as our first subsequence instead of [A_{N-2}]. In the same way it can be proved for all the other elements less than or equal to A_{N-2}. So our optimal choice would always be to choose one of the largest 2 distinct elements of the array.
Note: Increasing frequency of elements does not affect their GCD. All the occurrences of the largest and the second largest element will give the same answer so we need to consider them only once and no element smaller than or equal to A_{N-2} is suitable as already mentioned.
Extra Observation
If the largest element occurs more than once, the first subsequence can only contain the largest element for the most optimal answer.
Proof
Let’s say our sequence is:- A_1 \leq A_2 \leq \ldots \leq A_X < A_{X+1} = A_{X+2} = \ldots = A_N
If we take A_N in the first subsequence, the GCD of the second subsequence will be G_i = gcd(A_1, A_2, \ldots , A_{N-1}).
First, we remove A_X from the second subsequence. The GCD of the second subsequence can either increase or remain the same.
Now, we will add A_N to the second subsequence. The gcd will remain the same as A_{N-1} = A_N is already present in the second subsequence. Let’s call the gcd of the second subsequence now as G_f.
Then, we can surely say G_i \leq G_f and we already know A_X < A_N. So, A_N - G_i > A_X - G_f. Hence, in this case we only need to consider the largest element of the subarray.
Corner Case
If all elements of the array are equal, then if K = 0, the answer is 2 and -1 otherwise. This solution covers this case automatically but some solutions might find this as a corner case.
Reduced problem
So, the problem is reduced to finding the smallest subarray such that A_X - GCD( rest of elements of the subarray ) \geq K where, A_X is either the largest or the second largest distinct element.
Now, we will use two pointers to find the smallest subarray satisfying above conditions.
Our goal is to calculate the value of MXDV(S) for the current subarray [l, r] where, l and r are the current indices of our two-pointers. For calculating GCD_1 - GCD_2, we simply calculate the value:
A_X (largest or second largest element) - GCD of the rest of the elements in the subarray.
If we know the index of A_X then this value can be calculated using a GCD Segment tree.
Now, for finding the indices of the largest and the second largest element (A_X) in the subarray, we can map the elements of the subarray with a queue containing indices of all the occurrences of the elements in the subarray. We can then pop and push indices in this map as we move our left and right pointers respectively.
If we use the Extra Observation mentioned, then this can be implemented using std::set which stores the elements as pairs of {elements, index}.
Note: You can even use binary-search instead of two-pointers. It still passes all the test cases.
TIME COMPLEXITY
The time complexity is O(N\cdot \log (N)\cdot \log (A_i)).
SOLUTIONS
Setter's Solution
// author: Shivansh Agarwal
#include <bits/stdc++.h>
using namespace std;
#define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
vector<int> st; // Segment Tree
int n;
// 0-based indexing
void MakeST()
{
for (int i = n - 1; i >= 1; i--)
st[i] = __gcd(st[i << 1], st[i << 1 | 1]);
}
int query(int l, int r) // range [l, r)
{
int res = 0;
for (l += n, r += n; l < r; l >>= 1, r >>= 1)
{
if (l & 1)
res = __gcd(res, st[l++]);
if (r & 1)
res = __gcd(res, st[--r]);
}
return res;
}
int32_t main()
{
fastio;
int tt;
cin >> tt;
while (tt--)
{
int x;
cin >> n >> x;
vector<int> v(n);
// Segment Tree for calculating range GCD
st.resize(2 * n);
for (int i = 0; i < n; i++)
cin >> v[i], st[i + n] = v[i];
// building the Segment Tree
MakeST();
// Set for finding the max and second max element of the current subarray
set<pair<int, int>, greater<pair<int, int>>> curr_max;
//Initialising pointers [l, r] for Two-pointers
int l = 0, r = 1, ans = n + 1;
curr_max.insert({v[0], 0});
curr_max.insert({v[1], 1});
// Two Pointers Algorithm
while (r < n && r != l)
{
auto it = curr_max.begin();
// Checking for the largest element
int rest_gcd = __gcd(query(l, (*it).second), query((*it).second + 1, r + 1));
//Here, rest_gcd stores the gcd of rest of elements of the current subarray
if ((*it).first - rest_gcd >= x)
{// If condition is satisfied we will update our set and increment left pointer
curr_max.erase({v[l], l});
ans = min(ans, r - l + 1), l++;
continue;
}
//Checking for the second largest element
it++;
rest_gcd = __gcd(query(l, (*it).second), query((*it).second + 1, r + 1));
if ((*it).first - rest_gcd >= x)
{
curr_max.erase({v[l], l});
ans = min(ans, r - l + 1), l++;
continue;
}
// If this subarray does not satisfy the condition then we update our set and increment right pointer
r++;
if (r < n)
curr_max.insert({v[r], r});
}
// If the value of ans is still n + 1 that means, no subarray satisfied the conditions
if (ans == n + 1)
cout << "-1\n";
else
cout << ans << "\n";
}
}
Tester's Solution 1
#include <bits/stdc++.h>
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
using ll = long long int;
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
/**
* Sparse Table
* Source: kactl
* Description: Given an idempotent function f and a static array V,
* finds f(V[L], V[L+1], ..., v[R-1]) in O(1) using O(nlogn) memory
* Time: O(nlogn) precomputation, O(1) query
* Note: Ranges are half-open, i.e, [L, R)
*/
template<class T>
struct RMQ {
T f(T a, T b) {return gcd(a, b);}
vector<vector<T>> jmp;
RMQ(const vector<T>& V) : jmp(1, V) {
for (int pw = 1, k = 1; pw * 2 <= (int)V.size(); pw *= 2, ++k) {
jmp.emplace_back(V.size() - pw * 2 + 1);
for (int j = 0; j < (int)jmp[k].size(); ++j)
jmp[k][j] = f(jmp[k - 1][j], jmp[k - 1][j + pw]);
}
}
T query(int a, int b) {
if (a >= b) return 0;
// assert(a < b); // or return unit if a == b
int dep = 31 - __builtin_clz(b - a);
return f(jmp[dep][a], jmp[dep][b - (1 << dep)]);
}
};
int main()
{
ios::sync_with_stdio(false); cin.tie(0);
int t; cin >> t;
while (t--) {
int n, k; cin >> n >> k;
vector<int> v(n);
for (int &x : v) cin >> x;
RMQ RMQ(v);
auto get = [&] (int L, int x, int R) {
return gcd(RMQ.query(L, x), RMQ.query(x+1, R));
};
auto calc = [&] (int len) {
int mx = 0;
set<tuple<int, int>> active;
for (int i = 0; i+1 < len; ++i) active.insert({v[i], i});
for (int i = len-1; i < n; ++i) {
active.insert({v[i], i});
if (i-len >= 0) active.erase({v[i-len], i-len});
auto [val, pos] = *active.rbegin();
mx = max(mx, val - get(i-len+1, pos, i+1));
tie(val, pos) = *next(active.rbegin());
mx = max(mx, val - get(i-len+1, pos, i+1));
}
return mx;
};
if (calc(n) < k) {
cout << -1 << '\n';
continue;
}
int lo = 2, hi = n;
while (lo < hi) {
int mid = (lo + hi)/2;
if (calc(mid) >= k) hi = mid;
else lo = mid+1;
}
cout << lo << '\n';
}
}
Tester's Solution 2
#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll max(ll l, ll r){ if(l > r) return l ; return r;}
ll min(ll l, ll r){ if(l < r) return l ; return r;}
/*
------------------------Input Checker----------------------------------
*/
long long readInt(long long l,long long r,char endd){
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true){
char g=getchar();
if(g=='-'){
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g && g<='9'){
x*=10;
x+=g-'0';
if(cnt==0){
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);
assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd){
if(is_neg){
x= -x;
}
if(!(l <= x && x <= r))
{
cerr << l << ' ' << r << ' ' << x << '\n';
assert(1 == 0);
}
return x;
} else {
assert(false);
}
}
}
string readString(int l,int r,char endd){
string ret="";
int cnt=0;
while(true){
char g=getchar();
assert(g!=-1);
if(g==endd){
break;
}
cnt++;
ret+=g;
}
assert(l<=cnt && cnt<=r);
return ret;
}
long long readIntSp(long long l,long long r){
return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
return readString(l,r,'\n');
}
string readStringSp(int l,int r){
return readString(l,r,' ');
}
/*
------------------------Main code starts here----------------------------------
*/
const int MAX_T = 1;
const int MAX_N = 100;
const int SUM_N = 300000;
const int MAX_VAL = 100;
const int SUM_VAL = 20005 ;
const int OFFSET = 10000 ;
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define ff first
#define ss second
#define mp make_pair
#define ll long long
#define rep(i,n) for(int i=0;i<n;i++)
#define rev(i,n) for(int i=n;i>=0;i--)
#define rep_a(i,a,n) for(int i=a;i<n;i++)
#define pb push_back
ll sum_n = 0, sum_m = 0;
int max_n = 0, max_m = 0;
int yess = 0;
int nos = 0;
int total_ops = 0;
ll mod = 998244353;
using ii = pair<ll,ll>;
struct ST{
vector<vector<int> > bt;
int n;
ST(int _n){
n = _n;
bt.assign(_n, vector<int>(21,0));
}
void build(vector<int> v){
rep(i,n) bt[i][0]=v[i];
rep_a(i,1,21){
for(int j=0; j+(1<<i)<=n; j++) bt[j][i] = __gcd(bt[j][i-1], bt[j+(1<<(i-1))][i-1]);
}
}
int qr(int l, int r){
int res = 0;
rev(i,20){
if(l>r) break;
if(l+(1<<i)-1<=r){
res = __gcd(res, bt[l][i]);
l+=(1<<i);
}
}
return res;
}
};
void solve()
{
int n = readIntSp(2,1e5);
int k = readIntLn(0,1e6);
vector<int> a(n);
rep(i,n){
if(i<n-1) a[i] = readIntSp(1,1e6);
else a[i] = readIntLn(1,1e6);
}
if(k==0){
cout<<2<<'\n';
return;
}
struct ST s(n);
s.build(a);
int l = 2, r = n;
while(l<=r){
int mid = (l+r)>>1;
int f = 0;
map<int,int> ms;
rep(i,mid-1){
ms[a[i]]=i;
}
rep_a(i,mid-1,n){
ms[a[i]]=i;
if(ms.size()>1){
auto it = ms.end();
--it;
int p = it->ss;
int tmp = __gcd(s.qr(i-mid+1, p-1), s.qr(p+1,i));
if(it->ff-tmp>=k){
f=1;
break;
}
--it;
p = it->ss;
tmp = __gcd(s.qr(i-mid+1, p-1), s.qr(p+1,i));
if(it->ff-tmp>=k){
f=1;
break;
}
}
if(ms[a[i-mid+1]]==i-mid+1) ms.erase(a[i-mid+1]);
}
if(f){
r=mid;
if(l==r) break;
}
else l=mid+1;
}
if(l==n+1) cout<<-1<<'\n';
else cout<<r<<'\n';
}
signed main()
{
fast;
#ifndef ONLINE_JUDGE
freopen("input.txt" , "r" , stdin) ;
freopen("output.txt" , "w" , stdout) ;
#endif
int t = 1;
t = readIntLn(1,1000);
for(int i=1;i<=t;i++)
{
solve() ;
}
assert(getchar() == -1);
assert(sum_n<=1e5);
cerr<<"SUCCESS\n";
cerr<<"Tests : " << t << '\n';
// cerr<<"Sum of lengths : " << sum_n << '\n';
// cerr<<"Maximum length : " << max_n << '\n';
// cerr<<"Minimum length : " << min_n << '\n';
// cerr << "Sum o f product : " << sum_nk << '\n' ;
// cerr<<"Total operations : " << total_ops << '\n';
// cerr<<"Answered yes : " << yess << '\n';
// cerr<<"Answered no : " << nos << '\n';
}
Feel free to share your approach. Suggestions are welcomed. 