SPOJ: DNA SEQUENCES

3408. DNA Sequences

Problem code: SAMER08D

Link to problem :DNA SEQUENCES

Algorithm: It's a standard DP problem longest common subsequence with constraints that subesquence must be formed from common segments of length k or more.

Hence ans[][] must be updated only when segment size is greater than or equal to k.

Tricky test case to discuss:

4 
aggasdfa 
aggakasdfa

ans:8

possible WA: 5

Last 5 characters asdfa forms a common segment, but char a is also a part of segment agga . Hence instead of a segment of length 5, two segment of length 4 each should be considered.

Thus at i=8,j=10 when cont[i][j]=5 we should update lcs[i][j] considering z=4 and z=5, choosing the maximum of both.

Procedure:
1)apply standard lcs() algorithm.
2)update only when segment_length>=k and select the length of common segment for which lcs[i][j] is maximum.

CODE:

#include <cstdio>
#include<string.h>
#include<stdlib.h>
#define N 1009
#include<algorithm>
using namespace std;

int main()
   {
 char s[N], t[N];
    int lcs[N][N], cont[N][N];//lcs is answer matrix and cont is matrix for storing common segment length
     int k,z;
     scanf("%d", &k);
    while( k ){
        scanf("%s %s", s, t);
        int l1=strlen(s);
        int l2=strlen(t);
        cont[0][0] = 0;
        for(int i = 0; i < N; ++i) lcs[i][0] = lcs[0][i] = 0;
        for(int i = 1; i <= l1; ++i)
            for(int j = 1; j <= l2; ++j)
            {
                lcs[i][j] = max(lcs[i - 1][j], lcs[i][j - 1]);
                if(s[i-1]==t[j-1])
                cont[i][j]=cont[i-1][j-1]+1;
                else 
                cont[i][j]=0;
                //update lcs matrix if segment size is greater than or equal to k
                if(cont[i][j] >= k)
                for(z= k; z <= cont[i][j]; z++)
                    lcs[i][j] = max(lcs[i][j], lcs[i - z][j - z] + z);
            }
        printf("%d\n",lcs[l1][l2]);
        scanf("%d",&k);
    }
    return 0;
}

SPOJ: NOCHANGE

                                     

1847. No Change

Problem code: NOCHANGE

This is a dynamic programming problem. Here is O(k*x) based solution of this problem.

Equation : n1*v1+n2*v2...+nk*vk=x;

 where n1>=n2>=n3...>=nk;

Let ans[x+1] be a boolean array where ans[i] determines whether it is possible to pay money i. 

For coin of value v[0], we calculate ans[i] , if(i%v[0]==0) ans[i]=true  

OR

 in dp term  if(ans[i]==true||ans[i-v[0]]=true) ans[i]==true.

When we get an extra coin of value v[1], as per the constraints we have to pay at least as many coins of value v[0] as of value v[1].

now consider v[1]=v[1]+v[0] i.e a coin of value v[1]+v[0] .As per the equation we have considered n2 number of v1 coins and n2 number of v2 coins and for remaining n1-n2 coins of value v[0], we have already computed ans[i].

now if(ans[i]==true|| ans[i-v[1]]==true) ans[i]=true;

Similar is the case when we consider ans[i] for coins of value v[2]...v[k].

e.g input 13 3 9 2 1.
after processing v[]={9,11,12};
base condition
ans[0]=true :as we can always pay money=0;
ans[i]=false : default (not computed)
ans
optimal substructure: ans[j]=ans[j] | ans[j-v[i]];

CODE:

#include<cstdio>
using namespace std;

int main()
{
 int x,k;
 scanf("%d %d",&x,&k);
 int v[k],i,j;
 for(i=0;i<k;i++)
   {scanf("%d",&v[i]);
  if(i>0)
   v[i]+=v[i-1];
   }

 bool ans[x+1];
//base condition
    ans[0]=true;
  for(i=1;i<=x;i++)
     ans[i]=false;

  for(i=0;i<k;i++)
   {
    for(j=v[i];j<=x;j++)
 {
   ans[j]|=ans[j-v[i]];  
 }
   }
 if(ans[x])printf("YES\n");
 else printf("NO\n");
 return 0;
}