decrypt_me's blog

By decrypt_me, history, 13 months ago, In English

Problem Link : Problem Link : Black in Black

In solution , It is written take unique values in queries and mod with 2 because pressing twice is means doing nothing. I understood but let's say you first pressed 6th button then every 6th button state changes and later on you pressed 3rd button so, it will change every 3rd button states but I want to say that 3rd button pushing also changing the states of 6th button so, pressing count of 6th button is taken twice. Please suggest how count of pressing unique values working.

Full text and comments »

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

By decrypt_me, history, 15 months ago, In English

Need Help! IN CSES Graph Series in Shortest Route 2 problem it is accepting solution of floyd warshall algorithm while O(n*2logn) not (using dijkastra Priority queue).

#

I want to know , when It is benificial to use floyd warshall algorithm and when not ?

Full text and comments »

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

By decrypt_me, history, 15 months ago, In English

Why it is showing TLE in 3 testcases

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




void helper(string str){
    string temp = "#";
    long long int n = str.length();
    // because for even length it made palindrome of odd length
    // for example   #a#b#b#a#  = length(9) while it is of length(4);
    for(long long int i =0;i<n;i++){
          temp += str[i];
          temp += "#";
    }
    
    int l = 0,r = -1;
    // taking the segment [l,r] which is palindrome 
    // then let  "ababcbaba" is palindrome and center is 'c' then for 'a'(part right of 'c' )
    // the kickstart length of palindrome same as 'a'(part left of 'c')
    long long int m = temp.length();
    vector<long long int>ans(m,0);
   for(long long int i = 0;i<temp.length();i++){
          if(i>r){
             ans[i] = 0;
          }else{
              ans[i] = min(ans[l+r-i],r-i);
          }
          while(i-ans[i]>=0 && i+ans[i]<temp.length() && temp[ans[i]+i]== temp[i-ans[i]] ){
    //             cout<<temp[i+ans[i]]<<" ";
               ans[i]++;

          }
     //     cout<<" I am answer "<<ans[i]<<endl;
          if(i+ans[i]>r){
             r = i+ans[i];
             l = i-ans[i];
          }
   }
   long long int ind = -1;
   long long int len = -1;
    for(long long int i = 0;i<ans.size();i++){
    //   cout<<ans[i]<<" ";
       if(ans[i]>len){
          len = ans[i];
          ind = i;
       }
    }
    string t = "";
    bool flag = true;
     while(len>1){
        if(flag && len%2==0){
           flag = false;
          if(temp[ind]!= '#')
           t += temp[ind];

        }else if(flag && len%2 != 0){
            flag = false;
          if(temp[ind] != '#')
            t += temp[ind];
        }else{
           if(temp[ind] != '#'){
               t = temp[ind]+ t + temp[ind];
           }
        }
         ind--;
         len--;
     }

     cout<<t<<endl;
   
}

void solve(){
    string str;
    cin>>str;
    helper(str);
}



int main(){
  solve();
  return 0;
}

Full text and comments »

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

By decrypt_me, history, 16 months ago, In English

Link : https://cses.fi/problemset/task/1130/ My approach : 1. using dfs I going down if leaf node encounter then take it if its parent is not visited and mark both of them visited.

  1. If lets all child is giving answer and if any one of the child is not visited and parent is not visited increment count by 1 and mark them visited.
#include<bits/stdc++.h>
using namespace std;


unordered_map<int,vector<int>>mp;



int dfs(int i,int prev,vector<int>&visited){
        
        if(mp[i].size()==0){
// case 1 leaf case 
           if(prev != -1 && !visited[i] && !visited[prev]){
             visited[i] = 1;
             visited[prev]= 1;
            
             return 1;
           }
          
           return 0;
        }
        int cal = 0;
        int p = -1;
        for(auto x : mp[i]){
            
            cal += dfs(x,i,visited);
           if(!visited[x]){
             p = x;
           }
        }
// case 2 for non leaf case 
        if(p != -1 && !visited[p]){
            if(!visited[i] && !visited[p]){
              cal++;
               visited[i] = 1;
               visited[p] = 1;
            }
        }
  
        return  cal;

}
void solve(){
    int n ;
    cin>>n;
 
    for(int i = 1;i<=n-1;i++){
       int a,b;
       cin>>a>>b;
      mp[a].push_back(b);
    }
    vector<int>visited(n+1,0);

   int ans = 0;
   for(int i= 1;i<=n;i++){
      int prev = -1;
      if(!visited[i]){
        ans += dfs(i,prev,visited);
      }
   }
   cout<<ans<<endl;
   
}

void template1(){
     
    int t;
    cin>>t;

    while(t>0){
        solve();
        t--;
    }
}


void template2(){
    solve();
}


int main(){
   // template1();
     template2();
    return 0;
}

Full text and comments »

  • Vote: I like it
  • -6
  • Vote: I do not like it