Bitmask approach not working

Revision en1, by YogeshZT, 2024-07-06 08:51:16

I was solving 1741E — Sending a Sequence Over the Network 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();
}  

Tags bitmasks, backtracking

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English YogeshZT 2024-07-06 08:53:31 54
en1 English YogeshZT 2024-07-06 08:51:16 2028 Initial revision (published)