Lucky Palin

Problem code: LUCKPAL

All submissions for this problem are available.

Chef Palin, as his name suggests, is always very interested in palindromic strings. Recently, he made a pretty interesting discovery on palindromes and that made him feel really Lucky. He came across something known as Lucky Palindromes. He defines a string as being a lucky palindrome if it is a palindrome containing the string "lucky" as a substring. As always, now he wants to turn every string he comes across into a lucky palindrome. Being a chef, he is a man of patience and creativity, so he knows the operation of replacing any character of the string with any other character very well and he can perform this action infinitely many times. He wants you to write a program that can help him convert a given string to a lucky palindrome using the minimum number of operations and if several such lucky palindromes are possible, then output the lexicographically smallest one.

Input

The first line contains a single integer T <= 100 the number of testcases. The following T lines each contain a string of length <= 1000 and only containing characters 'a'-'z'.

Output

For each line of testcase, your program should output on a single line, the required lucky palindrome along with the minimum number of operations, both separated by a single space. If there is no lucky palindrome possible, then just output "unlucky" in a single line.

Example:

Input

3
laubcdkey
luckycodechef
aaaaaaaa

Output

luckykcul 8
luckycocykcul 6
unlucky
Author: ankul_iiita
Date Added: 27-08-2011
Time Limit: 1 sec
Source Limit: 50000 Bytes
Languages: ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.0.0-8, CPP 4.3.2, CS2, D, ERL, F#, FORT, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC


Comments

Mr. admin, the palindrome

jaysdk @ 1 Oct 2011 03:35 PM
Mr. admin, the palindrome generated for the word "luckycodechef" is "luckycocykcul". But a lexicographically smaller word can be "luckycecykcul" and the smallest will be "luckyccykcul". I didn't understood how you got the answer... Please elaborate.

^above : "luckycodechef" to

ankul_adm @ 1 Oct 2011 05:00 PM
^above : "luckycodechef" to "luckycocykcul" conversion requires 6 replacements while conversion to "luckycecykcul" requires 7 replacement operations. You need to first find the conversion with minimum replacements required and if multiple answers exist with minimum replacements, then find the lexicographically smallest one. Also, here conversion to "luckyccykcul" is not possible as length of the string cannot be modified from 13 to 12. Please read the question again carefully.

@admin: thanks a lot.

jaysdk @ 1 Oct 2011 05:17 PM
@admin: thanks a lot.

Is it important how many

aircube @ 1 Oct 2011 06:03 PM
Is it important how many times "lucky" is a substring of palindrome?

@aircube, no @problem setter

pr0ton @ 1 Oct 2011 07:03 PM
@aircube, no @problem setter / tester... check the input files and read the input description carefully, there seems to be an inconsistency with input (i have got accepted,so i know)

@pr0ton, thanks.

aircube @ 1 Oct 2011 07:14 PM
@pr0ton, thanks.

can i replace character of

piyushurpade @ 1 Oct 2011 07:31 PM
can i replace character of string by any letter? or only by the letters in string?

it seems that the judge input

chhung6 @ 1 Oct 2011 08:58 PM
it seems that the judge input contains space character...?

judge data contains space

shiplu @ 1 Oct 2011 10:40 PM
judge data contains space character, so now what to do? handle it or not? will the spaces will be part of the answer or not?

i just wanna say that, C++ /

chhung6 @ 2 Oct 2011 12:07 AM
i just wanna say that, C++ / C coders should use scanf() instead of gets() to read input btw, there should be no empty string in the test data too.

@admin - Please confirm

sanchit_h @ 2 Oct 2011 10:32 AM
@admin - Please confirm whether test cases have been corrected, it's really frustrating when you don't know what's wrong in the (maybe correct) solution.

Did anyone else think this

tl268 @ 2 Oct 2011 12:19 PM
Did anyone else think this question was about Saran Palin when they saw the title? lol

@admin Can you please tell

rosyish @ 2 Oct 2011 03:16 PM
@admin Can you please tell whether test sets are free of inconsistencies now ?

what are the problems with

aseem_pandey @ 2 Oct 2011 09:16 PM
what are the problems with test data exactly?? Those who have got accepted please let us know how to avoid them.

the smallest lexicographic

taneja_stud @ 3 Oct 2011 12:55 AM
the smallest lexicographic palindrome be printed

@people - Test cases are

sanchit_h @ 3 Oct 2011 10:14 AM
@people - Test cases are fine.

I have tried for many test

efficience @ 3 Oct 2011 10:21 AM
I have tried for many test cases , even the overlapping ("lucky") words. My code is giving correct output for all test cases.I dont understand why my code is not being accepted (wrong output). for :- input string :- xlutckyzcvlluckblbutkw output is :- wlutckykculluckykctulw 9 which is minimum changes..... Can admin provide some more test cases so that I can check my code ? If asked even I can explain the logic.

@efficience the answer may be

dudechandan123 @ 3 Oct 2011 11:58 AM
@efficience the answer may be wltuckykculluckykcutlw 9

@dudechandan123 , thanx a lot

efficience @ 3 Oct 2011 01:12 PM
@dudechandan123 , thanx a lot . I was looking @ the code & it is giving output as => wkttbkykculluckykbttkw 9. Which is minimum. Is their any complex test case that I need to consider... I have work on about 10-15 test cases , still the same problem.

@dedechandan123 , thanx

efficience @ 3 Oct 2011 01:16 PM
@dedechandan123 , thanx brother . You helped me find a bug in the code .. It has been accepted .. Thanx a lot

Can admin provide any complex

sandygupta @ 3 Oct 2011 03:14 PM
Can admin provide any complex test case , please !!!

what does replacement of

prakharcipher @ 3 Oct 2011 04:09 PM
what does replacement of characters meaqn here???

is it mecessary that every

prakharcipher @ 3 Oct 2011 04:12 PM
is it mecessary that every output have ''lucky'' at the starting and ''ykcul'' at the end

input is correct... use

dudechandan123 @ 3 Oct 2011 05:54 PM
input is correct... use scanf..

Limits are too easy. My brute

Kokos @ 4 Oct 2011 01:55 AM
Limits are too easy. My brute got AC.

Admin, moderate comments

gunjanbansal @ 5 Oct 2011 12:58 PM
Admin, moderate comments (kokos)

I am using "cin" with

mkagenius @ 5 Oct 2011 03:41 PM
I am using "cin" with "string" in c++.No problem with that , right ?

can anyone provide some

qwrt4181 @ 5 Oct 2011 09:34 PM
can anyone provide some testcases...

Can anyone please explain me

perlsux @ 5 Oct 2011 11:20 PM
Can anyone please explain me why for input xlutckyzcvlluckblbutkw the correct output is wltuckykculluckykcutlw and not wkttbkykculluckykbttkw? For the second position, k < l so it should start with wk and end with kw (not wl and lw). also, t

nevermind, the

perlsux @ 6 Oct 2011 12:54 AM
nevermind, the wkttbkykculluckykbttkw is correct.

what should be the output for

sidhantgoyal @ 6 Oct 2011 10:38 AM
what should be the output for a string like "blucky"???please tell!!

Okay, No problem with

mkagenius @ 6 Oct 2011 01:06 PM
Okay, No problem with "cout/cin and string in c++". So, don't worry about whitespaces. :D

replacing any character of

amriteshanand @ 6 Oct 2011 02:42 PM
replacing any character of the string with any other character does it mean the other chars should be in the string or can be anything from a to z.please reply i am getting wrong answer but can't point out the fault.

@amriteshanand replace with

gunjanbansal @ 6 Oct 2011 03:53 PM
@amriteshanand replace with any char from a-z, resulting string must be palindrome with minimum changes required and contain lucky as substring.

how is luckycoykcul a

karan093 @ 6 Oct 2011 05:31 PM
how is luckycoykcul a palindrome to start with.. should not the output be a palindrome with lucky as substring?

sorry.. My BAD!

karan093 @ 6 Oct 2011 05:32 PM
sorry.. My BAD!

can any one provide a complex

allada @ 6 Oct 2011 08:15 PM
can any one provide a complex test case!! donno y im getting wrong ans

what will be the output for

amriteshanand @ 6 Oct 2011 08:58 PM
what will be the output for uuuluckyykcul : luckyckcykcul 5 replacing chars at 1,3,4,5,8 or just swapping 1,2,3 to middle positions at luckyuuuykcul.is swapping considered as 1 valid operation.

@amriteshanand ykculckclucky

allada @ 6 Oct 2011 09:29 PM
@amriteshanand ykculckclucky 10

hey sorry ans will be

allada @ 6 Oct 2011 09:44 PM
hey sorry ans will be luckyckcykcul

@admin can u please check my

allada @ 6 Oct 2011 11:10 PM
@admin can u please check my solution. i tried many test cases, it was giving right ans... but when i submit it was showing wrong ans.... could not understand why !!! http://www.codechef.com/viewsolution/689825

@amriteshanand I am getting

phantom11 @ 6 Oct 2011 11:54 PM
@amriteshanand I am getting luckyckcykcul 5

@allada i am not able to view

mkagenius @ 7 Oct 2011 12:11 AM
@allada i am not able to view your link, have you locked it with some wierd passwrd ?

@mkagenius: hehe.. during the

allada @ 7 Oct 2011 12:26 AM
@mkagenius: hehe.. during the contest, the solutions wont be visible to others

@mkagenius: can u provide any

allada @ 7 Oct 2011 12:41 AM
@mkagenius: can u provide any corner test case ?? thanku

All I can say is, try to

mkagenius @ 7 Oct 2011 02:01 AM
All I can say is, try to write a clean code. Earlier I also got WAs. But den I decided to write a clean-n-beautiful code , I got AC the first time. :D before printing any answer make sure it contains "lucky" and it is palindrome

@mkgenius I am also getting

cricketer @ 7 Oct 2011 03:18 AM
@mkgenius I am also getting WA. I don't know why even if I hav done it by brute.....At last i hav also checked for palindrome as well as it contains lucky.plz help me out....Can u plz tell me ur mail id ..............I want u to see my code.......I would be very helpful 2 u.....

@mkagenius : thanx very much

allada @ 7 Oct 2011 08:00 AM
@mkagenius : thanx very much dude... u have really helped me... now it got accepted.... once again thanku :)

what should be the output for

ascend @ 7 Oct 2011 11:41 AM
what should be the output for "luckyaa" ?

@ascend: unlucky

allada @ 7 Oct 2011 11:56 AM
@ascend: unlucky

Can someone provide more test

siddharth_l @ 9 Oct 2011 11:31 PM
Can someone provide more test cases??

Hi, are there any problems in

mohan89 @ 10 Oct 2011 11:16 PM
Hi, are there any problems in cout<

I am sorry, cout"str""endl"

mohan89 @ 10 Oct 2011 11:16 PM
I am sorry, cout"str""endl"

Can you please check

mohan89 @ 10 Oct 2011 11:20 PM
Can you please check http://www.codechef.com/viewsolution/698167.., New line at the end of cases.. is it allowed?

Hi, can anyone listdown any

mohan89 @ 10 Oct 2011 11:46 PM
Hi, can anyone listdown any of the corner things in c++, like newline, reading, like the same. My code is giving correct answer for all the test cases, but it is WA.

Hiee admin .. Check out my

ashcoder @ 11 Oct 2011 10:06 AM
Hiee admin .. Check out my solution http://www.codechef.com/viewsolution/699264 It's giving output as per your questions .. but still judging WRONG ANSWER at here could u please refer my code

SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:

CodeChef is a global programming communityCodeChef hosts online programming competitions