## 11523 - Recycling

Moderator: Board moderators

Leonid
Experienced poster
Posts: 146
Joined: Thu Dec 22, 2005 5:50 pm
Contact:

### 11523 - Recycling

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

Marius
New poster
Posts: 5
Joined: Thu Apr 10, 2008 5:55 pm

### Re: 11523 - Recycling

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).
Last edited by Marius on Wed Oct 15, 2008 7:23 am, edited 1 time in total.

Leonid
Experienced poster
Posts: 146
Joined: Thu Dec 22, 2005 5:50 pm
Contact:

### Re: 11523 - Recycling

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
Experienced poster
Posts: 146
Joined: Thu Dec 22, 2005 5:50 pm
Contact:

### Re: 11523 - Recycling

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
New poster
Posts: 1
Joined: Sat Feb 09, 2013 10:41 am

### Re: 11523 - Recycling

Leonid wrote: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.
custom phone cases designer for kekacase.com

forthright48
New poster
Posts: 37
Joined: Wed Mar 14, 2012 11:57 am