# ICM0006 (Special String) - Editorial

Div-1 Contest

Div-2 Contest

Div-3 Contest

Author: d_en_ominator and dyrroth

Tester: dyrroth

Editorialist: dyrroth

EASY-MEDIUM:

# PREREQUISITES:

Maths and Good observation skills

# PROBLEM

You are given a string S and you want to make it (n,k) special. String A is (n,k) special if after concatenating n copies of string A we get at least k substring of A in the resulting string ( Overlapping substrings also count ). Your task is to find the minimum number of characters you need to alter to make string S, (n,k) special.

# EXPLANATION:

First, if string S is periodic with maximum period i (periodic means that string S can be divided into i equal sub strings) then after concatenating n copies of string S we get exactly i*n-i+1 substrings.

So we can now find the minimum value of i lets say l, such that l*n-l+1>=k, every i greater than equal to l satisfy the condition. So, now question is reduced to find minimum number of changes required to make string y periodic such that y>=l.

Also if string is y periodic then |S| mod y = 0, i.e. y should be a divisor of |S|. So, iterate through all divisors d of |S| which are greater than equal to l and calculate minimum number of moves to make string d periodic and take minimum for all valid d.

For particular d minimum number of changes can be calculated by storing frequency of every character at position j where j mod d = r, for every r calculate contribution independently and add to ans. Contribution for every r is equal to |S|/d - frequency of maximum occuring character for all j s.t. j mod d = r.

# TIME COMPLEXITY

The time complexity is O(|S|*no. of divisors of |S|) per test case.

# SOLUTIONS

Editorialist's Solution
``````
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
int cnt[100001][26];
int ct[100001];
int main(){
int T=1;
cin>>T;
while(T--){
ll n,k;
cin>>n>>k;
string s;
cin>>s;
ll len=s.size();
vector<ll> div;
for(ll i=1;i*i<=;len;i++){
if(len%i==0){
div.pb(i);
if(i*i!=len){
div.pb(len/i);
}
}
}
ll ans=1e15;
for(auto x:div){
if(x*n-x+1<k)continue;
int m=len/x;
for(int i=0;i<m;i++){
ct[i]=0;
for(int j=0;j<26;j++){
cnt[i][j]=0;
}
}
for(int i=0;s[i];i++){
cnt[i%m][(s[i]-'a')]++;
ct[i%m]=max(ct[i%m],cnt[i%m][(s[i]-'a')]);
}
ll count=0;
for(int i=0;i<m;i++){
count+=(x-ct[i]);
}
ans=min(ans,count);
}
cout<<ans<<"\n";
}

return 0;
}

/*_*/

``````

Tester's Solution
``````
// Jai Shree Ram
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n)     for(int i=a;i<n;i++)
#define ll             long long
#define int            long long
#define pb             push_back
#define all(v)         v.begin(),v.end()
#define x              first
#define y              second
#define gcd(a,b)       __gcd(a,b)
#define mem1(a)        memset(a,-1,sizeof(a))
#define mem0(a)        memset(a,0,sizeof(a))
#define sz(a)          (int)a.size()
#define pii            pair<int,int>
#define hell           1000000007
#define elasped_time   1.0 * clock() / CLOCKS_PER_SEC
template<typename T1,typename T2>istream& operator>>(istream& in,pair<T1,T2> &a){in>>a.x>>a.y;return in;}
template<typename T1,typename T2>ostream& operator<<(ostream& out,pair<T1,T2> a){out<<a.x<<" "<<a.y;return out;}
template<typename T,typename T1>T maxs(T &a,T1 b){if(b>a)a=b;return a;}
template<typename T,typename T1>T mins(T &a,T1 b){if(b<a)a=b;return a;}
const int N = 1e5 + 5;
vector<int>d[N];
int len = 0;
int solve(){
int n,k; cin >> n >> k;
string s;cin>>s;
len += s.length();
int m = s.length();
int ans = hell;
auto check = [&] (int j){
vector<vector<int>>fr(j,vector<int>(26));
vector<int>cnt(j);
for(int i = 0; i < m; i++){
fr[i%j][s[i]-97]++;
cnt[i%j]++;
}
int res = 0;
for(int i = 0; i < j; i++){
int mx = 0;
for(int k = 0; k < 26; k++){
maxs(mx,fr[i][k]);
}
res += cnt[i] - mx;
}
return res;
};
int cnt = 0;
for(auto j:d[m]){
// m/j perodic
// j*(n-1)+j;
if(j*(n-1) + 1 < k)continue;
cnt++;
mins(ans,check(m/j));
}
cout << ans << endl;
return 0;
}
signed main(){
for(int i = 1; i < N; i++){
for(int j = i; j < N; j +=i ){
d[j].push_back(i);
}
}
#ifdef SIEVE
sieve();
#endif
#ifdef NCR
init();
#endif
int t;cin >> t;
while(t--)solve();
assert(len <= 1e5);
return 0;
}
```
```