 # CASTP Editorial

Authors: Anshul,Saiyam
Testers: Anshul,Saiyam

Easy-medium

Hashing, strings

# PROBLEM STATEMENT:

Given a string s, convert it into a string with not more than k distinct character, where the cost of changing a character x to character y is abs(ASCII(x) -ASCII(y)). The string is composed of only the first 16 alphabets.

# EXPLANATION:

The problem makes use of the fact that there are only 16 valid alphabets.

->So first we preprocess a bitmask of 16 bits.
We store these bitmasks in a vector according to the number of setbits in each number.
For example, numbers like 1,2,4 etc with only 1 set bit in their binary representation are stored in a single vector.
Whereas numbers like 3, which have 2 set bits are stored in a separate vector.

-> Next we create a frequency table of all the letters appearing in the string s.

-> Finally, given k, we try each mask which has number of set bits equal to k.
Here, ith bit of the mask being 1 corresponds to the ith alphabet (with a=0,b=1,c=2,…,p=16),wherever it appears in s, is also present in the final string p.
Similarly, the ith bit of the mask being 0 indicates that the ith alphabet, wherever it appears in s, is changed to some other alphabet in final string p.

The alphabets which correspond to 0 bits in the mask, are changed to the nearest alphabet which has value 1 in the mask.
The cost is calculated for each mask in this way, and then the minimum cost is taken as the final answer.

# SOLUTION:

Tester's Solution

#include<bits/stdc++.h>

``````     #define prime 1000000007

#define pb push_back

#define mp make_pair

#define forn(i,a,b) for (int i = a; i <b; i++)

#define fornn(i,a,b) for (int i = a; i <=b; i++)

#define num 1000000000

#define ALL(v) v.begin(), v.end()

#define INF INT_MAX

typedef long long ll;

using namespace std;

int main()

{  ios_base::sync_with_stdio(false);

cin.tie(NULL);

vector<vector<int>> v(17);

forn(i,0,int(pow(2,16))+1)

{

v[__builtin_popcount(i)].pb(i);

}

int T;

cin>>T;

while(T--)

{

int n,k;

cin>>n>>k;

string s;

cin>>s;

vector<int> p(16,0);

forn(i,0,n)

{p[s[i]-'a']++;

}

int ans=1e9;

forn(i,0,v[k].size())

{ int f=0;

forn(j,0,16)

{

if(((v[k][i]>>j)&1)==0)

{ if(p[j]==0)

continue;

int l=20;

for(int m=j-1;m>=0;m--)

{

if(((v[k][i]>>m)&1)==1 && p[m]>0)

{  l=min(l,j-m);

break;

}

}

forn(m,j+1,16)

{

if(((v[k][i]>>m)&1)==1 && p[m]>0)

{l=min(l,m-j);

break;

}

}

f+=p[j]*l;

}

}

ans=min(ans,f);

}

cout<<ans<<"\n";

}

//WINPAUSE;

return 0;

}
``````