Last week I was at the Romanian training camp for the IOI, after several years of absence. (If you don't know what I'm talking about, I wrote a series of posts about informatics olympiads a while ago.) To my great surprise, I was still able to solve the competition problems :)
Unlike Math, CS doesn't have a culture for tough puzzles, i.e. problems that are not "important" for any reason, but are fun and intellectually challenging. Perhaps the difference is that CS folks are vastly superior to Mathematicians when it comes to bull-shitting (our ability to draw targets around any arrow we shoot makes all our problems "serious research"...)
In any case, here's a rewarding problem from the competition, for your own enjoyment. It captures my intuitive notion of a "CS puzzle" very well, but beware: it is not a trivial puzzle. (It may have taken me one hour of thinking, of course in my current rusty state.)
Dwarves. n dwarves fell in a hole that is H meters deep. Each dwarf is characterized by the distance from his feet to his shoulders (hi), and the length of his arms (li). Dwarves can pile up as a tower, with each dwarf sitting on the shoulders of another. The dwarf at the top of the tower can climb out of the hole if his hands, stretched up, can reach to the top.
Given n, H, hi, and li, find the maximum number of dwarves that can escape from the hole (through forming towers as above; of course, once a dwarf escapes he cannot take part in another tower).
Desired running time: O(n2). Can you do better?
Tuesday, June 24, 2008
Dwarves
Subscribe to:
Post Comments (Atom)
![[home]](http://people.csail.mit.edu/mip/images/home.gif){kind=small}
33 comments:
hi
First if we see the simpler problem of having everyone's hand length=0. Then the problem reduces to sorting in decreasing order and keeping the first k persons such that their sum of length < H.
Now consider the general problem. It is nothing but for each person consider H-hi-li and check what is the optimal way to do the restricted problem with remaining already sorted people in H-hi-li. (O(n2))
Hmmm(can u do better) of O(n logn). I guess in the second step of previous solution if you use a slightly modified verion of binary search it will yield O(n logn) algo.
Unlike Math, CS doesn't have a culture for tough puzzles, i.e. problems that are not "important" for any reason, but are fun and intellectually challenging.
Some would argue that CS, unlike math, has a culture of nothing but tough but unimportant puzzles!
About the dwarves: If there is a giant dwarf whose height is equal to the depth of the hole and whose arms have length epsilon, does every dwarf escape? When can one dwarf climb on another's shoulders?
Jeff: yes, all dwarves escape in your example (i.e. any tower can be formed irrespective of heights).
Ashwinkumar: I don't understand how your solution can work. If the "remaining dwarves" can give you H-hi-li, then this dwarf can escape. But it says nothing about the maximal number of dwarves that escape. In other words, searching for some optimal solution for height H-hi-li doesn't tell you anything.
hi
i guess i wrote ambiguously. What i meant was to assume that there is some arrangement of dwarfs inside the well when the last dwarf escapes. Now assume that the ith dwarf is at the top of this arrangement(we loop for i=1 to n).
This dwarf covers H-hi-li of the height. So the sum of remaining dwarf's height(hands not included) in the well should be at max of H-hi-li-1. This is nothing but the first simplification i solved. The minimum can be found out by minimum of the answers found for i=1 to n(one of these is bound to be the minimum)
{border case of everyone escaping not considered}.
You are looping to find the last dwarf to escape. But which are the rest escaping?
There are counterexamples to sorting dwarves by something, and then sayng that the first i must escape.
Obviously the ones which are not in the hole have escaped. What i essentially gave was algo to minimize number of dwarfs left inside the hole. (The ones left are the top one and the remaining ones below the top one in the minimum calculated.)
This is not exactly sorting. Which step in the algo do you disagree with? I am unable to find any mistake.
But how do you know that all the rest can escape?? You are minimizing the ones who stay in the whole, conditioned on a single guy escaping.
Alright, Let me explain it again.
First simplified case. All hand lengths=0. Then sort all of them in decreasing order. Find k such that sum of height of first k is less than H and sum of first k+1 is greater than or equal to H. Then first k remain and rest all escape. Do you agree with my first simplification? (algo in this para is just for hand length=0 special case)
Also assuming first simplification is right.
Assume ith person is at the top. If this assumption of ith person at the top is right, do you agree that the remaining problem reduces to the first simplification with new H=H-hi-li and remaining dwarfs with height or ith dwarf=hi and hand length=0.
If u dont agree with any of above assumptions, state why
One loop to check by brute force who is at the top and solve the problem.
I agree with the case when all li=0. No problem.
I do not agree with the second part. What do you mean by "the i-th person is at the top"? At the top when? Many dwarves can escape. Which one is i?
As, i had mentioned. i is a loop variable from i to n(it is not a variable to indicate who was the i-th person to leave).
i-th person is at the top when all dwarfs have escaped. (You can consider the arrangment when the last dwarf has left)
Since we are talking past each other, I suggest we end this conversation. Just think carefully about what you're saying, and you will see how it fails.
Your solution needs to guarantee that all dwarves who have supposedly escaped can in fact escape. The ones remaining (with i on top) cannot guarantee that all other escape. The order in which they escape also matters, for instance.
Let me explain my solution.
Let us call a set of dwarves $R$ a rescue team, if all other dwarves can escape while dwarves from $R$ are at the bottom of the pit.
Obviously $R$ is a rescue team iff:
$$
\sum_{i \in R} h_i + \min_{j \notin R} (h_j + l_j) \geq H
$$
this is essentially a definition of $R$ re-written as formula.
The problem will be solved, if we find a resuce team with minimum number of dwarves. (The claim requires some additional reasoning. However, I skip it due to its relative simplicity.)
Straightforward algorithm enumerates all possible rescue teams $R$ and finds the smallest one. It has exponential execution time.
However, smallest rescue team can be found much faster.
Let us put all the dwarves into array $A$ and sort them in the ascending order of $h_i + l_i$. For each set of dwarves $X$, exists a unique index in array $A$ --- the smallest index of the dwarf not in $X$, $j(X)$.
We will enumerate all possible values of $j(X)$ from $n$ till $1$.
For each value $j'$ we will find the smallest rescue team $R$ with $j(R) = j'$. Let us look at the characteristic formula of rescue team above. Minimum is now obviously equal to $l_{A[j']} + h_{A[j']}$. Sum contains all of the elements to the left of $j(X)$ plus (in case of smallest rescue team) minimum amount of dwarves to the right of $j(X)$ sufficient to satisfy the inequality. This minimum amount can be easily found by sorting all dwarves to the right of $j(X)$ in descending order of their heights.
It looks like, that efficient implementation of this algorithm will have $O(n \log n)$ comparisons and $O(n^2)$ additions.
I have a slight suspicion that this is what ashwinkumar was trying to explain.
alexander: my solution is a bit different from yours.
say if H=10.
h1=7,l1=0
h2=4,l2=1
h3=1,l3=1
According to your assumption R={1} cannot be a rescue team as
h1+min(h2+l2,h3+l3)=9 is not greater than 10.
But I assumed that after 2 stands over 1 he doesnt immediately get out. 3 can then stand over 2 and get out and then 2 can get out.
so the confusion may be regarding what i understood the problem as.
Nice problem, Mihai. Would you mind posting a link to the test data (if available)? So that we could check correctness of our solutions.
My approach is greedy.
1. In the optimal solution, if two dwarves i, j can escape and h[i]+l[i] > h[j]+l[j] then the solution where the i-th dwarve escapes later than the j-th dwarve is also optimal.
2. Therefore, we can sort the list of the dwarves in descending order of h[i]+l[i] (such that the first dwarve is the biggest and the last is the smallest). We also can assume that when the i-th dwarve is escaping, all dwarves before him (j < i) are in the tower.
3. Now we go from the smallest dwarve to the biggest (i.e. i:= from n to 1) and mark some dwarves as sacrificed. A sacrificed dwarve is doomed to live in the well. The algorithm looks like:
h_s = 0
(h_s -- sum of the heights of the sacrificed dwarves)
for i = n to 1
h_p = sum(h[j] | 1 <= j < i)
if (h[i]+l[i]+h_s+h_p < H)
begin
this means that i-th dwarve cannot escape, we must sacrifice at least one dwarve.
find the dwarve k (i <= k <= n) among the unsacrificed dwarves with the maximum height (greedy!).
mark the k-th dwarve as sacrificed and set h_s = h_s + h[k].
end
The complexity is O(n^2). Could be made O(nlogn) with priority queue.
Proof by implementation :) (Sources are available).
Alexander, I disagree with the idea that you have to find R, as you defined it.
Say there are 2 dwarves outside R (call them D1 and D2). It could be that if D1 escapes, D2 will not be able to escape after that. But if D1 is added onto R, D2 can escape, and then D1 can escape.
What I'm saying is that in some sense R is different for each person, and the order in which you take the guys out matters.
u1ik, how do you know that it's optimal to NOT sacrifice a dwarf if you don't have to? Maybe if you sacrifice a guy early (even if sacrificing him is not needed), you can rescue a lot later.
The test data is here.
Format:
n (n ≤ 2000)
h1 l1
...
hn ln
H
But I want to encourage you to think about your solution formally, instead of just trying out random stuff. A nice dynamic program is usually "obviously correct." A formal proof of correctness is usually a few lines.
Thanks for the tests :)
I coded my solution and it seems to work.
Of course it only proves that that the solution is not total nonsense, not that it is correct.
how do you know that it's optimal to NOT sacrifice a dwarf if you don't have to?
Even if we skip a dwarf at the current iteration of the for-loop, we always have a chance to sacrifice him later if he is tall enough (note that we sacrifice the k-th dwarf, not the i-th in the loop)
A sketch of the proof:
Assume that the list is sorted as before.
Let a[1] > a[2] > a[3] .. > a[r] be the indexes of the sacrificed in the optimal solution. And let b[1] > b[2] > b[3] >... > b[q] be the indexes of the sacrificed by the greedy solution.
We can drop the dwarves that were sacrificed by both solutions and assume that the sets of indexes are disjoint.
Now we want to prove that h[a[1]] <= h[b[1]]. Which means that the b[1]-th dwarf is as helpful for others as the a[1]-th dwarf.
if a[1] > b[1], the claims follows from the part of the algorithm where we select the tallest dwarf k from [b[1]..n] in the loop.
if a[1] < b[1], then b[1] was sacrificed when some dwarf i <= b[1], could not get out with the help of previously sacrificed guys and all other guys with smaller indexes. Note that i <= a[1] (not very obvious!).
And b[1] was selected as the tallest guy among [i..n].
---
Here is my
code.
Was the intended solution dynamic programming? If there is O(n^2) DP solution, I need to think more.
PS
In my first comment I use dwarve as a singular for dwarf, but now I cannot edit it. Sorry for that. :)
For my solution the proof would have three parts, but I'm too lazy to write and check them :P
1. Establish that for any solution that saves D dwarfs there is a one that lets the D dwarfs exit in order of increasing l+h. Therefore we only need to potential solutions that follow this.
2. Define H(i,j) to be the minimum total height of dwarfs in the hole needed to save j out of the first i dwarfs and write the recurrence for that.
Obviously, I was to lazy even to write a proper comment, even if it's probably somewhat understandable.
One part that is missing: By "the first i dwarfs" I mean the ones with high h+l (not low).
rgrig, your comment is essentially the entire proof :) I guess you've been looking too much at CLRS or other places, where a proof is defined to be a long formal description that obscures any understanding you might've had.
u1ik, I think your solution works. Nice!
It is quite similar to another greedy that I heard about during the training camp, and eventually I got convinced that that one works. So proof by similarity :)
"I guess you've been looking too much at CLRS"
Oh, I guess it's because I work with automated theorem provers where 'proof' means a file that has a few megabytes :)
Here's a puzzle you and your readers might like.
It's problem from russian olympiad. Did you know it?
Yes, I heard something about a Russian Olympiad, but don't know any details (I wasn't "involved" in this problem, just reporting it here because I think it's cool).
Are the Russian problems available somewhere in a language besides Russian?
I don't think so. :(
And I can be proud of myself. I solved it during olympiad. =)
Congrats! :)
the post is a little bit old now, but I found the problme funny.
Perhap's it's non sense, but I think I have a simple solution in O(n log n).
The idea is to build a set S of guys who sacrifice for the others (and won't escape) and a set T of helpers that will help others before getting out.
Let AS be the array of dwarves by h_i in decreasing order.
Let AT be the array of dwarves by h_i + l_i in decreasing order.
The process is presented here in a recursive way:
First you look at the top element of AT, if he can get out (h_i+l_i > H), it becomes a helper, you put it in T and you start again with H = H - h_i and removing this dwarf.
If this long-armed guy cannot get out, it means that nobody can: at least a dwarf has to sacrifice. So, we choose a big-body guy that will help the more people: we take the first elt in AS and we go on with H = H - h_i.
When no dwarf remain (all of thems are in S or T), all guys in T escape in the reverse order they have been put in T.
It seems to work, since each time we sacrifice a guy, it is the only way to let all the other stuck in the hole.
If there is an easy counterexample, please tell me.
Otherwise, has anyone an idea of what happens when all dwarves are not equal, i.e., each of them has a value v_i and you want to maximize the sum of the v_i that escaped.
I agree that in this case, for ethic reasons, we should change from dwarves to some non-aminated stuff :)
Something is missing in my previous comment: it works only if the sum of h_i + the min of l_i is greater or equal to H.
It's not a problem: we first put in S all the dwarves j such that sum (h_i) + l_j < H and then we keep with the previous solution.
Is the relation H(i,j) = min(H(i-1,j), max(H-li-sum(hi), H(i-1,j-1))) correct for the H function that rgrig defined (sum(hi) stands for the sum of the heights of all of the dwarfs)?
Thanks.
Post a Comment