10453 - Make Palindrome

[Larry]

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]

oh! i know this but i got wa but using lcs.
plz describe your method in ststements.
plz.
Anupam

[Noim]

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.

[anupam]

oh! very good idea, trying.
thanks.

[nayaya]

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]

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.

[Algoritmo]

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
abdccbad = reverse of input
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
dabdccdbad

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

[Noim]

you can check for following input:

aaaab
abbbb
ababab
aaaaa
abbcdba

[Algoritmo]

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
1 dabcdcbad
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
1 dabcdcbad
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

[Noim]

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.

[Algoritmo]

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).

[Noim]

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).

[cytmike]

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]

Hi Murilo

Thanx for your comment about the last line of input.
I finally got AC. I was wondering what was wrong with my code.
But now I know what was wrong.

[Abednego]

I did exactly what Nak described, but I'm getting WA. Are there spaces at the beginning or end of the line that we should ignore? Are there empty lines that we should ignore? Can there be several inputs on the same line?