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

×

LUCKPAL - Editorial

1
2

PROBLEM LINKS

Practice
Contest

DIFFICULTY

EASY

EXPLANATION

The problem is solvable by Greedy Algorithm. For each i >= 0 and j >=0, i < j such that string[i….j] = “lucky”, find the lexicographically smallest palindrome that can be constructed in a greedy manner using minimum number of replacement operations. So the problem can be divided into two tasks:

  1. Place the substring “lucky” at all possible locations in the string.
  2. For each such location of substring “lucky”, find the lexicographically smallest palindrome using minimum number of replacement operations while maintaining the substring “lucky”.

Let’s define each string obtained in task 1 as: “xxxxxluckyxxxxx” with str[a…b] = “lucky”. Now, second task can be achieved by iterating over the string starting with i = 0 and j = n-1 (n = string length), until i <= j. At each iteration, we have the following possibilities:

  1. str[i] = str[j] , requires no replacement operation
  2. str[i] != str[j] , either requires 1 replacement or no solution is possible
    a. i < a and j > b, requires 1 replacement
    i. if str[i] < str[j], str[j] = str[i]
    ii. str[i] > str[j], str[i] = str[j]
    b. a >= i and i <= b and j > b, requires 1 replacement
    i. str[j] = str[i], cannot change str[i] as it is part of “lucky”
    c. i < a and a >= j and j <= b, requires 1 replacement
    i. str[i] = str[j], cannot change str[j] as it is part of “lucky”
    d. a >= i,j <= b, cannot be converted to palindrome containing “lucky”
    Final answer is the string obtained after task 2 with minimum number of replacement operations and lexicographically smallest one. If no such string exists, then “unlucky”.

SETTER'S SOLUTION

Can be found here.

TESTER'S SOLUTION

Can be found here.

This question is marked "community wiki".

asked 05 Dec '12, 12:46

admin's gravatar image

0★admin ♦♦
19.8k350498541
accept rate: 36%

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:

×15,683
×3,766
×6
×4

question asked: 05 Dec '12, 12:46

question was seen: 5,115 times

last updated: 05 Dec '12, 12:46