VIKRAM91's blog

By VIKRAM91, history, 5 years ago, In English

Recently I did a Gym competition as a virtual contest. I was not able to do Problem D. Largest Group. After completion of the contest, I tried to implement the editorial solution of this given problem. The editorialist is saying that a solution of time complexity O((2^P)*P) will pass. But my solution is giving TLE in test case 2.

Why is my code giving TLE? Is there any other good solution for this problem?

This is my code which I implemented as said in editoiral.

Full text and comments »

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

By VIKRAM91, history, 5 years ago, In English

I have done a contest in codeforces Gym as virtual contest. Where can I find solutions of these problems and similar gym contest?

Full text and comments »

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

By VIKRAM91, history, 5 years ago, In English
  • Vote: I like it
  • 0
  • Vote: I do not like it

By VIKRAM91, history, 6 years ago, In English

I was doing this problem on Spoj. The solution of this problem is that first player always wins.

Can anyone give me proof of this?

Full text and comments »

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

By VIKRAM91, 6 years ago, In English

can anyone tell me what is trick behind this problem?

Full text and comments »

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

By VIKRAM91, history, 6 years ago, In English
  • Vote: I like it
  • 0
  • Vote: I do not like it

By VIKRAM91, history, 6 years ago, In English

I am doing BENEFACT — The Benefactor.

I am using 2-time BFS method to calculate the longest path. Because here cost is associated with every edge so I am doing 2 times Dijkstra instead of 2 times BFS. But I am getting WA.

Can Anyone tell me Why I am getting WA?

Here is my code.

Edit:- Now I have done uknowg BFS instead of Dijkstra and I got Ac. Here is my code.

I want to now why solution using Dijkstra give WA and BFS gives AC.

Can Anyone help me? Please

Full text and comments »

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

By VIKRAM91, history, 6 years ago, In English

I am doing this problem on Spoj and I have written the recursive solution. Which according to me is right. This solution is giving me TLE, so I change to memoization solution. This memoization solution is giving me WA.

Is my memoization of recursive solution wrong? If yes then why and if no then why is it not giving AC.

Is there any better way to do memoization?

Thank you.

Edit:-

I found my mistake. I was not initializing x,y,z. So they are taking garbage values for some testcases. Just initialize them with 0 and it's AC.

AC Solution

Full text and comments »

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

By VIKRAM91, history, 6 years ago, In English

I was doing this Spoj problem and written tabulation method which got accepted, then I have written recursive solution but this gave me the wrong solution(WA), Where is my recursive solution is wrong:-

Below is my tabulation solution which got AC:-

#include<bits/stdc++.h>
using namespace std;
int main(){
  int n;
  cin>>n;
  int a[n]={0};
  int b[n]={0};
  for(int i=0;i<n;i++){
      cin>>a[i]>>b[i];
  }
  int dp[n][2]={{0}};
  dp[0][0]=b[0];
  dp[0][1]=a[0];
  for(int i=1;i<n;i++){
      int x=dp[i-1][0]+abs(a[i]-a[i-1])+b[i];
      int y=dp[i-1][1]+abs(a[i]-b[i-1])+b[i];
      int s=dp[i-1][0]+abs(b[i]-a[i-1])+a[i];
      int t=dp[i-1][1]+abs(b[i]-b[i-1])+a[i];
      dp[i][0]=max(x,y);
      dp[i][1]=max(s,t);
  }
  cout<<max(dp[n-1][0],dp[n-1][1]);
  return 0;
 }

And below is my recursive solution which is giving me WA:-

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

 int ans(int a[],int b[],int n,int j){
    if(n==0&&j==0)
       return b[0];
    if(n==0&&j==1)
       return a[0];
    int x=ans(a,b,n-1,0)+b[n]+abs(a[n-1]-a[n]);
    int y=ans(a,b,n-1,1)+b[n]+abs(b[n-1]-a[n]);
    int s=ans(a,b,n-1,0)+a[n]+abs(a[n-1]-b[n]);
    int t=ans(a,b,n-1,1)+a[n]+abs(b[n-1]-b[n]);
    return max(max(x,y),max(s,t));
}

 int main(){
    int n;
    cin>>n;
    int a[n]={0};
    int b[n]={0};
    for(int i=0;i<n;i++){
       cin>>a[i]>>b[i];
    }
    if(a[0]>b[0])
        cout<<ans(a,b,n-1,1);
    else cout<<ans(a,b,n-1,0)
    return 0;
  }

I want to ask:-

1). What is wrong with my recursive solution.

2). Can we do all dp problem with tabulation and memoization i.e if we can do with memoization than can we do with tabulation and vice versa for every dp problem?

Full text and comments »

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

By VIKRAM91, history, 6 years ago, In English

Problem link:- https://practice.geeksforgeeks.org/problems/find-number-of-times-a-string-occurs-as-a-subsequence/0

I have written recursive solution for this problem:-

#include<bits/stdc++.h>
using namespace std;
int cnt=0;
int ans(string s1,string s2,int n,int m){
   if(n==0&&m==0||m==0)
      return 1;
   if(n==0)
      return 0;
   if(s1[n-1]==s2[m-1]){
       return ans(s1,s2,n-1,m-1)+ans(s1,s2,n-1,m);
    }
   else return ans(s1,s2,n-1,m);
 }

int main(){
    int t;
     cin>>t;
     while(t--){
        int n,m;
         cin>>n>>m;
         string s1,s2;
          cin>>s1>>s2;
        cout<<ans(s1,s2,n,m)<<endl;
    }
   return 0;
 }

How should I approach to do memoization on this given recursive algorithm?

Full text and comments »

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

By VIKRAM91, history, 6 years ago, In English

Can anybody post their solutions here? please.

Full text and comments »

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