10453 - Make Palindrome
Moderator: Board moderators
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.
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....
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
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
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.
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....
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
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
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
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
Sample Input/output
Noim, did you get AC ?
Here is mine + your inputs:
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![:x](./images/smilies/icon_mad.gif)
Here is mine + your inputs:
And the output my program (version 5) gives: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 4) 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
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).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
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
![:x](./images/smilies/icon_mad.gif)
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, did you get AC ?
![:wink:](./images/smilies/icon_wink.gif)
look at my input statement of my ac program:
what do this prove?scanf("%s", &input[1]);
no need to see for a blank line.
i don't think there is any meaningless input.
that's a good idea.Do you think I should make a program that checks if the input string is always present in the palindromes?
__nOi.m....
Noim, I was not sure if you had got accepted because of this sentence:
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 ![:)](./images/smilies/icon_smile.gif)
My first program, which uses simillar/same idea as yours, still gets WA. Only the simpler version worked (with Nak's recursive definition).
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).first i have determined the lcs string for the input string and the reverse of input string
This does not prove nothing, since both of our input methods work equal if all strings have a '\n' after them.what do this prove?scanf("%s", &input[1]);
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 !
![:)](./images/smilies/icon_smile.gif)
![:)](./images/smilies/icon_smile.gif)
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
the lcs of abcdcbad and it's reverse string is NOT abcd. it is abcdcba and my answer is right for this input.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,
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....
-
- 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]
![:cry:](./images/smilies/icon_cry.gif)
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]