CASTP Editorial

PROBLEM LINK:

CASTP,
ACRN2021

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;     

     }