YogeshZT's blog

By YogeshZT, history, 6 months ago, In English

I was solving 1778C - Flexible String and the editorial mentioned that one of the possible approaches of solving it involves bitmasking. I was able to code it using some parts of the code from another backtracking approach(one which has been mentioned in the editorial), my approach was to make a mask for the all the characters which have been pushed into the set and then proceed via the editorial code. However it isn't working. Can someone help me find the problem. Here is the code.

#include<bits/stdc++.h>
#define int long long  
using namespace std;

int min(int a,int b){
    if(a<b)return a;
    return b;
}
int max(int a,int b){
    if(a>b)return a;
    return b;
}

void answer(){
    int t=1;cin>>t;
    while(t--){
        int n,k;cin>>n>>k;
        string a,b;cin>>a>>b;
        unordered_set<int>uniq;
        for(auto it : a){
            uniq.insert(it);
        }
        string list;
        for(auto it : uniq){
            list.push_back(it);
        }
        k=min(k,uniq.size());
        int ans=0;
        for(int mask=0;mask<=(1<<k);mask++){
            if(__builtin_popcount(mask)==k){
                int mark[26];
                memset(mark,0,sizeof mark);
                for(int i=0;i<k;i++){
                    if((1<<i)&mask){
                        mark[list[i]-'a']=1;
                    }
                }
                ll tot_pair=0,match_count=0;
                for(ll i=0;i<a.size();i++) {
                    if(a[i]==b[i] || mark[a[i]-'a'])
                        match_count++;
                    else {
                        tot_pair+=match_count*(match_count+1)/2;
                        match_count=0;
                    }
                }
                tot_pair+=match_count*(match_count+1)/2;
                ans=max(ans,tot_pair);
            }
        }
        cout<<ans<<endl;
    }
    return ;
}
int32_t main(){
    answer();
}  

  • Vote: I like it
  • +1
  • Vote: I do not like it

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by YogeshZT (previous revision, new revision, compare).