CHEFSTR2 -Editorial

editorial
, , , ,
1

#Problem link:
[Practice] CHEFSTR2 Problem - CodeChef
[Codeyssey] CodeChef: Practical coding for everyone

Author:&editorialist [Abhishek Patnigere] stingray8041 | CodeChef User Profile for Abhishek Patnigere | CodeChef
Tester: [Akshat Goyal] beast787 | CodeChef User Profile for Akshat Goyal | CodeChef

DIFFICULTY: Hard
# PREREQUISITES: Math

Problem with explanation:

So The Problem asks us to convert our current string to a power of any string with any power.

  • So what is a power of a string it is like multiplication of a number say 3^4= 3.3.3.3 . Similarly power of a string can be understood as say we have a string abc so the kth power of our string will be abc concatenated k times with itself. So say S=“abc” is our string than s to the power k where k=4 than our required string is abcabcabcabc.
  • Now what we have to do is we are given a string and we need to convert it to a power of “any” string And for this we can only replace characters or add characters at the end of our current string.
  • It is to note here the second value being inputed after the string is of no use and is present just to create confusion .
  • So what we have to do is say we have a string of length=8 string being abaababa than we can convert it to any string such that in minimum operations it becomes a power of any k>=2
  • The logic here is that we need to calculate the count for each character position of each substring of length=3 And that too for all possible divisions of the string for k>=2 .
  • Now to find the minimum number of replacements we use the greedy approach and find that at each position which character is occuring the most times and subtract it from current k in code it is sz we do this for each letter of substring for positions where character is not present it is considered null and count is increased since a character will be added later. This will give us the minimum number of replacements required.
  • You can see in the code that we have taken our possible k (sz) only upto 3n/4 why is that?
    This can be understood like this consider a string of length 8 whats the maximum replacements required to make it a power of a string. That is n/2. Why?? Because at n/2 replacements in the worst case scenario we can replace all the characters of half of our string say abcdefgh so we can replace efgh to abcd and we have our required power of string in n/2 replacements.
  • Now still why 3n/4 because as we move above n/2 at every number we don’t have a character i.e null so count is going to increase so for an additional n/4 we have to add n/2 characters at the end that is the maximum so there is no point going above 3n/4.
    From an example you can see say length of string is 8 and our k=6 so string is divided by 6
    Therefore we have 6 characters in our first substring and 2 in second so have to add 4 characters in second substring which is equal to n/2.
  • So there is no point in considering a k>3n/4. Besides that’s where we will even get a TLE if we take greater than 3n/4 so it’s a must requisite.
  • In our example we run the loop and find that minimum is when we add two characters at end of abaababa the two character’s being ab.
  • We need to output the minimum changes with final k.

#Solutions:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define all(x) x.begin(),x.end()
#define debug(x) cout << “(” << #x << ": " << x << “)” << endl;

void solve() {
string s;
cin >> s;
int k;
cin >> k;
int n = s.size();
ll ans=0;
vector freq(26,0);

int len_copy = n/k;
ll mx=-1;

ll ops=1e6, pow=1e6;

for(int sz=1; sz<=3*n/4; sz++) {
ll o=0;
ll ks= ceil(float(n)/float(sz));
for(int i=0; i<sz; i++) {

  	for(int x=0; x<26; x++)
  		freq[x]=0;

  	for(int j=i; j<n; j+=sz)
  		freq[s[j]-'a']++;

  	mx = *max_element(all(freq));
  	o += ks - mx;
  }

  if(ops == o) {
  	if(ks < pow)
  		pow = ks;
  }

  else if(o < ops) {
  	ops = o;
  	pow = ks;
  }

}

cout << ops << " " << pow << endl;
}

int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
solve();
}