try visit
http://www.comp.nus.edu.sg/~stevenha/pr ... g_dp1.html
there are explanation about LIS there.
10154 - Weights and Measures
Moderator: Board moderators
LIS algorithm can have a time complexity of O(n log n).
But for this problem, O(n^2) is quite enough
But for this problem, O(n^2) is quite enough
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org
-
Julien Cornebise
- Experienced poster
- Posts: 145
- Joined: Sat Feb 23, 2002 2:00 am
- Location: Paris, France
- Contact:
Hi !
I finally got AC, but... I don't understand why !!
I sort by strength then by weight (if strengths are equal), then LIS. This got me AC.
But ! I don't understand why my first prog, wich is almost the same but that sort by RESIDUAL STRENGTH instead of strength got WA. I saw that it failed on the test case mentionned earlier in the topic, but I still don't see why it does not work... I mean : a very heavy turtle, with a residual strength of 1 (but with a very big strength) will be of no use, so the residual strength seems more meaningful to me. Indeed, I can see it's not, because it gets WA, but ... well, I simply can't see why.
Please could someone explain me ?
Thank you !
I finally got AC, but... I don't understand why !!
I sort by strength then by weight (if strengths are equal), then LIS. This got me AC.
But ! I don't understand why my first prog, wich is almost the same but that sort by RESIDUAL STRENGTH instead of strength got WA. I saw that it failed on the test case mentionned earlier in the topic, but I still don't see why it does not work... I mean : a very heavy turtle, with a residual strength of 1 (but with a very big strength) will be of no use, so the residual strength seems more meaningful to me. Indeed, I can see it's not, because it gets WA, but ... well, I simply can't see why.
Please could someone explain me ?
Thank you !
10154
many people said the algorithm of 10154 is LIS
and my LIS program also got AC
(sort the strength first and the weight secondary)
but i don't think so
what about this input
200 220
10 110
my AC program using algorithm LIS gave me the answer 1
but i think the correct answer should be 2
(put the first at the bottom ,and the second at the top)
can anyone explain about it?
thanks in advance!
and my LIS program also got AC
(sort the strength first and the weight secondary)
but i don't think so
what about this input
200 220
10 110
my AC program using algorithm LIS gave me the answer 1
but i think the correct answer should be 2
(put the first at the bottom ,and the second at the top)
can anyone explain about it?
thanks in advance!
-
Adrian Kuegel
- Guru
- Posts: 724
- Joined: Wed Dec 19, 2001 2:00 am
- Location: Germany
Yes, the answer should be 2. But it is possible to solve this input by sorting according to strength.
I can explain why you can sort by strength: Assume the solution would have a turtle that is stacked upon a turtle with smaller strength. Then the turtle with smaller strength has to carry also the weight of the turtle with bigger strength. So it is also possible to exchange them, because if the turtle with smaller strength can carry at least both weigths, then of course the turtle with bigger strength can.
I can explain why you can sort by strength: Assume the solution would have a turtle that is stacked upon a turtle with smaller strength. Then the turtle with smaller strength has to carry also the weight of the turtle with bigger strength. So it is also possible to exchange them, because if the turtle with smaller strength can carry at least both weigths, then of course the turtle with bigger strength can.
10154 - weights & measures
Hi!!
I've read in previous posts that this problem is about dynamic pogramming, LIS. But I can't see how i can apply LIS to this problem. And why do you sort by strength then by weight? I think we have to take into account the residual strength.
Please give me some hint to get to the solution.
I've read in previous posts that this problem is about dynamic pogramming, LIS. But I can't see how i can apply LIS to this problem. And why do you sort by strength then by weight? I think we have to take into account the residual strength.
Please give me some hint to get to the solution.
This is not in fact a LIS problem, but rather one that is solved with greedy algorithm. Before using LIS, I suppose that you are sorting the input, boiling down to a greedy algorithm where sorting criterion is the cost function.
I've got AC on greedy algo by maximizing "remaining strength" which is defined recursively as:
MIN(remaining_strength - weight(i), strength(i) - weight(i))
with initial remaining_strength = INFINITE.
In each step, I take the turtle that maximizes this measure, and that's all.
I've got AC on greedy algo by maximizing "remaining strength" which is defined recursively as:
MIN(remaining_strength - weight(i), strength(i) - weight(i))
with initial remaining_strength = INFINITE.
In each step, I take the turtle that maximizes this measure, and that's all.
-
Adrian Kuegel
- Guru
- Posts: 724
- Joined: Wed Dec 19, 2001 2:00 am
- Location: Germany
I am not sure if your greedy is correct. At first I got Accepted with a greedy algorithm, for which I found a counter example.
Here is the correct way how to solve the problem:
First, you can sort by strength. Prove:
Assume the solution would have a turtle that is stacked upon a turtle with smaller strength. Then the turtle with smaller strength has to carry also the weight of the turtle with bigger strength. So it is also possible to exchange them, because if the turtle with smaller strength can carry at least both weights, then of course the turtle with bigger strength can.
Now you can use DP: Go through the list of turtles that is sorted ascending by strength (because I try to stack a tower of turtles upon ith turtle, therefore the turtle with smallest strength has to go first). In each step calculate the minimum weight that a stack of k turtles has. If it is impossible to have a stack of k turtles, define this as Infinity. Lets define this as mw(i,k) (i is number of step). mw(i,k) = min(mw(i-1,k),mw(i-1,k-1)+weight(i)) if mw(i-1,k-1)+weight(i)<=strength(i) or else mw(i,k) = mw(i-1,k). Answer is maximum k with mw(n,k)<infinity.
Here is the correct way how to solve the problem:
First, you can sort by strength. Prove:
Assume the solution would have a turtle that is stacked upon a turtle with smaller strength. Then the turtle with smaller strength has to carry also the weight of the turtle with bigger strength. So it is also possible to exchange them, because if the turtle with smaller strength can carry at least both weights, then of course the turtle with bigger strength can.
Now you can use DP: Go through the list of turtles that is sorted ascending by strength (because I try to stack a tower of turtles upon ith turtle, therefore the turtle with smallest strength has to go first). In each step calculate the minimum weight that a stack of k turtles has. If it is impossible to have a stack of k turtles, define this as Infinity. Lets define this as mw(i,k) (i is number of step). mw(i,k) = min(mw(i-1,k),mw(i-1,k-1)+weight(i)) if mw(i-1,k-1)+weight(i)<=strength(i) or else mw(i,k) = mw(i-1,k). Answer is maximum k with mw(n,k)<infinity.
-
Adrian Kuegel
- Guru
- Posts: 724
- Joined: Wed Dec 19, 2001 2:00 am
- Location: Germany
By the way, I think that LIS is also incorrect (at least if you use normal LIS). Consider following test case (already sorted by strength):
500 1000
400 900
100 800
101 700
You can stack turtles 2,3,4. With LIS you would find only a stack of size two. Because in normal LIS, you can add a value to a sequence if it is > than last element added before. Here you cannot do that in all cases.
Or another test case (for other LIS approach):
101 101
100 201
99 300
98 301
5 302
best stack has turtles 2,3,4,5
500 1000
400 900
100 800
101 700
You can stack turtles 2,3,4. With LIS you would find only a stack of size two. Because in normal LIS, you can add a value to a sequence if it is > than last element added before. Here you cannot do that in all cases.
Or another test case (for other LIS approach):
101 101
100 201
99 300
98 301
5 302
best stack has turtles 2,3,4,5
-
Adrian Kuegel
- Guru
- Posts: 724
- Joined: Wed Dec 19, 2001 2:00 am
- Location: Germany
Sorry if I sounded rude, Adrian, I meant it's fishy that 95% of people didn't find out that both LIS and simple greedy are fundamentally incorrect. 
Well, it seems like I have got AC again, by modifying the greedy algorithm. It now uses construction approach:
1. start with an empty stack
2. in each step try to add one turtle ANYWHERE in or on or below the stack, in such the manner that total remaining strength of the stack is maximal
3. repeat step 2 while possible
This algorithm has solved all samples from these posts, and also got AC. It solves, for instance, trivial case with two turtles that cannot be solved with simple greedy algorithm:
5 15
11 17
Correct answer is obviously 2, but simple greedy that puts new turtle always on top of the current stack would give result 1 by taking 5 15 turtle (that has max(remaining strength), and then gets stuck.
Real reason why simple greedy or one-dimensional LIS do not work here is because they both rely on some kind of sorting, with fixed and predefined sorting criterion. When I say fixed criterion (say, relation R), I mean that sorting is a recurrent operation where array of N elements is sorted if its first N-1 elements are sorted and Nth element is in relation R with all elements before it. One of the tricks that make greedy and LIS algorithms nice (and often hard to prove) is that relation R doesn't have to be transitive as it normally is in plain sorting problems.
I am not sure about the proof of the algorithm above. For example, I haven't proved exactly how to resolve multiple solutions in one step although I did it somehow. As for now, I am AC and out, and I hope there will be no further counter examples that would make my solution WA again
. I just hope that I've learned something out of this problem.
Well, it seems like I have got AC again, by modifying the greedy algorithm. It now uses construction approach:
1. start with an empty stack
2. in each step try to add one turtle ANYWHERE in or on or below the stack, in such the manner that total remaining strength of the stack is maximal
3. repeat step 2 while possible
This algorithm has solved all samples from these posts, and also got AC. It solves, for instance, trivial case with two turtles that cannot be solved with simple greedy algorithm:
5 15
11 17
Correct answer is obviously 2, but simple greedy that puts new turtle always on top of the current stack would give result 1 by taking 5 15 turtle (that has max(remaining strength), and then gets stuck.
Real reason why simple greedy or one-dimensional LIS do not work here is because they both rely on some kind of sorting, with fixed and predefined sorting criterion. When I say fixed criterion (say, relation R), I mean that sorting is a recurrent operation where array of N elements is sorted if its first N-1 elements are sorted and Nth element is in relation R with all elements before it. One of the tricks that make greedy and LIS algorithms nice (and often hard to prove) is that relation R doesn't have to be transitive as it normally is in plain sorting problems.
I am not sure about the proof of the algorithm above. For example, I haven't proved exactly how to resolve multiple solutions in one step although I did it somehow. As for now, I am AC and out, and I hope there will be no further counter examples that would make my solution WA again
. I just hope that I've learned something out of this problem.