You are not logged in. Please login at www.codechef.com to post your questions!

×

Help! Codeforces: Palindromic Transformation but with a twist

This is the original question: click here
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?

asked 30 May '17, 20:20

rishi_07's gravatar image

5★rishi_07
31617
accept rate: 20%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×2,718
×2,172
×682
×311

question asked: 30 May '17, 20:20

question was seen: 496 times

last updated: 30 May '17, 20:20