11022 - String Factoring

[rajkon]

Hi,

can anybody give me some tricky examples?

Thanks

[Jan]

Here are some samples

Input:

Code: Select all

ABCABCCBACBA
AAAAABBBABBB
BBAXXBBAXX
AABBCCBBAA
ABCDEFGHGHGHEF
FINLALLY
ACCEPTED
*

Output:

Code: Select all

6
3
3
5
10
7
7

Hope it helps.

[lonelyone]

any hint, please

[sclo]

solve it with dp, it can be done in O(n^3)

[Jan]

You can solve it by recursion. To make it faster use memorization.

[lonelyone]

thanks for sclo and jan, I solved it already
it seems as matrix multiply

Lonely

[devmax]

How to use DP?
i think, it is not similar to matrix chain multiplication.

[Timo]

it is 90% similiar to matrix chain multiplication problem

[Hackson]

it is 90% similiar to matrix chain multiplication problem

Yes, definitely

I 've got this problem accepted, but I think the runtime was a bit too slow. I 've tried writting it in both C++ and pascal, but well, the runtime is about 1.4~1.7sec, which is not enough to solve it for N = 380 (N=80 originally).

I saw most can got it in 0.0xx sec

As I am not spoiling , may be I can post part of my code, it's 90% similar to MCM

Code: Select all

/*Hidden above*/
                                string t, A, B;
                                int tind, p;
                                A = DP[i][j];
                                B = DP[j+1][m];
                                if (A == B){
                                        t = A;
                                        tind = ind[i][j] + ind[j+1][m];
                                        p = ans[i][j];
                                }else{
                                        char Tp;
                                        Tp = ind[i][j];
                                        A=A+'*'+Tp;
                                        Tp = ind[j+1][m];
                                        B=B+'*'+Tp;
                                        t = A+B;
                                        tind = 1;
                                        p = ans[i][j] + ans[j+1][m];
                                }
                                if (/*comparison*/){
                                        /*Assign new DP value*/
                                }
/* Hidden below*/

where DP stores the factorized string so as to compare, ind stores the index of the factorized string and ans stores the mimimum length.
Is it too slow to solve the problem? And, should DP and ind be used in the solution?

[Timo]

My solution is use recursive with memo and I get 0:00.051.
I think you must optimize your dp.

[Hackson]

My solution is use recursive with memo and I get 0:00.051.
I think you must optimize your dp.

Yep, under some but limited optimization, I got 0:00.58x.

But I 'd like to ask what you 've memoized?
Is the recursive formula same as mine?

[asif_rahman0]

Can someone tell me how can i reduce my Time Limit?
I got it accepted within 0.00.5sec:(.
I used O(n^2) to find Periodic String in MCM. Is there any better algorithm or STL function which can help me to reduce my TL?



thnx
rabbi



------------------------------------------------------------------------

[gauravc]

I have no clue about the DP to be used for the problem. Any hints please?