## 10453 - Make Palindrome

Moderator: Board moderators

Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:
Gah! My trace function was wrong. Got it now.
If only I had as much free time as I did in college...

kbr_iut
Experienced poster
Posts: 103
Joined: Tue Mar 25, 2008 11:00 pm
Contact:

### Re: 10453 - Make Palindrome

To solve this problem I got help from topcoder explanation...I tried it in two approach.both of them are giving TLE

1) DP approach.

Code: Select all

``````#include<iostream>
#include<string>
using namespace std;

string MakePalindrom(string base){
string best[1002][1002];
int len=base.length();
if(len<=1)return base;
for(int i=0;i<len;i++)best[i][1]=base[i];
for(int sublen=2;sublen<=len;sublen++){
for(int i=0;i<=len-sublen;i++){
string subset(base,i,sublen);
char first=subset[0];
char last=subset[sublen-1];
if(first==last)best[i][sublen]=first+best[i+1][sublen-2]+last;
else{
string s1=first+best[i+1][sublen-1]+first;
string s2=last+best[i][sublen-1]+last;
string& res=best[i][sublen];
if(s1.length()<s2.length())res=s1;
else if(s2.length()<s1.length())res=s2;
else if(s1<s2)res=s1;
else res=s2;
}
}
}
return best[0][len];
}
int main(){
string s,res;
#ifndef ONLINE_JUDGE
freopen("1.txt","r",stdin);
#endif
while(cin>>s){
res=MakePalindrom(s);
//cout<<res.length()-s.length()<<" "<<res<<endl;
printf("%d %s\n",res.length()-s.length(),res.c_str());
}
return 0;
}``````

2.normal recursive approach with memorization.

Code: Select all

``````#include<iostream>
#include<string>
#include<map>
using namespace std;
map<string,string>mps;
string maxi(string a,string b){
if(a.length()<b.length())return a;
else if(b.length()<a.length())return b;
else if(a<b)return a;
else return b;
}
string MakePalindrom(string s){
int len=s.length();
if(len<=1)return s;
if(mps[s]>=" ")return mps[s];
char first=s[0];
char last=s[len-1];
string equ(s,1,len-2);
string fir(s,1,len-1);
string lst(s,0,len-1);
string res;
if(first==last)res=first+MakePalindrom(equ)+last;
else res=maxi( first+MakePalindrom(fir)+first,last+MakePalindrom(lst)+last);
mps[s]=res;
return res;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("1.txt","r",stdin);
#endif
string s,res;
while(cin>>s){
res=MakePalindrom(s);
cout<<res.length()-s.length()<<" "<<res<<endl;
}
return 0;
}``````
can anyone help me out...thanx in advance.

At last I found my error. I think STL is taking too much time. I tried with normal char array approach . and got AC.I am not deleting this code because of those will be stuck trying with STL.
It is tough to become a good programmer.
It is more tough to become a good person.
I am trying both...............................

bizman
New poster
Posts: 1
Joined: Tue Jun 16, 2009 11:04 pm

### Re: 10453 - Make Palindrome

Hi, All,

I need some help with this problem. I wrote my program with recursion+memo. It is a simple program, and it works for all the test cases I can find. I also wrote a small program to generate random input
string from 0 to 1000 and compared the results with the results in uva toolkits. But I still cannot find why it is always a WA.

Anyone can have a look at it? Thank you so much!

Code: Select all

``````#include <iostream>
#include <string>

using namespace std;

#define N 1024

int memo[N][N];

int min(int a, int b)
{
return (a < b)? a : b;
}

int opt(char * s, int b, int e)
{
if (b >= e) {
memo[b][e] = 0;
return 0;
}

if (memo[b][e] != -1)
return memo[b][e];

if (s[b] == s[e]) {
memo[b][e] = opt(s, b+1, e-1);
return memo[b][e];
}

memo[b][e] = min(opt(s, b, e-1), opt(s, b+1, e)) + 1;
return memo[b][e];
}

string print(char * s, int b, int e)
{
string t = "";

if (b > e)
return t;

if (b == e)
return t + s[b];

if (s[b] == s[e])
return s[b] + print(s, b+1, e-1) + s[e];

if (memo[b][e-1] < memo[b+1][e])
return s[e] + print(s, b, e-1) + s[e];
else
return s[b] + print(s, b+1, e) + s[b];

}

int main()
{
char word[N];
int len;

while(fgets(word, N, stdin)) {

//memset(memo, 0xff, N*N*4);
for (int i = 0; i < N; ++i)
for (int j = 0; j < N; ++j)
memo[i][j] = -1;

len = strlen(word)-1;

cout<<opt(word, 0, len-1)<<" ";
cout<<print(word, 0, len-1)<<endl;

}

return 0;
}

``````

pdwd
New poster
Posts: 19
Joined: Sat May 15, 2010 4:35 pm

### Re: 10453 - Make Palindrome

To avoid tle, just count the dp int values for minimal number of moves. Then write recursive reconstruction function, which will use these values to construct palindrom, don't do something like string t[1000][1000] and constract the palindrom for each substring of the word.

DD
Experienced poster
Posts: 145
Joined: Thu Aug 14, 2003 8:42 am
Location: Mountain View, California
Contact:

### Re: 10453 - Make Palindrome

I think the output palindrome is tricky , it took me a while to figure it out to backtrace it from the DP table.
Have you ever...
• Wanted to work at best companies?
• Struggled with interview problems that could be solved in 15 minutes?
• Wished you could study real-world problems?
If so, you need to read Elements of Programming Interviews.

devilL
New poster
Posts: 1
Joined: Sun Dec 18, 2011 4:46 pm

### Re: 10453 - Make Palindrome

@Nak

can u mail me ur code..........i am trying it for a long time can't get AC.......plz mail me....

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 10453 - Make Palindrome

devilL, try generating some test cases at http://www.uvatoolkit.com/problemssolve.php
Check input and AC output for thousands of problems on uDebug!

jddantes
Learning poster
Posts: 73
Joined: Sat Mar 08, 2014 8:55 am

### Re: 10453 - Make Palindrome

AC
(Reading per line with fgets resulted to WA)
Last edited by jddantes on Thu Feb 12, 2015 5:04 am, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 10453 - Make Palindrome

If you switch to scanf("%s"), you'll get AC.
Check input and AC output for thousands of problems on uDebug!