OJ Board

Posted: **Sun Apr 02, 2006 2:00 pm**

Hi,

can anybody give me some tricky examples?

Thanks

Posted: **Mon Apr 03, 2006 12:42 am**

Here are some samples

Input:

ABCABCCBACBA
AAAAABBBABBB
BBAXXBBAXX
AABBCCBBAA
ABCDEFGHGHGHEF
FINLALLY
ACCEPTED
*

Output:

Code: Select all

Hope it helps.

Posted: **Sat Apr 15, 2006 7:52 am**

any hint, please

Posted: **Sat Apr 15, 2006 8:47 am**

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

Posted: **Sat Apr 15, 2006 11:55 am**

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

Posted: **Mon Apr 17, 2006 8:24 am**

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

Lonely

Posted: **Tue May 23, 2006 8:37 pm**

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

Posted: **Wed May 24, 2006 7:46 am**

it is 90% similiar to matrix chain multiplication problem

Posted: **Wed May 24, 2006 10:53 am**

Timo wrote: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?

Posted: **Wed May 24, 2006 2:30 pm**

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

Posted: **Wed May 24, 2006 6:24 pm**

Timo wrote: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?

Posted: **Sat Jul 01, 2006 6:51 pm**

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

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

Posted: **Fri Apr 10, 2009 5:57 pm**

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

OJ Board

11022 - String Factoring

11022 - String Factoring

Re: 11022 - String Factoring