I used O(n^3) DP solution but I can't get AC.
Some good tests anyone?...
11523  Recycling
Moderator: Board moderators
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).
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.
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,k1) 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...
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,k1) 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...
Re: 11523  Recycling
Ok, I solved problem: THX to Vytenis
This assumption was wrong
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.

 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,k1) 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

 New poster
 Posts: 37
 Joined: Wed Mar 14, 2012 11:57 am
 Location: Bangladesh
 Contact:
Re: 11523  Recycling
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