jugal_sahu's blog

Palindrome 2000 (IOIPALIN) SPOJ
By jugal_sahu, 9 years ago, In English

I am unable to find where my code is going wrong.First i calculated LCS of string and it's reverse than printed ans=length of string — LCS.

Can anyone tell me where i am wrong . my code is : here

Tags dp, lcs
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
9 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I think that you should initialize dp with zeroes and then take care of this:

else cur[j]=0;

If the last two elements are different, it doesn't mean that the length of the LCS is 0.

I'm not sure if I understood your code right. Why don't you just take the reversed string and use 2D DP or just DP[from][to] without computing the LCS:

Let dp[i][j] gives us the answer for the sequence S[i],S[i+1],...,S[j].

Then you have two cases:

If S[i]==S[j], then dp[i][j]=dp[i+1][j-1].

If S[i]!=S[j], then dp[i][j]=1+min(dp[i+1][j],dp[i][j-1]).

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Your answer is correct i had implemented that but it gives tle because of space complexity. I searched for solution and got an answer that space optimization is required for this problem.That is why i was trying to write code like that but gave wrong answer. Can anyone help??? my code is :Your text to link here...

    → Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

I just got accepted.

My first idea was the one that I shared with you yesterday — dp[from][to] but it received TLE:

ioipalin1

My second idea was actually the same but my dp looks like dp[i][from], not dp[from][to] because this can be easily space optimized. However, this second idea got AC(I don't know why):

ioipalin2

But I made an optimization and it got AC with linear space:

ioipalin3

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you please explain how you have optimized to get AC.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I am not getting how to optimize space using dp[from][to]......

      → Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

You asked me how to optimize (from,to) with PM. I am using my phone now and I can't write a PM. Those who have tried will know. So my answer goes here:

Actually I don't even know if it is possible to optimize it and that is why I transformed dp[from][to] to dp[length][from] where length=to-from. Then to calculate the state (length,from) we need only the states with length-1 and length-2. Check my second and third posted codes to understand it completely.

→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Optimise space. You can see that in LCS :

dp[i][j] = max(dp[i-1][j],dp[i][j-1]) for non equal a[i] and b[j]

dp[i][j] = dp[i-1][j-1] for equal a[i] and b[j]

Now you can observe that for a state(i,j) you need information of only two rows, i and i-1. This can help you reduce your state drastically. Create an array of 2 * N instead of N * N.

→ Reply