## 11828 - Palindrome Again

Moderator: Board moderators

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

### 11828 - Palindrome Again

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

### Re: 11828 - Palindrome Again

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

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

### Re: 11828 - Palindrome Again

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
4 3

150 156

aaaaaaaaaaaaabbbbbbbbbbdfsdjhdfsdhfkhsdkhfshdfhedhfksjdhfkjhsdkfhshdkjfhskdjhfsdhfkjsdhkjfhsdkjfhsdkjhfskdhfkjsdhfkjsdhhkdhsfhsdkfhskdhfkshdsdhfdhfjff``````
Output:

Code: Select all

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

Mak
Help me PLZ!!

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

### Re: 11828 - Palindrome Again

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 [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 );
//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

### Re: 11828 - Palindrome Again

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

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 [MM]
``````
>>>>>>>>> A2
Beliefs are not facts, believe what you need to believe;)