PROBLEM LINK:
Author: Ritesh Gupta
Tester: Subhadeep Chandra
Editorialist: Ritesh Gupta
DIFFICULTY:
SIMPLE
PREREQUISITES:
Ad-hoc, Greedy, GCD
PROBLEM:
You are given a sequence A_1, A_2, \ldots, A_N. You have to split the array into a maximum number of non-empty subarrays such that the gcd of elements of each subarray is equal to 1. If there is no split possible then print ā-1ā.
Constraints:
- 1 \le T \le 3
- 1 \le N \le 5 \cdot 10^5
- 1 \le A_i \le 10^6 for each valid i
EXPLANATION:
We can approach this problem greedily. We can perform follow the following steps:
- Initially, the answer is zero.
- Find the smallest length prefix of the current sequence such that gcd of elements is 1.
- Increment the answer by 1 and remove the prefix from the current sequence.
- Repeat step 2 unless the sequence is vanished or have gcd greater than 1.
If the answer is zero then print ā-1ā or print answer.
As every time, we are choosing the best cut possible so the overall answer is optimum possible. One way to prove this is by contradiction. I left this for you.
SOLUTIONS:
Setter's Solution
#include <bits/stdc++.h>
#define int long long
#define endl ā\nā
#define mod 1000000007
using namespace std;
int32_t main()
{
int t;
cin >> t;
while(t--)
{
int n;
cin >> n;
vector <int> v;
for(int i=0;i<n;i++)
{
int x;
cin >> x;
v.push_back(x);
}
reverse(v.begin(),v.end());
int curr = 0;
int ans = 0;
for(int i=0;i<n;i++)
{
curr = __gcd(curr, v[i]);
if(curr == 1)
{
ans++;
curr = 0;
}
}
if(ans == 0)
cout << -1 << endl;
else
cout << ans << endl;
}
}
Tester's Solution
#include<bits/stdc++.h>
#define MOD 1000000007
using namespace std;
using ll=long long;
ll gcd(ll a,ll b)
{
if(a<b)
swap(a,b);
if(!b)
return a;
return gcd(b,a%b);
}
int main()
{
int n,t;
cin>>t;
while(t--)
{
cin>>n;
vector<int> v(n);
for(int i=0;i<n;i++)
{
cin>>v[i];
}
int ans=0,ref=0;
for(int i=0;i<n;i++)
{
ref=gcd(ref,v[i]);
if(ref==1)
{
ans++;
ref=0;
}
}
if(ans)
cout<<ans<<endl;
else
cout<<-1<<endl;
}
}