## 10453 - Make Palindrome

Moderator: Board moderators

Gah! My trace function was wrong. Got it now.
Let's hope Yury doesn't notice that I'm solving problems again.

Abednego
A great helper

Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA

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

kbr_iut
Experienced poster

Posts: 103
Joined: Tue Mar 25, 2008 11:00 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 1024int 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;}`
bizman
New poster

Posts: 1
Joined: Tue Jun 16, 2009 11:04 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.
pdwd
New poster

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

### 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.
DD
Experienced poster

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

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

devilL
New poster

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

### Re: 10453 - Make Palindrome

devilL, try generating some test cases at http://www.uvatoolkit.com/problemssolve.php
brianfry713
Guru

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

Previous