MININS - Editorial

PROBLEM LINK:

Division 1
Division 2
Video Editorial

Author: Naman Jain
Tester: Rahul Dugar
Editorialist: Ritesh Gupta

DIFFICULTY:

Easy

PREREQUISITES:

Observation, GCD

PROBLEM:

You are given a sequence of N integers. This sequence is circular ― for each valid i, the element (i+1)-th follows after i-th, and the first element follows after the N-th element.

You may add any positive integers at any positions you choose in this sequence; let’s denote the resulting sequence by B. This sequence is also circular. A subarray is said to be good if there exists a valid pair of adjacent elements such that they have their GCD is equal to 1.

For each K from 2 to N inclusive, find the smallest possible number of elements that need to be inserted into A to form a sequence B for which all the subarrays of size K are good.

QUICK EXPLANATION:

  • If the gcd of all the adjacent elements including the first and last is greater than 1 then the answer can be found easily and it is fixed for any N.
  • In other cases, let’s divide the array into a minimum number of subarrays such that the GCD of any adjacent pair in those subarrays should be greater than 1.
  • Now, for each subarray, we just need to check for each value of K, how many numbers need to be inserted.
  • We can optimize it to check only K values which are less than the size of that subarray.

EXPLANATION:

We always introduce 1 if we want to introduce any element at any place as it gives GCD with 1 to any other positive integer.

Let suppose there is no adjacent pair of numbers in the given sequence such that they have their GCD equal to 1, then for each K from 2 to N, the answer is equal to N/(K-1) + (N\%(K-1) > 0).

For other cases, we first need to divide the given sequence in minimum numbers of subarray(non-circular) such that there are no two adjacent elements that have the GCD equal to 1 then we can know the continuous parts of the given circular array where we need to introduce new elements.

Now, for each of this subarray, we can need to find the answer independently and sum all of them to find the overall answer.

Why is it working? As these subarrays are disjoint only those places where they are having GCD equal to 1 for any adjacent element.

To calculate answer for any subarray of size sz, we can check for each value of K from 2 to sz, how many numbers needs to be inserted to satisfy the given conditions and it can be easily seen to be (sz-1)/(K-1).

We can further optimize it with this: As size is the only thing it matters to compute the number of new elements needed to satisfy the condition. So, we create a frequency array to store the sizes and we can show that there are no more than 1000 distinct values are possible for this array.

TIME COMPLEXITY:

TIME: O(N)
SPACE: O(N)

SOLUTIONS:

Setter's Solution
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
 
template<class T> ostream& operator<<(ostream &os, vector<T> V) {
 os << "[ "; for(auto v : V) os << v << " "; return os << "]";}
template<class L, class R> ostream& operator<<(ostream &os, pair<L,R> P) {
	return os << "(" << P.first << "," << P.second << ")";}
 
#define TRACE
#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
	cout << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
	const char* comma = strchr(names + 1, ',');cout.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...) 1
#endif
 
 
#define vi vector<int>
#define pii pair<int, int>
#define vpii vector< pii >
#define I insert 
#define pb push_back
#define F first
#define S second
#define ll long long
#define ld long double
#define vll vector<ll>
#define pll pair<ll,ll>
#define vpll vector<pll>
#define endl "\n"
 
 
// const int mod=1e9+7;
// inline int mul(int a,int b){return (a*1ll*b)%mod;}
// inline int add(int a,int b){a+=b;if(a>=mod)a-=mod;return a;}
// inline int sub(int a,int b){a-=b;if(a<0)a+=mod;return a;}
// inline int power(int a,int b){int rt=1;while(b>0){if(b&1)rt=mul(rt,a);a=mul(a,a);b>>=1;}return rt;}
// inline int inv(int a){return power(a,mod-2);}
// inline void modadd(int &a,int &b){a+=b;if(a>=mod)a-=mod;} 
 
 
void solve(){
	int N; cin>>N;
	vi sz;
	vi v(N);
	int tot=0;
	for(int i=0;i<N;i++){
		cin>>v[i];
		if(i==0 || __gcd(v[i], v[i-1])==1){
			sz.pb(1); tot++;
		}
		else sz[tot-1]++;
	}
	bool full = 0;
	if(tot>1 && (__gcd(v[0], v.back())>1) ) { sz[0]+=sz.back(); sz.pop_back(); }
	if(tot==1 && (__gcd(v[0], v.back())>1)) full =1;
	vi ans(N+1, 0);
	for(auto z:sz){
		for(int i=2; i<=z;i++){
			ans[i] += (z-1)/(i-1);
			if(full) ans[i]++;
		}
	}
	for(int i=2;i<=N;i++){
		cout<<ans[i]<<" ";
	}
	cout<<"\n";
}
 
int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);cout<<setprecision(25);
	int T; cin>>T;
	while(T--) solve();	
}
Tester's Solution
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#ifndef rd
#define trace(...)
#define endl '\n'
#endif
#define pb push_back
#define fi first
#define se second
#define int long long
typedef long long ll;
typedef long double f80;
#define double long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define sz(x) ((long long)x.size())
#define fr(a,b,c) for(int a=b; a<=c; a++)
#define rep(a,b,c) for(int a=b; a<c; a++)
#define trav(a,x) for(auto &a:x)
#define all(con) con.begin(),con.end()
const ll infl=0x3f3f3f3f3f3f3f3fLL;
const int infi=0x3f3f3f3f;
//const int mod=998244353;
const int mod=1000000007;
typedef vector<int> vi;
typedef vector<ll> vl;
 
typedef tree<pii, null_type, less<pii>, rb_tree_tag, tree_order_statistics_node_update> oset;
auto clk=clock();
mt19937_64 rang(chrono::high_resolution_clock::now().time_since_epoch().count());
int rng(int lim) {
	uniform_int_distribution<int> uid(0,lim-1);
	return uid(rang);
}
int powm(int a, int b) {
	int res=1;
	while(b) {
		if(b&1)
			res=(res*a)%mod;
		a=(a*a)%mod;
		b>>=1;
	}
	return res;
}
 
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;
			}
			assert(l<=x && x<=r);
			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,' ');
}
 
 
int sum_n=0;
int a[100005];
void solve() {
	int n=readIntLn(2,100000);
	sum_n+=n;
	assert(sum_n<=2000000);
	fr(i,1,n)
		if(i!=n)
			a[i]=readIntSp(1,1000'000'000);
		else
			a[i]=readIntLn(1,1000'000'000);
//	int n;
//	cin>>n;
//	fr(i,1,n)
//		cin>>a[i];
	a[n+1]=a[1];
	int te=0;
	vi poo;
	fr(i,1,n) {
		if(__gcd(a[i],a[i+1])>1)
			te++;
		else {
			if(te)
				poo.pb(te);
			te=0;
		}
	}
	if(te==n) {
		rep(i,1,n)
			cout<<(n+i-1)/i<<" ";
		cout<<endl;
	} else {
		if(te) {
			if(__gcd(a[1],a[2])>1)
				poo[0]+=te;
			else
				poo.pb(te);
		}
		sort(all(poo));
		reverse(all(poo));
		rep(i,1,n) {
			int an=0;
			for(int j=0; j<sz(poo)&&poo[j]>=i; j++)
				an+=poo[j]/i;
			cout<<an<<" ";
		}
		cout<<endl;
	}
}
 
signed main() {
	ios_base::sync_with_stdio(0),cin.tie(0);
	srand(chrono::high_resolution_clock::now().time_since_epoch().count());
	cout<<fixed<<setprecision(8);
	int t=readIntLn(1,2000);
//	int t=1;
//	cin>>t;
	fr(i,1,t)
		solve();
	assert(getchar()==EOF);
	return 0;
}
Editorialist's Solution
#include <bits/stdc++.h>
 
using namespace std;
 
int ans[200010];
 
int32_t main() {
	int t;
	cin >> t;
 
	while(t--) {
		int n;
		cin >> n;
 
		int prev = 1;
		vector <int> v;
		vector <int> v1;
 
		for(int i=0;i<n;i++) {
			int x;
			cin >> x;
 
			v1.push_back(x);
 
			if(__gcd(prev, x) > 1) {
				int top = v.back();
				v.pop_back();
				v.push_back(top+1);
			} else {
				v.push_back(1);
			}
			
			prev = x;
		}
 
		if(__gcd(v1[0], v1.back()) > 1 && v.size() == 1) {
			for(int i=2;i<=n;i++) {
				cout << n/(i-1) + (n%(i-1) != 0) << " ";
			}
			cout << endl;
			continue;
		}
 
		if(__gcd(v1[0], v1.back()) > 1) {
			v[0] += v.back();
			v.pop_back();
		}
 
		for(int i=2;i<=n;i++) {
			ans[i] = 0;
		}
 
		for(int i:v) {
			for(int j=2;j<=i;j++) {
				ans[j] += (i-1)/(j-1);
			}
		}
 
		for(int i=2;i<=n;i++) {
			cout << ans[i] << " ";
		}
		cout << endl;
	}
} 

Video Editorial

4 Likes

Thanks for the lightning quick editorials :slight_smile:

2 Likes

https://www.codechef.com/viewsolution/38062768
I did the same thing can anyone tell why its giving WA

i was doing the same thing, manually checked for many cases and it was passing them all but i’m getting WA. Can anyone please check?
https://www.codechef.com/viewsolution/38062515

Can you explain why the number of distinct values be less than 1000?

1 Like

(1+2+3....+1000) >= 5*10^5 which is greater than value of N

The minimum possible N values are from 1 to N and these values represent the length of some subarray. So, sum of them is n*(n+1) which should be less then or equal the length of the array itself. Now, try some simple math.

prev should be updated each time inside the for loop. Otherwise it is always equal to 1.

I feel so bad for myself xD. I just missed one condition to check if gcd(arr[n-1], arr[0]) != 1 in the case where there is only one subarray and that costed me.
Solution during the contest: https://www.codechef.com/viewsolution/38075758
AC solution: https://www.codechef.com/viewsolution/38080300

Sorry for typo. It is updated now.

@rishup_nitdgp
What’s wrong with this? It has the same logic that you have in the editorial

Code

@rishup_nitdgp Editor’s code not working for all cased when gcd(a, a1, …,an) !=1.
Ex - 5,10,15,20.

Hi shivam,

Thanks for pointing out. Actually, I added the wrong solution by mistake. It is corrected now.

Why the time is O(N)?

2 Likes

Are subsequence and subarray same thing? @ri

1 Like

Nope, subsequence and subarray are different, tester should have verified this point. I had the same doubt before but if you think, for K = 2 we cannot answer the question since we can always chose 2 non - coprime pairs. After that, I assumed it as subarray and solved it.
Also, why wasn’t any explanation given for sample @smartnj. It took me a lot of time to understand the sample.

1 Like

Even tester has not notice such a big mistake :’(

The main thing to understand in in this question was not not =yes!!

2 Likes

@rishup_nitdgp
Can someone check my solution why I am getting WA? I did the exact same approach as used in Editorial. Please help

Edit: Got AC.

If we iterate on individual gaps and then for each gap, add contribution to only viable group sizes K where gap size >= K, then it can be proved that the time complexity of the brute force solution is NlogN at worst using harmonic sum

1 Like