## 1182 - Sequence Alignment

Moderator: Board moderators

kimbbakar
New poster
Posts: 5
Joined: Wed Nov 13, 2013 8:48 am

### Re: 1182 - Sequence Alignment

Im getting WA.Can anyone give me some test case for this problem please ?

Code: Select all

``````/*
Problem name :
Algorithm : Not Sure Yet
Contest/Practice :
Source :
Comment : Whenever you start to believe  yourself, people also start to believe in you
Date : --
Last Update : 23-Dec-2014
*/

#include<bits/stdc++.h>

#define pause           system("pause");
#define FOR(s,e,inc)    for(int i=s;i<=e;i+=inc)
#define mod             1000000007
#define inf             1<<30
#define pb              push_back
#define ppb             pop_back
#define mp              make_pair
#define F               first
#define S               second
#define sz(x)           ((int)x.size())
#define sqr(x)          ( (x)* (x) )
#define eps             1e-9
#define gcd(x,y)         __gcd(x,y)
#define lcm(x,y)        (x/gcd(x,y))*y
#define on(x,w)         x|(1<<w)
#define check(x,w)      (x&(1<<w))
#define all(x)          (x).begin(),(x).end()
#define pf              printf
#define pi              acos(-1.0)
#define reset(x,v)      memset(x,v,sizeof(x));
#define AND             &&
#define OR              ||

typedef long long ll;
typedef unsigned long long llu;

using namespace std;

template<class T>
inline T mod_v(T num)
{
if(num>=0)
return num%mod;
else
return (num%mod+mod)%mod;
}

template<class T>
T fast_pow(T n , T p)
{
if(p==0) return 1;
if(p%2)
{
T g=mod_v ( mod_v(n) * mod_v(fast_pow(n,p-1)) );
return g;
}
else
{
T g=fast_pow(n,p/2);
g=mod_v( mod_v(g) * mod_v(g) ) ;
return g;
}
}

template<class T>
inline T modInverse(T n)
{
return fast_pow(n,mod-2);
}

template<class T>
inline void debug(string S1,T S2,string S3)
{
cout<<S1<<S2<<S3;
}

template<class T>
inline T in()
{
register char c=0;
register T num=0;
bool n=false;
while(c<33)c=getchar();
while(c>33){
if(c=='-')
n=true;
else num=num*10+c-'0';
c=getchar();
}
return n?-num:num;
}

#ifndef ONLINE_JUDGE
#  define p(x) cout<<x<<endl;
#else if
#  define p(x) 0;
#endif

/*...... ! Code start from here ! ......*/

int dp[55][55][2][2];
int ok[55][55][2][2]={0};

string s1,s2;
int n,cc;
int z1,z2;

int re(int i,int j,int l,int k)
{//printf("%d %d %d %d \n",i,j,l,k);//pause
if(z1==i && z2==j)
{
return 0;
}

if(ok[i][j][l][k] ==cc ) return dp[i][j][l][k];

ok[i][j][l][k]=cc;

dp[i][j][l][k]=-inf;

if(j<sz(s2) && i<sz(s1))
if(s1[i]==s2[j])
dp[i][j][l][k]=max(dp[i][j][l][k] ,2+re(i+1,j+1,1,1) );
if(i<sz(s1) )
dp[i][j][l][k] =max(dp[i][j][l][k] ,re(i+1,j,1,0)-( (k==1)  ) );
if(j<sz(s2) )
dp[i][j][l][k] =max(dp[i][j][l][k] ,re(i,j+1,0,1)-( (l==1)  ) );

return dp[i][j][l][k];
}

int main()
{
#ifndef ONLINE_JUDGE
freopen ( "in.txt", "r", stdin );
#endif

int t;
cc=1;
char ch;

scanf("%d",&t);

scanf("%c",&ch);

while(t--)
{
getline(cin,s1);
getline(cin,s2);

z1=sz(s1);
z2=sz(s2);

int res=-inf;
for(int i=0;i<z1;i++)
{
res=max(res,re(i,0,1,1) );//printf("%d %d\n",i,res);
}
for(int i=0;i<z2;i++)
{
res=max(res,re(0,i,1,1) );
}

printf("%d\n",res);

cc++;
}

return 0;
}

``````

uDebug
A great helper
Posts: 475
Joined: Tue Jul 24, 2012 4:23 pm

### Re: 1182 - Sequence Alignment

kimbbakar wrote:Im getting WA.Can anyone give me some test case for this problem please ?
Looks like you figured it out. Well done!

Perhaps you can consider providing test cases that helped you find your bug?
Check input and AC output for over 7,500 problems on uDebug!

suhendry
New poster
Posts: 14
Joined: Sat Aug 31, 2002 6:55 am

### Re: 1182 - Sequence Alignment

What is the correct output for the following input:

Code: Select all

``````3
SA
SB
AS
BS
AB
CD
``````
My code gives:

Code: Select all

``````0
1
-1``````
My best right alignment for those cases are:

Code: Select all

``````SA-
S-B

A-S
BS

AB--
CD``````
and the score are 2-1-1 = 0, 2-1 = 1, and -1 respectively.

But uDebug gives:

Code: Select all

``````2
2
0``````
Did I misunderstand the problem? What does it mean by "we do not penalize for misalignment at the left"?
Suhendry Effendy

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 1182 - Sequence Alignment

You do not have to insert gaps, a mismatched char gives a score of 0.
So the best alignments for all of those 3 cases have no gaps, the output on uDebug is correct. 2 points for the matched S's, 0 points for the other chars.
SA
SB
AS
BS
AB
CD
Check input and AC output for thousands of problems on uDebug!

suhendry
New poster
Posts: 14
Joined: Sat Aug 31, 2002 6:55 am

### Re: 1182 - Sequence Alignment

brianfry713 wrote:You do not have to insert gaps, a mismatched char gives a score of 0.
Ah! You're right; it got accepted.

The problem statement didn't mention anything about that, and the sample did not help either

Anyway, thanks!
Suhendry Effendy