LOJ – 1013 – Love Calculator

Link : Problem
Algo : DP

Let dp[i][j] -> The length of the shortest string that contains a[1…i] and b[1….j] as sub-sequence
Let dp2[i][j] -> Total number of unique shortest strings which contain a[1…i] and b[1….j] as sub-sequence

The recurrence relation :

if(a[i] == b[j] ) {
      dp[i][j] = 1 + dp[i-1][j-1]; // Just add a[i] to the dp[i-1][j-1]
      dp2[i][j] = dp2[i-1][j-1];
}
else {
      dp[i][j] = 1 + min(dp[i][j-1] , dp[i-1][j]); // Check which one is minimum
      if(dp[i][j-1] == dp[i-1][j]) dp2[i][j] = dp2[i][j-1]  + dp2[i-1][j];
      else dp2[i][j] = dp[i][j-1] < dp[i-1][j] ? dp2[i][j-1] : dp2[i-1][j];
}

Solution :

/*
 
 *************************
 Id  : Matrix.code
 Task: 1013 - Love Calculator
 Date: 10/9/15.
 **************************
 
 */

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

/*------- Constants---- */

#define LL                      long long
#define ull                     unsigned long long
#define mod                     1000000007
#define MEMSET_INF              63
#define MEM_VAL                 1061109567
#define forn(i,n)               for( int i=0 ; i < n ; i++ )
#define mp(i,j)                 make_pair(i,j)
#define lop(i,a,b)              for( int i = (a) ; i < (b) ; i++)
#define pb(a)                   push_back((a))
#define all(x)                  (x).begin(),(x).end()
#define gc                      getchar_unlocked
#define PI                      acos(-1.0)
#define INF                     1<<29
#define EPS                     1e-9
#define Fr                      first
#define Sc                      second
#define Sz                      size()
#define lc                      ((n)<<1)
#define rc                      ((n)<<11)
#define db(x)                   cout << #x << " -> " << x << endl;
#define Di(n)                   int n;si(n)
#define Dii(a,b)                int a,b;si(a);si(b)
#define Diii(a,b,c)             int a,b,c;si(a);si(b);si(c)
#define min(a,b)                ((a)>(b) ? (b) : (a) )
#define max(a,b)                ((a)>(b) ? (a):(b))
/*---- short Cuts ------- */
#define ms(ara_name,value) memset(ara_name,value,sizeof(ara_name))
typedef pair<int, int> ii;
typedef vector<int > vi ;
/*------ template functions ------ */
#ifndef getchar_unlocked
#define getchar_unlocked getchar
#endif
template<class T> inline void si(T &x){register int c = gc();x = 0;int neg = 0;for(;((c<48 | c>57) && c != '-');c = gc());
      if(c=='-') {neg=1;c=gc();}for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}if(neg) x=-x;}template <class T> inline T bigmod(T p,T e,T M){LL ret = 1;for(; e > 0; e >>= 1){if(e & 1) ret = (ret * p) % M;p = (p * p) % M;} return (T)ret;}
template <class T> inline T gcd(T a,T b){if(b==0)return a;return gcd(b,a%b);}
template <class T> inline T modinverse(T a,T M){return bigmod(a,M-2,M);}
void IN(){    freopen("in.txt","r",stdin); freopen("out.txt","w",stdout);}

/*************************** END OF TEMPLATE ****************************/
const int N = 35;
char a[N], b[N];
LL dp[N][N];
LL dp2[N][N];

int main()
{
      
      Di(t);
      int cs = 0;
      while(t--){
            scanf("%s %s", a+1,b+1);
            for(int i=0;i<N;i++) dp[0][i]= dp[i][0] = i,  dp2[i][0] = dp2[0][i] = 1;
            int N1, N2;
            for(int i=1;a[i]; i++ ) N1 = i;
            for(int i=1;b[i]; i++ ) N2 = i;
            for(int i=1; a[i] ; i ++) {
                  for(int j= 1; b[j] ; j ++ ) {
                        if(a[i] == b[j] ) {
                              dp[i][j] = 1 + dp[i-1][j-1];
                              dp2[i][j] = dp2[i-1][j-1];
                        }
                        else {
                              dp[i][j] = 1 + min(dp[i][j-1] , dp[i-1][j]);
                              if(dp[i][j-1] == dp[i-1][j]) dp2[i][j] = dp2[i][j-1] + dp2[i-1][j];
                              else dp2[i][j] = dp[i][j-1] < dp[i-1][j] ? dp2[i][j-1] : dp2[i-1][j];
                        }
                        //printf("%d %d %d\n", i,j,dp[i][j]);
                  }
            }
            printf("Case %d: %lld %lld\n",++cs, dp[N1][N2] , dp2[N1][N2]);
      }
      return 0;
      
}