YogeshZT's blog

By YogeshZT, history, 8 days 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();
}  

Full text and comments »

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

By YogeshZT, history, 7 weeks ago, In English

I read somewhere that unordered maps are faster than normal maps. However when I was solving a question, the moment I replaced the map with an unordered map, it gave TLE. Here is the submission 262627698

Full text and comments »

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

By YogeshZT, history, 9 months ago, In English

Hello, I was solving the question which involves finding Kth ancestor of a node in a tree using binary lifting. I was wondering if instead of binary lifting, is there something like n-ary lifting (n>2 ofc). Is it something which can be thought of and will it be more efficient?

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it