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: GAME OF LINES

                                 

3184. Game of Lines

Problem code: LINES

Link to problem: http://www.spoj.com/problems/LINES/

SOLUTION: find number of all different slopes possible.

All slopes:

can be found in O(n^2) time by considering all possible combinations.

Different slopes:

How to remove or detect duplicate value of slopes?
STL library class set is the data structure which should be used as it contains only unique keys.Map can also be used but set will serve our purpose better.

Slopes:
Slopes can be stored in set in two ways.

1) double slope, but  can be a possible source of WA (wrong answer) for various reasons.
2) int mx=(x2-x1) , my=(y2-y1); 

    m=gcd(mx,my);
    mx/=m; my/=m;

    now pair(mx,my) can be inserted into the set. 

SOURCE CODE:

#include<stdio.h>
#include<map>
#include<set>
#include<algorithm>
#include<iostream>
#include<limits.h>
using namespace std;

int gcd(int m,int n)
{
if(m==0)return n;
return gcd(n%m,m);
}

int main()
{
int n;
scanf("%d",&n);
while(n!=0)
{
set<pair<int,int> > mp;
int i,x[n],y[n],j;
for(i=0;i<n;i++)
   scanf("%d %d",&x[i],&y[i]);
 int mx,my,m;
for(i=0;i<n;i++)
 {
  for(j=i+1;j<n;j++)
  {
   my=(y[j]-y[i]);
   mx=(x[j]-x[i ]);
   m=gcd(mx,my);
   if(m!=0){
  my/=m;mx/=m;
  if(mx<0)
  {mx*=-1;my*=-1;}
  }
  mp.insert(make_pair(mx,my));
  }
}
  printf("%d\n",mp.size());
  scanf("%d",&n);
}

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