## 11753 - Creating Palindrome

Moderator: Board moderators

serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm

### 11753 - Creating Palindrome

All I can think of is a lazy DP: the minimum cost of making a palindrome of s[i:j] is stored in a map if the cost is <= K...
Of course this is still O(n^2), but I thought that K's being small will make up for this deficiency... Any ideas?
If there is ever a war between men and machines, it is easy to guess who will start it (c) Arthur Clarke

mintae71
New poster
Posts: 18
Joined: Tue Jan 19, 2010 10:50 am

### Re: 11753 - Creating Palindromes

I think you have to use LCS to solve this problem.

serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm

### Re: 11753 - Creating Palindromes

Reversing the sequence and finding the length of its longest common subsequence with the original sequence. Th? answer is n-LCS. Now, LCS problem is still O(n^2). There is also a O(rlog(n)) algo, where r is the number of pairs (i,j) such that ai = bj...
If there is ever a war between men and machines, it is easy to guess who will start it (c) Arthur Clarke

simon_cuet
New poster
Posts: 2
Joined: Thu Feb 21, 2008 1:57 pm

### Re: 11753 - Creating Palindromes

There is no necessity of "dynamic programming" to solve this problem. It's an "adhoc" problem with a few line code in C++
I solved this problem in 0.324 sec. But to avoid TLE you must need to check a certain condition.

robot
New poster
Posts: 29
Joined: Sun May 24, 2009 8:39 pm

### Re: 11753 - Creating Palindromes

Hi simon
How it's possible in adhoc. i solve it with Recursion , but time nedded 0.63. please can u tell ur process.
u can tell this address. thimpu_cse@yahoo.com

just_yousef
New poster
Posts: 50
Joined: Tue Dec 17, 2013 11:01 pm

### Re: 11753 - Creating Palindromes

Got AC With regular DP and a special condition, Like Problem 10453 - make palindrome
But Solution is slow :/
and ideas for better solution ??

jalil_cse
New poster
Posts: 8
Joined: Tue Dec 25, 2012 12:35 pm

### Re: 11753 - Creating Palindrome

plz help me why runtime error

Code: Select all

``````#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<stdlib.h>
#include<memory.h>
using namespace std;
int pal(int str[], int n)
{
int table[n][n], l, h, gap;
memset(table, 0, sizeof(table));

for (gap = 1; gap < n; ++gap)
for (l = 0, h = gap; h < n; ++l, ++h)
table[l][h] = (str[l] == str[h])? table[l+1][h-1] :
(min(table[l][h-1], table[l+1][h]) + 1);
return table[0][n-1];
}
int main(){
int t,ca=1;
cin>>t;
while(t--)
{
int n,arr[100010],te;
cin>>n>>te;
for(int i=0;i<n;i++)
{
cin>>arr[i];
}
int l=pal(arr,n);
//cout<<l<<endl;
if(l==0)
printf("Case %d: Too easy\n",ca++);
else if(te>=l)
printf("Case %d: %d\n",ca++,l);
else
printf("Case %d: Too difficult\n",ca++);
}
return 0;
}
``````

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

### Re: 11753 - Creating Palindrome

Your table array is probably using too much memory.
Check input and AC output for thousands of problems on uDebug!

fresher96
New poster
Posts: 25
Joined: Wed Sep 03, 2014 8:50 am

### Re: 11753 - Creating Palindrome

can this problem be solvable using DP, if so how to reduce the O(n^2) complexity ?