11753 - Creating Palindrome

[serur]

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?

[mintae71]

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

[serur]

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

[simon_cuet]

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]

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]

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]

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]

Your table array is probably using too much memory.

[fresher96]

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