11753 - Creating Palindrome

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

Moderator: Board moderators

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

11753 - Creating Palindrome

Post by serur » Tue Jan 19, 2010 8:52 pm

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

Post by mintae71 » Thu Jan 21, 2010 7:46 am

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

Post by serur » Thu Jan 21, 2010 10:41 am

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

Post by simon_cuet » Wed Feb 24, 2010 5:19 pm

There is no necessity of "dynamic programming" to solve this problem. It's an "adhoc" problem with a few line code in C++ :D
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

Post by robot » Thu Aug 19, 2010 11:34 am

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

Post by just_yousef » Wed Aug 13, 2014 1:47 am

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

Post by jalil_cse » Thu Jan 08, 2015 10:16 am

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

Post by brianfry713 » Fri Jan 09, 2015 12:41 am

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

Post by fresher96 » Sun Apr 12, 2015 12:54 pm

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

Post Reply

Return to “Volume 117 (11700-11799)”