10453 - Make Palindrome

All about problems in Volume 104. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

User avatar
Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:

Post by Abednego » Sat Jul 02, 2005 11:36 pm

Gah! My trace function was wrong. Got it now.
If only I had as much free time as I did in college...

User avatar
kbr_iut
Experienced poster
Posts: 103
Joined: Tue Mar 25, 2008 11:00 pm
Location: IUT-OIC, DHAKA, BANGLADESH
Contact:

Re: 10453 - Make Palindrome

Post by kbr_iut » Sat May 23, 2009 10:11 pm

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

Post by bizman » Fri Aug 28, 2009 7:50 pm

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

Post by pdwd » Tue Jul 27, 2010 12:23 am

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

Post by DD » Sun Mar 27, 2011 2:55 am

I think the output palindrome is tricky :evil: , 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

Post by devilL » Sun Dec 18, 2011 5:03 pm

@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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10453 - Make Palindrome

Post by brianfry713 » Wed Jan 11, 2012 2:01 am

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

Post by jddantes » Wed Feb 11, 2015 4:43 pm

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

Post by brianfry713 » Wed Feb 11, 2015 10:13 pm

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

Post Reply

Return to “Volume 104 (10400-10499)”