PROBLEM LINK:
Authors: Anshul,Saiyam
Testers: Anshul,Saiyam
DIFFICULTY:
Easy-medium
PREREQUISITES:
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;
}