11523 - Recycling

All about problems in Volume 115. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

11523 - Recycling

Post by Leonid » Mon Oct 13, 2008 12:09 am

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

Post by Marius » Tue Oct 14, 2008 10:41 am

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

Post by Leonid » Tue Oct 14, 2008 11:32 pm

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

Post by Leonid » Wed Oct 15, 2008 2:14 am

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

Post by evelynjames » Sat Feb 09, 2013 10:44 am

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
Location: Bangladesh
Contact:

Re: 11523 - Recycling

Post by forthright48 » Wed May 07, 2014 11:40 am

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
What ever happens, happens for good. Even when we get WA :p
http://www.forthright48.com

Post Reply

Return to “Volume 115 (11500-11599)”