## 10453 - Make Palindrome

Moderator: Board moderators

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
It's basically a LCS problem (kind of) with a word and its reverse.. this should be enough hint for you to test things out.. keep asking if it doesn't though..

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:
oh! i know this but i got wa but using lcs.
plz describe your method in ststements.
plz.
Anupam
"Everything should be made simple, but not always simpler"

Noim
Learning poster
Posts: 88
Joined: Sun Oct 13, 2002 6:11 am
Anupam vai,

first i have determined the lcs string for the input string and the reverse of input string.

after that i add characters into the lcs string as necessary while comparing the input string .

i compared the input string with the lcs string both from beging and final position of the input string.
__nOi.m....

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:
oh! very good idea, trying.
thanks.
"Everything should be made simple, but not always simpler"

nayaya
New poster
Posts: 9
Joined: Sat Jun 08, 2002 1:57 pm
Noim,

I don't quite understand how your alg works. I used Dynamic Programming to calculate Min[j], which means the minimum number of chars to be added between position i and j in order to make this substring(between i and j) a palindrom. It has nothing to do with LCS. How do you think about it? I got WA but I don't know why

Noim
Learning poster
Posts: 88
Joined: Sun Oct 13, 2002 6:11 am
Nayaya,

i can't understand your algorithm of this problem.

But i can say what i did. i determine the LCS , so that the LCS string is the longest string for which no new chracter have to be added. So LCS string give me the largest sub-suquence Palindrome of the input string. And the remaining character of that string should be added only one time to make the input string palindrome. For me my algorithm is right to dertermine the output correctly. but if you think it would not work or have some bugs , will you please tell me the reason of telling so?

take care.
__nOi.m....

Algoritmo
New poster
Posts: 32
Joined: Wed Oct 15, 2003 12:10 pm
Contact:

### LCS reverse

I got all answers, exept AC.
My method is simillar to what Noim described, but I do not compare the full string against it's full reverse. Instead, I stop the comparison when the left-to-right sub-string 'hits' the right-to-left sub-string.

Example:
dabccdba = input
dabdccdbad = example of minimum sized palindrome
abcd = LCS between them input and it's reverse (wrong)
abc = LCS between left-to-right and right-to-left strings in input that do not meet with each other

From the correct LCS I create the palindrome. Example of process:
abc
dabc
dabdc

I added charters inside the LCS then repeated them in reverse order. Note that if any character is added after the end of the LCS, it can be kept as a center character, so it won't be repeated. When there is a center character, a odd sized palindrome is produced.

Any one sees any possible problem with my method ?

My solution is too complex, but at least I wrote a LCS algorithim that is faster and has lower memory requirements than the basic one.

The simplest way of solving this problem must be the one described in another thread:
http://online-judge.uva.es/board/viewto ... ight=10453
I solve 4 problems per day, then I expend 4 days stuck in a single problem. But I think I'm doing well... ID 37180

Noim
Learning poster
Posts: 88
Joined: Sun Oct 13, 2002 6:11 am
you can check for following input:
aaaab
abbbb
ababab
aaaaa
abbcdba
__nOi.m....

Algoritmo
New poster
Posts: 32
Joined: Wed Oct 15, 2003 12:10 pm
Contact:

### Sample Input/output

Noim, did you get AC ?
Here is mine + your inputs:
abcd
aaaa
abc
aab
abababaabababa
pqrsabcdpqrs
azbzczdzez
aaab
acaaaba
zzzaaazz
pooq
aoob
dabcdcba
z

aaaab
abbbb
ababab
aaaaa
abbcdba
And the output my program (version 5) gives:
3 dcbabcd
0 aaaa
2 cbabc
1 baab
0 abababaabababa
9 srqpdcbasrqrsabcdpqrs
5 zeazdbzczbdzaez
1 baaab
2 abcaaacba
1 zzzaaazzz
2 qpoopq
2 baooab
0 z
0
1 baaaab
1 abbbba
1 bababab
0 aaaaa
2 abdcbcdba
And the output my program (version 4) gives:
3 abcdcba
0 aaaa
2 abcba
1 baab
0 abababaabababa
9 pqrsabcdpqrqpdcbasrqp
5 azbezczdzczebza
1 baaab
2 acbaaabca
1 zzzaaazzz
2 pqooqp
2 abooba
0 z
0
1 baaaab
1 abbbba
1 abababa
0 aaaaa
2 abbcdcbba
I did not check them all one by one but the ones I checked seem correct. I also tested a input string with 1000 characters in length (I did not paste it here because it's too big).

The version 4 of my program is complete and uses an LCS algorithim plus a function that inserts characters in the LCS to make it a palindrome and a make it include all characters of the input string.
The version 5 uses a simplified recursive defiintion (in the other topic thread), aided with DP.
Both produce palindromes with the same length, and both seem correct but both get WA.

Maybe it's some critical case or some detail in input/output format that's tricking me. Do you think I should make a program that checks if the input string is always present in the palindromes?

My input format is: while (gets(Str) && !feof(stdin)) { ...
This will process any line, even if blank, since it's terminated with '\n'.

My output format is: printf("%d %s\n", strlen(Pal) - strlen(Str), Pal);

HELP
I solve 4 problems per day, then I expend 4 days stuck in a single problem. But I think I'm doing well... ID 37180

Noim
Learning poster
Posts: 88
Joined: Sun Oct 13, 2002 6:11 am
Noim, did you get AC ?
what do you think i give hints in this page, one year ago, without accepting the program??

look at my input statement of my ac program:
scanf("%s", &input[1]);
what do this prove?
no need to see for a blank line.
i don't think there is any meaningless input.
Do you think I should make a program that checks if the input string is always present in the palindromes?
that's a good idea.
__nOi.m....

Algoritmo
New poster
Posts: 32
Joined: Wed Oct 15, 2003 12:10 pm
Contact:
Noim, I was not sure if you had got accepted because of this sentence:
first i have determined the lcs string for the input string and the reverse of input string
This would give an LCS of abcd from abcdcbad, and the palindrome would start with 8 characters in length (abcddcba) and end up with 10 (dabcddcbad), but the smallest palindrome for this case has only 9 characters (dabcdcbad).
scanf("%s", &input[1]);
what do this prove?
This does not prove nothing, since both of our input methods work equal if all strings have a '\n' after them.

But tried your statement scanf("%s", &input[1]) as while (scanf("%s", Str) == 1) { and it is the same as while (gets(Str)) {. I finally got AC. Thanks ! Now that I got AC, it's proven that the last string doesn't have '\n' after it

My first program, which uses simillar/same idea as yours, still gets WA. Only the simpler version worked (with Nak's recursive definition).
I solve 4 problems per day, then I expend 4 days stuck in a single problem. But I think I'm doing well... ID 37180

Noim
Learning poster
Posts: 88
Joined: Sun Oct 13, 2002 6:11 am
Noim, I was not sure if you had got accepted because of this sentence:

Quote:
first i have determined the lcs string for the input string and the reverse of input string---------> this is my quotation.

This would give an LCS of abcd from abcdcbad,
the lcs of abcdcbad and it's reverse string is NOT abcd. it is abcdcba and my answer is right for this input.

using scanf("%s",..) means : if there is a input having blank line , you sould not have to consider that as a input. You consider that case as an independent input in your sample output.

anyway, i can't say you why your first algo is not ok. i think you consider half part of the input for finding lcs. see what will happen considering full input and it's full reverse? i think thus you can find Ac again in this method.
Considering half portion, there may have some error.( thoug i am not sure).
__nOi.m....

cytmike
Learning poster
Posts: 95
Joined: Mon Apr 26, 2004 1:23 pm
Location: Hong Kong and United States
Contact:
i did so but i got TLE
here is my code:
[cpp]
#include <iostream>
#include <string>
#include <cstring>
#include <hash_map.h>

using namespace std;

string sky(int,int);

hash_map <int,string> hp;
string p;

int main()
{
while (cin>>p)
{
hp.clear();
string h=sky(0,p.length()-1);
cout<<h.length()-p.length()<<' '<<h<<endl;
}
return 0;
}

string sky(int h,int y)
{

if (h==y)
return p.substr(h,1);
if (h>y)
return "";

int s=1000*h+y;
if (hp.count(s))
return hp[s];

if (p[h]==p[y])
return p[h]+sky(h+1,y-1)+p[y];
string l=p[y]+sky(h,y-1)+p[y],i=p[h]+sky(h+1,y)+p[h];

if (l.length()<i.length())
{
hp[s]=l;
return l;
}
else
{
hp[s]=i;
return i;
}
} [/cpp]

Arktus
New poster
Posts: 3
Joined: Mon Nov 22, 2004 5:26 pm
Location: Tehran
Hi Murilo