11523 - Recycling

[Leonid]

I used O(n^3) DP solution but I can't get AC.
Some good tests anyone?...

[Marius]

I used DP in O(N^4) and I can't imagine how I can reduce it to O(N^3).

I'm sorry. I was confused with other problem. It's O(N^3).

[Leonid]

My idea is the following:

DP(i,j) is the answer for the substring starting at index i and ending at index j
Also I denote S(i) as particular element in a given string and S(i,j) as substring.

First I find all answers for substring of length L.
We must remove element S(i) of the substring S(i,j).
It can be done in 2 ways:
We remove only element S(i) with one move without merging it with other elements to the right of the substring: DP(i,j) = 1 + DP(i + 1, j)
We remove element S(i) with some other elements to the right. Observe, that if we remove it with some other elements to the right, then the leftmost element with the same value as S(i) and with index greater than i must be removed. Say the index of this elements is k. To merge elements S(i) and S(k) we consider DP(i+1,k-1) and DP(k,j). In this case the answer is DP(i,j) = DP(i + 1, k - 1) + DP(k, j). Observer that we don't add 1 to the answer, since S(i) is merged with S(k).
Generally DP(i, j) = min(1 + DP(i + 1, j), DP(i + 1, k - 1) + DP(k, j)); with k as defined above. I believe this approach could be done in O(N^2 * log(N) ). In my case I've done it in O(N^3).

What is wrong with this approach?...
I haven't found any tests that would fail.
I'd be very happy if I found one...

[Leonid]

Ok, I solved problem: THX to Vytenis

This assumption was wrong

Code: Select all

Observe, that if we remove it with some other elements to the right, then the leftmost element with the same value as S(i) and with index greater than i must be removed.

[evelynjames]

My idea is the following:

DP(i,j) is the answer for the substring starting at index i and ending at index j
Also I denote S(i) as particular element in a given string and S(i,j) as substring.

First I find all answers for substring of length L.
We must remove element S(i) of the substring S(i,j).
It can be done in 2 ways:
We remove only element S(i) with one move without merging it with other elements to the right of the substring: DP(i,j) = 1 + DP(i + 1, j)
We remove element S(i) with some other elements to the right. Observe, that if we remove it with some other elements to the right, then the leftmost element with the same value as S(i) and with index greater than i must be removed. Say the index of this elements is k. To merge elements S(i) and S(k) we consider DP(i+1,k-1) and DP(k,j). In this case the answer is DP(i,j) = DP(i + 1, k - 1) + DP(k, j). Observer that we don't add 1 to the answer, since S(i) is merged with S(k).
Generally DP(i, j) = min(1 + DP(i + 1, j), DP(i + 1, k - 1) + DP(k, j)); with k as defined above. I believe this approach could be done in O(N^2 * log(N) ). In my case I've done it in O(N^3).

What is wrong with this approach?...
I haven't found any tests that would fail.
I'd be very happy if I found one...

been trying the said procedure but I can't seems to figure out.

[forthright48]

Really interesting problem. Found a good hint from UVA Toolkit that this problem is similar to SRM 240 Div 1 900. Here is the editorial link http://community.topcoder.com/tc?module ... &d2=srm240