Just programming

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   (  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...

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; ...

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.          ...

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 ; }