11828 - Palindrome Again

All about problems in Volume 118. 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
Angeh
Experienced poster
Posts: 108
Joined: Sat Aug 08, 2009 2:53 pm

11828 - Palindrome Again

Post by Angeh » Thu Sep 30, 2010 3:38 am

HI all ...
Any Hints How to avoid TLE ... !!!!?
>>>>>>>>> A2
Beliefs are not facts, believe what you need to believe;)

mak(cse_DU)
Learning poster
Posts: 72
Joined: Tue May 30, 2006 5:57 pm
Location: bangladesh

Re: 11828 - Palindrome Again

Post by mak(cse_DU) » Mon Oct 18, 2010 7:19 pm

My solution 500*1000 for each case.
But still TLE.
No Of test case 5000. (huge).
Is it needed to solve in linear time?
Mak
Help me PLZ!!

Leonid
Experienced poster
Posts: 146
Joined: Thu Dec 22, 2005 5:50 pm
Contact:

Re: 11828 - Palindrome Again

Post by Leonid » Sat Oct 23, 2010 12:07 am

The problem can be solved using DP with precalculation. I solved it with O(N*K + T*(N + K)) algorithm. Think about what can be precalculated in order to give the answer for a test case in O(K).

mak(cse_DU)
Learning poster
Posts: 72
Joined: Tue May 30, 2006 5:57 pm
Location: bangladesh

Re: 11828 - Palindrome Again

Post by mak(cse_DU) » Mon Oct 25, 2010 3:38 pm

I solved it with O(Testcase*K+N*K).

I got idea from my Academic elder brother (Jane Alam Jan). "Thanks Jan vai"

let n be length, A[0 to (n-1)]

P= number of characters where a = a[n-i-1];
Q= number of characters where a != a[n-i-1];

Then Independently calculate DP(P,K); and DP2(Q,K);

Hope you have got the Idea.

Same input:

Code: Select all

5

3 2
kxk

3 3

kxk

4 1
addc
4 3

addc

150 156

aaaaaaaaaaaaabbbbbbbbbbdfsdjhdfsdhfkhsdkhfshdfhedhfksjdhfkjhsdkfhshdkjfhskdjhfsdhfkjsdhkjfhsdkjfhsdkjhfskdhfkjsdhfkjsdhhkdhsfhsdkfhskdhfkshdsdhfdhfjff
Output:

Code: Select all

Case 1: 51
Case 2: 676
Case 3: 2
Case 4: 76
Case 5: 41189376

***Note: last sample input is wrong. You can assume "addc" instead of "Addc"
Mak
Help me PLZ!!

Angeh
Experienced poster
Posts: 108
Joined: Sat Aug 08, 2009 2:53 pm

Re: 11828 - Palindrome Again

Post by Angeh » Tue Oct 26, 2010 3:42 pm

Thanks Mak For Your help ...
I make The DP1 and DP2 table ...
Then For each K sum up DP1 [k][MM] + =DP1 [k-1][MM] +DP1 [k-2][MM]....DP1 [0][MM]
Then For each case the result is
MM = mismatch ... M= match
for(i=0...i<=k , j=k-i ) result+=DP1[MM] + DP2[j][M] .....
am i Right ,....??

and This is How i calculate the DP1 and DP2....
I think This Calculation is Wrong here ... maybe the Base Cases are Wrong ...
P2[ t ] means 2^t ... P24[t] means 24^t ... Choose (n,a) is n!/(a!*(n-a)!) .....

Code: Select all

    //Fill DP1 ... number of Missmatch ... 
    FOR(k,1010)for(int mm=0;mm<1010;mm+=2){
        if(k>mm)continue;
        int MM=mm/2;
        if(k<MM){ DP1[k][mm]=0; break; }
        if(k==MM ){
            DP1[k][mm]=p2[MM];
        }else{
            int K=k-MM;
            DP1[k][mm]= Choose(MM,K)*p24[K]*p2[MM-K];
        }
        DP1[k][mm]%=Mode;//*/
    }
    //printf("%lld\n\n",DP1[0][2] );
    //Fill DP2 ... number of matchings ... 
    FOR(k,1010)for(int m=0;m<1010;++m){
        if(k>m)continue;
        if(k==0){DP2[k][m]=1;continue;}
        int M=m/2;
        if(m%2==1 && k%2==1 )DP2[k][m]=25;
        if(m%2==0 && k%2==1 ){DP2[k][m]=0;continue;}
        int K=k/2;
        if(DP2[k][m]==0 )DP2[k][m]=Choose(M,K)*p25[K];        
        else DP2[k][m]*=Choose(M,K)*p25[K];
        DP2[k][m]%=Mode;
    }
>>>>>>>>> A2
Beliefs are not facts, believe what you need to believe;)

mak(cse_DU)
Learning poster
Posts: 72
Joined: Tue May 30, 2006 5:57 pm
Location: bangladesh

Re: 11828 - Palindrome Again

Post by mak(cse_DU) » Tue Oct 26, 2010 6:20 pm

I am not able to figure it out your DP.

Code: Select all

for(i=0...i<=k , j=k-i ) result+=DP1[i][MM] + DP2[j][M] ;
you can simply discover that result must be
result+=DP1[MM] * DP2[j][M] ;

At first define DP1 and DP2 carefully.
Mak
Help me PLZ!!

Angeh
Experienced poster
Posts: 108
Joined: Sat Aug 08, 2009 2:53 pm

Re: 11828 - Palindrome Again

Post by Angeh » Tue Oct 26, 2010 11:07 pm

Oh sorry i meant
result+=DP1[MM] * DP2[j][M] ;
i think my problem is in Defining The DP1 and DP2 ...
The Code Below ...
Would you please give some hint where is my fault ...

Code: Select all

//Fill DP1 ...mm number of Missmatch ...
    FOR(k,1010)for(int mm=0;mm<1010;mm+=2){
        if(k>mm)continue;
        int MM=mm/2;
        if(k<MM){ DP1[k][mm]=0; break; }
        if(k==MM ){
            DP1[k][mm]=p2[MM];
        }else{
            int K=k-MM;
            DP1[k][mm]= Choose(MM,K)*p24[K]*p2[MM-K];
        }
        DP1[k][mm]%=Mode;//*/
    }


    //Fill DP2 ... m number of matchings ...
    FOR(k,1010)for(int m=0;m<1010;++m){
        if(k>m)continue;
        if(k==0){DP2[k][m]=1;continue;}
        int M=m/2;
        if(m%2==1 && k%2==1 )DP2[k][m]=25;
        if(m%2==0 && k%2==1 ){DP2[k][m]=0;continue;}
        int K=k/2;
        if(DP2[k][m]==0 )DP2[k][m]=Choose(M,K)*p25[K];       
        else DP2[k][m]*=Choose(M,K)*p25[K];
        DP2[k][m]%=Mode;
    }

and at last 
Then For each K sum up DP1 [k][MM] + =DP1 [k-1][MM] +DP1 [k-2][MM]....DP1 [0][MM]
>>>>>>>>> A2
Beliefs are not facts, believe what you need to believe;)

Post Reply

Return to “Volume 118 (11800-11899)”