PROBLEM LINK:
Author: d_en_ominator and dyrroth
Tester: dyrroth
Editorialist: dyrroth
DIFFICULTY:
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;
}