[Help] A small variation in the question Palindromic Transformation

Revision en1, by rishi_07, 2017-05-30 20:29:02

This is the original question: http://codeforces.net/problemset/problem/486/C

This question uses four keys (up, down, left and right) and can be easily solved by greedy approach in linear time. My question is what if there were only three keys (left, right and up) then how to solve it? Previously, when we found a mismatch between two positions like in (i)th position we have 'b' and in (n-i)th position we have 'c', both of them could be made same using just 1 operation irrespective of the index ((i)th or (n-i)th) where we are performing the operation. But now, 'b' to 'c' will take only 1 operation but 'c' to 'b' will take 25 operations. I think now the question can be solved using DP. But, I am unable to formulate it. Any idea?

Tags doubt, round #277, variation, dynamic programming

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English rishi_07 2017-05-30 20:29:02 808 Initial revision (published)