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.

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

Problem Link:- http://mirror.codeforces.com/gym/101915/problem/D

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?

can anyone tell me what is trick behind this problem?

Problem link:- http://www.spoj.com/problems/MKTHNUM/

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

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

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?

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?

Can anybody post their solutions here? please.