[Help] A small variation in the question Palindromic Transformation

Правка en1, от 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?

Теги doubt, round #277, variation, dynamic programming

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский rishi_07 2017-05-30 20:29:02 808 Initial revision (published)