LONGEST COMMON SUBSTRING




#include<iostream>
#include<stdio.h>
#include<bits/stdc++.h>

using namespace std;

int main()
{
char a[100],b[100];
int i,j,l1,l2,result=0;
cout<<"enter first string "<<endl;
scanf("%s",a);

cout<<"enter second string "<<endl;
scanf("%s",b);

int dp[100][100];
l1=strlen(a);
l2=strlen(b);

for(i=0;i<=l1;i++)
{
 for(j=0;j<=l2;j++)
 {
  if(i==0 || j==0)
  dp[i][j]=0;

  else if(a[i-1]==b[j-1])              // same same mtch pe diagonal  se 1 jyada
  {
  dp[i][j]=dp[i-1][j-1]+1;
  result=max(result,dp[i][j]);
  }

  else
  dp[i][j]=0;
 }
}

cout<<"LC substring  is "<<result<<endl;

return 0;
}

LONGEST  COMMON SUBSEQUENCE




#include<iostream>
#include<stdio.h>
#include<bits/stdc++.h>

using namespace std;

int main()
{
char a[100],b[100],i,j,l1,l2;
cout<<"enter first string "<<endl;
scanf("%s",a);

cout<<"enter second string "<<endl;
scanf("%s",b);

int dp[100][100];
l1=strlen(a);
l2=strlen(b);

for(i=0;i<=l1;i++)
{
 for(j=0;j<=l2;j++)
 {
  if(i==0 || j==0)
  dp[i][j]=0;

  else if(a[i-1]==b[j-1])       // same same mtch pe diagonal  se 1 jyada
  dp[i][j]=dp[i-1][j-1]+1;

  else
  dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
 }
}

cout<<"LCS is "<<dp[l1][l2]<<endl;

return 0;
}

LIS   SIMPLE  O(n2)





#include<iostream>

using namespace std;

int main()
{
int n,i;
cin>>n;

int a[n],maximum[n],maxx=0,j;

maximum[0]=1;

for(i=0;i<n;i++)
cin>>a[i];

for(i=1;i<n;i++)
{
 maxx=0;
 for(j=0;j<i;j++)
 {
  if(a[i]>a[j] && maximum[j]>=maxx)
   maxx=maximum[j];
 }
 maximum[i]=maxx+1;
}
maxx=0;

for(i=0;i<n;i++)
if(maxx<maximum[i])
maxx=maximum[i];

cout<<"LIS is "<<maxx<<endl;

return 0;
}

LIS CODE WITH  MULTISET


if  we  required  repeated  elements we use upper_bound(s.begin(),s.end(),g)   if(it!=s.end()) then erase(it);



if repaeated elements are not required then we use---->>>>  s.find(g);  it++;  if(it!=s.end()) then erase(it);


#include <iostream>
#include <set>
#include <algorithm>
using namespace std;

int main()
{
    int n,g;
    multiset<int> s;
    multiset<int>::iterator it;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>g;
        s.insert(g);
        it = upper_bound(s.begin(), s.end(), g);
        if(it!=s.end())
        s.erase(it);
    }
    cout<<s.size()<<endl;
    return 0;
}

NETWORK FLOW

 NETWORK   FLOW   ( E. Soldier and Traveling codeforces )

This concept of network flow is useful in problems like

 "Marriage problem"  in which the motive is to make maximum pairs.

In this problem we make a source and a sink. After that we find all the possible paths from source to sink (using bfs). while using bfs we have to save parents of each node in the path. It will help us to find the maximum flow in this path.

If we subtract this maxflow fom the path ,we will get residual graph. 



#include<bits/stdc++.h>

using namespace std;

int graph[1000][1000];

int main()
{
  int v,e,i,j,k,l,v1,v2;
  cin>>v>>e;

  for(i=1;i<=v;i++)           ///present situation   ('0' is source)
   cin>>graph[0][i];


  for(i=1;i<=v;i++)           ///future situation    ('2*v+1' is sink)
   cin>>graph[i+v][2*v+1];


   for(i=1;i<=e;i++)
   {
    cin>>v1>>v2;
    graph[v1][v2+v]=INT_MAX;
    graph[v2][v1+v]=INT_MAX;
   }

   for(i=1;i<=v;i++)
   graph[i][v+i]=1e6;

///-------------------------------------------flow started----------------------------------------------------///

while(1)
{
  queue<int> q;
  q.push(0);

 int parent[2*v+2];               ///parent array
  for(k=0;k<=2*v+1;k++)
    parent[k]=0;
     parent[0]=-1;                ///source ka parent -1



  int visited[2*v+2];             ///vsisited array
   for(k=0;k<=2*v+1;k++)
    visited[k]=0;
    visited[0]=1;               ///  only source is visited



  while(!q.empty())
  {
    int p=q.front();
    q.pop();

    visited[p]=1;

     for(k=0;k<=2*v+1;k++)
      if(graph[p][k]>0 && visited[k]==0)
      {
        parent[k]=p;
        q.push(k);
      }
  }
   //cout<<"hi";

   if(visited[2*v+1]==0)                         ///agar kisi v baar source se destination nahi aa paaye toh break;
     break;

      int mxflow=99999;
   for(k=2*v+1;parent[k]!=-1;)                  ///ye batayega ki maximum flow kitna ho sakta hai iss path mein
   {
    mxflow= min(mxflow,graph[parent[k]][k]);
    k=parent[k];
   }

    for(k=2*v+1;parent[k]!=-1;)
   {
    graph[k][parent[k]]+=mxflow;
    graph[parent[k]][k]-=mxflow;
    k=parent[k];
   }

}
for(i=1;i<=v;i++)
{
    if(graph[0][i]||graph[i+v][2*v+1])
    {
        cout<<"NO"<<endl;
        return 0;
    }
}
cout<<"YES"<<endl;

   for(i=1;i<=v;i++)
   {
      for(j=1;j<=v;j++)
      cout<<graph[j+v][i]<<" ";
      cout<<endl;
   }
return 0;
}

Recusive Dp (Branch & Bound )

Strategy for the World Cup (codechef )

In this question we have to complete a given amount of runs using only 4's and 6's

 we have to say the no. of ways by which we can do this.

 in this question there are four cases

 case 1) run=6    then--->> ball= ball-1 , run=run-6, wicket=wicket

 case 2) run=4     then--->> ball= ball-1 , run=run-4, wicket=wicket
 case 3) run=0     then--->> ball= ball-1 , run=run, wicket=wicket
 case 4) run=out  then--->> ball= ball-1 , run=run, wicket=wicket-1


base case if (run==0 && bal==0 && w>=0 ) this will return 1;







#include<bits/stdc++.h>

using namespace std;

long long  dp[305][1805][15];

long long  solve(long long  b,long long  r,long long  w)
{
  long long  a=0;

  if(r==0 && b==0 && w>=0)
  return 1;

  if(w<0 || b<=0 || r<0)
  return 0;

 if(dp[b][r][w]!=-1)
  {
    return dp[b][r][w];
  }
 
 
 long long  &ret=dp[b][r][w];
   ret=0;


   a=a+solve(b-1,r-6,w);
   a=a%1000000007;

   a=a+solve(b-1,r-4,w);
   a=a%1000000007;

   a=a+solve(b-1,r,w);
   a=a%1000000007;

   a=a+solve(b-1,r,w-1);
   a=a%1000000007;
   return ret=a;

}




int  main()
{
 long long i,j,k;
 //memset(dp,-1,sizeof(dp));
 for(i=0;i<301;i++)
     for(j=0;j<1801;j++)
       for(k=0;k<11;k++)
         dp[i][j][k]=-1;
 long long  t;
 cin>>t;
 while(t--)
 {
  long long  b,r,w,i;
  cin>>r>>b>>w;

  if(r>1800 || r%2==1 )
    cout<<0<<endl;
  else
  cout<<solve(b,r,w)<<endl;
 }
return 0;
}

Recursion  Questions  (Branch & Bound)

The Game Of Weights (codechef )

In this question , there are two cases

 

case1) when barrier[i] < total barrier  ( here we have two options either we can take this or leave this)

case2 ) when barrier[i] > total barrier (here we must have to take this)

Base condition of this recursion , if we reached at last position ,

                                                              and if barrier[i] < total barrier then  

                                                                            return total cost. 

                                                                    else  return total cost+cost[i]

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

long int  cost[10000];
long int  barrier[10000];
long int  n;

long int  dp[1005][1005];

long int  comp(long int  i,long int  tbarr, long int  tcost)
{
    if(dp[i][tcost])
        return dp[i][tcost];

 if(i==n)
 {
   if(barrier[i]<tbarr)
   {
    return dp[i][tcost]=tcost;
   }
    else
    {
     return dp[i][tcost]=tcost+cost[i];
    }
 }

 if(barrier[i]<=tbarr)
 {
   return dp[i][tcost]=min(comp(i+1,tbarr+barrier[i],tcost+cost[i]), comp(i+1,tbarr,tcost));
 }

 if(barrier[i]>tbarr)
  {
    return dp[i][tcost]=comp(i+1,barrier[i]+tbarr,tcost+cost[i]);
  }
}



int  main()
{

 cin>>n;

 for(long int  i=1;i<=n;i++)
 {
   cin>>cost[i];
   cin>>barrier[i];
 }
cout<<comp(1,0,0)<<endl;;

return 0;
}

Another  Way  to  find  NcR  using  higher  Secondary school  formula :P


void pre()
{
    for(int i=0;i<=4000;i++)
        nCr[i][0] = 1 ;
    for(int i=1;i<=4000;i++)
        for(int j=1;j<=i;j++)
            nCr[i][j] = ( nCr[i-1][j-1] + nCr[i-1][j] ) % MOD ;
}