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