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,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...
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...
Re: 11523 - Recycling
Ok, I solved problem: THX to Vytenis
This assumption was wrong
This assumption was wrong
![:)](./images/smilies/icon_smile.gif)
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,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
-
- 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