1182 - Sequence Alignment

[kimbbakar]

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]

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?

[suhendry]

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"?

[brianfry713]

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

[suhendry]

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!