bonnon
Answer
b onno n

Edited by author 27.10.2022 10:18

Edited by author 27.10.2022 10:19

might it is very complicated but i use hash and dp to solve this problem

I had MLE on test 33. I just changed int to short and 1,0 to bool
Sorry if this is too obvious

Edited by author 22.11.2020 16:48

Try this abacabadabacab.
The problem is in hash.
Answer is : a bacabadabacab

Edited by author 15.08.2018 21:18

nvm accepted

Edited by author 05.02.2017 04:33

pls help

Edited by author 24.02.2016 16:20

try this:
aaaba

is
2
aa aba

not
3
aaa b a

Stuck at test case #12

Per reply in 2008, someone suggested testing with axayaaxa

I don't know whether this is the real #12. But I tried anyway.

My program answers a x aya axa

And another possible answer is axa y a axa

Both with 4 palindromes. Question says output any is correct.

Suggestion?

Thanks in advance!

Can i get test case 59?

I am getting wrong answer.Please give me some test case.
My solution:


#include<iostream>
#include<string.h>
#include<string>
#include<stdlib.h>
#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
string line;
bool check(int s,int e)
{
    string temp;
    for(int i=s; i<=e; i++)
        temp.push_back(line[i]);
    string temp2=temp;
    reverse(temp.begin(),temp.end());
    if(temp==temp2)
        return true;
    return false;
}
int dp[4005][4005];
int palindrome(int s,int e)
{
    if(s>=e)
        return 0;
    if(dp[s][e]!=-1)
        return dp[s][e];
    int ans=(1<<30);
    for(int i=s; i<e; i++)
        if(check(s,i))
        {
            ans=min(ans,1+palindrome(i+1,e));

        }
    return dp[s][e]=ans;
}
vector<string>anss;
void print(int s,int e)
{
    int b=palindrome(s,e);
    if(b==1)
    {
        string temp;
        for(int i=s; i<e; i++)
            temp.push_back(line[i]);
            anss.push_back(temp);

        return;
    }
    for(int i=s; i<e; i++)
        if(b==1+palindrome(i+1,e))
        {
             string temp;
           for(int j=s;j<=i;j++)
             temp.push_back(line[j]);
            anss.push_back(temp);

           print(i+1,e);
           break;
        }

}
int main()
{
    cin>>line;
    int len;
    len=line.size();
    anss.clear();
    memset(dp,-1,sizeof dp);
    cout<<palindrome(0,len)<<endl;
    print(0,len);
    len=anss.size();
    for(int i=0;i<len-1;i++)
        cout<<anss[i]<<" ";
    cout<<anss[len-1]<<"\n";



}

WA #7 can anyone help plz?

using simple dp

Can you tell me why I always WA #1? Beacause I have tested all those samples in the board, and I pass them all...

I test my code at my computer,I got a test which is filled by period string "abcde" and its length is 4000,and my program run only 0.25s.
My computer is:
Memory:3GB
System:Windows XP
CPU:1.66GHZ
But I got tle at #32...Why???
Here is my code.
var
        i,j,xx,ox,t,l:longint;
        s:ansistring;
        f,x:array [1..4010] of longint;
        o:array [0..4010] of boolean;
function pdhw(l,r:longint):boolean;
var
        i:longint;
begin
        if l=r then exit(true);
        for i:=l to (l+r)>>1+1 do
          if s[i]<>s[r+l-i] then exit(false);
        exit(true);
end;
begin
        readln(s);
        l:=length(s);
        for i:=1 to l do
        begin
          f[i]:=maxlongint;
          if pdhw(1,i) then f[i]:=0
          else for j:=1 to i-1 do
                 if (f[i]>f[j]+1)and(pdhw(j+1,i)) then begin
                   f[i]:=f[j]+1;
                   x[i]:=j;
                 end;
        end;
        writeln(f[l]+1);
        xx:=l;
        repeat
          ox:=xx;
          xx:=x[xx];
          if ox=l then o[xx+1]:=true
          else o[xx+1]:=true;
        until xx=0;
        o[1]:=false;
        for i:=1 to length(s) do
          if o[i] then write(' ',s[i])
          else write(s[i]);
end.

maybe it will be useful (or at least interesting) for somebody.

at first i tried to make simple DP with O(n^3).
i tried in java (and i received TLE in 32th test).

after that i tried to realize greed algorithm and understood that this idea is wrong (simple antigreed test is: "abzzbbbzza")

aand finally i've made O(n^2) DP.
little hint: try to precalc d[l][r]:
 d[l][r] = true, s[l..r] - palindrom
 d[l][r] = false, s[l..r] - not palindrom

who can tell me what #12 is? I don't know where my program is wrong.Thank you in advance.

Edited by author 22.10.2012 13:22

A very interesting problem! Cut two successive speakers:
A. To determine the palindrome at l to r - d [l] [r] = s [l] == s [r] && d [l +1] [r-1] == 1? A: 0;
0 if it is not a palindrome, a palindrome if. Lazy dynamic)))
Two. To determine the optimal line break at the Palindromes: dp [i] = min (dp [i], dp [ij] +1);
That's all!))
Very pleased with himself))) I should think of such problems)))

Edited by author 16.06.2012 05:40

Edited by author 16.06.2012 05:42

I got a AC program from others and compare the ANSWER-nothing is wrong.
So the ADMIN I need the TEST#1 please!

Edited by author 08.09.2011 17:57