10154 - Weights and Measures

[b3yours3lf]

try visit
http://www.comp.nus.edu.sg/~stevenha/programming/prog_dp1.html

there are explanation about LIS there.

[Observer]

LIS algorithm can have a time complexity of O(n log n).

But for this problem, O(n^2) is quite enough

[Julien Cornebise]

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 !

[inkfish]

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!

[Adrian Kuegel]

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.

[inkfish]

thanks
understand now!
i think i should think of the algorithm more carefully
before i post next time

[deneb]

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.

[zoranh]

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.

[Adrian Kuegel]

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.

[Adrian Kuegel]

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

[zoranh]

I've first got AC on greedy algorithm, and now it's not AC anymore (I haven't received email stating the new judgement yet). However, acceptance rate is now less than 5%... Something's fishy here.

[Adrian Kuegel]

There is nothing fishy, it is only that most people solved the problem incorrect using lis or greedy. Try your greedy algorithm on the two test cases in my previous post, it will probably fail to solve them correctly.

[zoranh]

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.

[jackie]

I got AC using DP LIS algorithm.

Modified LIS.

I test all the sample inputs in the forum and all make right answer.

Also, I think the prove above is right.

[Yonfui]

Hi, I tried to sort out the input gave by Red Scorpian in page 1 manually, but I got a maximum stack of 9, someone pls explain why is it not 8?

The sequence goes like this:
[1 2]
[100 101]
[1 1000]
[2 1000]
[10 500]
[3 40]
[20 30]
[200 300]
[500 901]