10453 - Make Palindrome

[Abednego]

Gah! My trace function was wrong. Got it now.

[kbr_iut]

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.

[bizman]

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]

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]

I think the output palindrome is tricky , it took me a while to figure it out to backtrace it from the DP table.

[devilL]

@Nak


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

mail address:miska.shaytan@yahoo.com

@ everyone................please help me.....anyone can send me ur code....

[brianfry713]

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