YogeshZT's blog

By YogeshZT, history, 4 months ago, In English

I was doing the question 1498B - Box Fitting. Here are my two submissions 271307925 and 271307851. One of the approaches works correctly while other gives TLE. The only difference between them is how I initialize the iterator 'it' using the upper_bound function.

Full text and comments »

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

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

Full text and comments »

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

By YogeshZT, history, 6 months 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, 13 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