DECOGCD - Editorial

PROBLEM LINK:

Practice
Contest

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;
}

}

1 Like

Your editorials are great !!! Thanks