1182 - Sequence Alignment

All about problems in Volume 11. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

Re: 1182 - Sequence Alignment

Post by kimbbakar » Sat Jan 03, 2015 7:38 pm

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



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

Re: 1182 - Sequence Alignment

Post by uDebug » Mon Jan 05, 2015 3:35 pm

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!

Find us on Facebook. Follow us on Twitter.

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

Re: 1182 - Sequence Alignment

Post by suhendry » Sat Feb 21, 2015 9:17 pm

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

Post by brianfry713 » Tue Feb 24, 2015 12:46 am

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

Post by suhendry » Wed Feb 25, 2015 5:08 pm

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

Post Reply

Return to “Volume 11 (1100-1199)”