tag:blogger.com,1999:blog-786333285568106173.post7831400725650443587..comments2024-01-25T01:05:59.968-05:00Comments on WebDiarios de Motocicleta: DwarvesMihaihttp://www.blogger.com/profile/11599372864611039927noreply@blogger.comBlogger33125tag:blogger.com,1999:blog-786333285568106173.post-85515540739221392012008-09-15T20:16:00.000-04:002008-09-15T20:16:00.000-04:00Is the relation H(i,j) = min(H(i-1,j), max(H-li-su...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)?<BR/>Thanks.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-58773764633191785512008-08-11T08:23:00.000-04:002008-08-11T08:23:00.000-04:00Something is missing in my previous comment: it wo...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.<BR/><BR/>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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-91842368943593112902008-08-09T17:52:00.000-04:002008-08-09T17:52:00.000-04:00the post is a little bit old now, but I found the ...the post is a little bit old now, but I found the problme funny. <BR/>Perhap's it's non sense, but I think I have a simple solution in O(n log n).<BR/><BR/>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. <BR/><BR/>Let AS be the array of dwarves by h_i in decreasing order.<BR/><BR/>Let AT be the array of dwarves by h_i + l_i in decreasing order. <BR/><BR/>The process is presented here in a recursive way:<BR/><BR/>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. <BR/><BR/>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.<BR/><BR/>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.<BR/><BR/>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. <BR/><BR/>If there is an easy counterexample, please tell me. <BR/><BR/>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. <BR/>I agree that in this case, for ethic reasons, we should change from dwarves to some non-aminated stuff :)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-15892988671208000852008-08-08T13:18:00.000-04:002008-08-08T13:18:00.000-04:00Congrats! :)Congrats! :)Mihaihttps://www.blogger.com/profile/11599372864611039927noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-19925951083454438852008-08-08T00:28:00.000-04:002008-08-08T00:28:00.000-04:00And I can be proud of myself. I solved it during o...And I can be proud of myself. I solved it during olympiad. =)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-67170464256663724152008-08-08T00:27:00.000-04:002008-08-08T00:27:00.000-04:00I don't think so. :(I don't think so. :(Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-5968798028325927742008-08-07T13:46:00.000-04:002008-08-07T13:46:00.000-04:00Yes, I heard something about a Russian Olympiad, b...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).<BR/><BR/>Are the Russian problems available somewhere in a language besides Russian?Mihaihttps://www.blogger.com/profile/11599372864611039927noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-41933434082483320882008-08-06T21:28:00.000-04:002008-08-06T21:28:00.000-04:00It's problem from russian olympiad. Did you know i...It's problem from russian olympiad. Did you know it?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-77288176803719846862008-07-02T02:44:00.000-04:002008-07-02T02:44:00.000-04:00Here's a puzzle you and your readers might like.Here's <A HREF="http://rgrig.blogspot.com/2008/06/black-and-white.html" REL="nofollow">a puzzle</A> you and your readers might like.rgrighttps://www.blogger.com/profile/02991214367108471744noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-37966383512109559282008-06-27T06:34:00.000-04:002008-06-27T06:34:00.000-04:00"I guess you've been looking too much at CLRS"Oh, ..."I guess you've been looking too much at CLRS"<BR/><BR/>Oh, I guess it's because I work with automated theorem provers where 'proof' means a file that has a few megabytes :)rgrighttps://www.blogger.com/profile/02991214367108471744noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-88221843790249748192008-06-27T04:46:00.000-04:002008-06-27T04:46:00.000-04:00u1ik, I think your solution works. Nice!It is quit...u1ik, I think your solution works. Nice!<BR/><BR/>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 :)Mihaihttps://www.blogger.com/profile/11599372864611039927noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-4230346427490109642008-06-27T04:43:00.000-04:002008-06-27T04:43:00.000-04:00rgrig, your comment is essentially the entire proo...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.Mihaihttps://www.blogger.com/profile/11599372864611039927noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-52166739040692516502008-06-26T07:10:00.000-04:002008-06-26T07:10:00.000-04:00Obviously, I was to lazy even to write a proper co...Obviously, I was to lazy even to write a proper comment, even if it's probably somewhat understandable.<BR/><BR/>One part that is missing: By "the first i dwarfs" I mean the ones with <I>high</I> h+l (not <I>low</I>).rgrighttps://www.blogger.com/profile/02991214367108471744noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-46984937788492584032008-06-26T07:04:00.000-04:002008-06-26T07:04:00.000-04:00For my solution the proof would have three parts, ...For my solution the proof would have three parts, but I'm too lazy to write and check them :P<BR/><BR/>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.<BR/><BR/>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.rgrighttps://www.blogger.com/profile/02991214367108471744noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-76849166347363522932008-06-26T05:42:00.000-04:002008-06-26T05:42:00.000-04:00Thanks for the tests :)I coded my solution and it ...Thanks for the tests :)<BR/>I coded my solution and it seems to work.<BR/>Of course it only proves that that the solution is not total nonsense, not that it is correct.<BR/><BR/><I><BR/>how do you know that it's optimal to NOT sacrifice a dwarf if you don't have to?<BR/></I><BR/>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)<BR/><BR/>A sketch of the proof:<BR/>Assume that the list is sorted as before.<BR/><BR/>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.<BR/>We can drop the dwarves that were sacrificed by both solutions and assume that the sets of indexes are disjoint.<BR/><BR/>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.<BR/><BR/>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.<BR/><BR/>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!).<BR/>And b[1] was selected as the tallest guy among [i..n].<BR/>---<BR/><BR/>Here is my <A HREF="http://snipplr.com/view/6924/dwarves-solution/" REL="nofollow"><BR/>code</A>.<BR/><BR/>Was the intended solution dynamic programming? If there is O(n^2) DP solution, I need to think more.<BR/><BR/>PS<BR/>In my first comment I use dwarve as a singular for dwarf, but now I cannot edit it. Sorry for that. :)u1ikhttps://www.blogger.com/profile/02296174044975315907noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-8874404410994643842008-06-26T04:14:00.000-04:002008-06-26T04:14:00.000-04:00The test data is here.Format:n (n ≤ 2000)h1 ...The test data is <A HREF="http://www.liis.ro/~lotinfo2008/probleme/pitici.zip" REL="nofollow">here</A>.<BR/><BR/>Format:<BR/>n (n ≤ 2000)<BR/>h1 l1<BR/>...<BR/>hn ln<BR/>H<BR/><BR/><BR/>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.Mihaihttps://www.blogger.com/profile/11599372864611039927noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-57921754214541674782008-06-26T04:10:00.000-04:002008-06-26T04:10:00.000-04:00u1ik, how do you know that it's optimal to NOT sac...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.Mihaihttps://www.blogger.com/profile/11599372864611039927noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-37915098098202158402008-06-26T03:57:00.000-04:002008-06-26T03:57:00.000-04:00Alexander, I disagree with the idea that you have ...Alexander, I disagree with the idea that you have to find R, as you defined it.<BR/><BR/>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.<BR/><BR/>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.Mihaihttps://www.blogger.com/profile/11599372864611039927noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-67781013474820195062008-06-25T14:52:00.000-04:002008-06-25T14:52:00.000-04:00Proof by implementation :) (Sources are available)...<A HREF="http://radu.ucd.ie/temp/mip/dwarves_0.pdf" REL="nofollow">Proof</A> <A HREF="http://radu.ucd.ie/temp/mip/dwarves_1.pdf" REL="nofollow">by</A> <A HREF="http://radu.ucd.ie/temp/mip/dwarves_2.pdf" REL="nofollow">implementation</A> :) (Sources are <A HREF="http://radu.ucd.ie/temp/mip/" REL="nofollow">available</A>).rgrighttps://www.blogger.com/profile/02991214367108471744noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-7000941386434262902008-06-25T12:20:00.000-04:002008-06-25T12:20:00.000-04:00Nice problem, Mihai. Would you mind posting a link...Nice problem, Mihai. Would you mind posting a link to the test data (if available)? So that we could check correctness of our solutions.<BR/><BR/>My approach is greedy.<BR/><BR/>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.<BR/><BR/>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.<BR/><BR/>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:<BR/><BR/>h_s = 0<BR/>(h_s -- sum of the heights of the sacrificed dwarves)<BR/><BR/>for i = n to 1<BR/> h_p = sum(h[j] | 1 <= j < i)<BR/> if (h[i]+l[i]+h_s+h_p < H)<BR/> begin<BR/><I><BR/> this means that i-th dwarve cannot escape, we must sacrifice at least one dwarve.<BR/><BR/> find the dwarve k (i <= k <= n) among the unsacrificed dwarves with the maximum height (greedy!).<BR/><BR/> mark the k-th dwarve as sacrificed and set h_s = h_s + h[k]. <BR/></I><BR/> end<BR/><BR/>The complexity is O(n^2). Could be made O(nlogn) with priority queue.u1ikhttps://www.blogger.com/profile/02296174044975315907noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-58318747527836157972008-06-25T08:03:00.000-04:002008-06-25T08:03:00.000-04:00alexander: my solution is a bit different from you...alexander: my solution is a bit different from yours.<BR/><BR/>say if H=10. <BR/>h1=7,l1=0<BR/>h2=4,l2=1<BR/>h3=1,l3=1<BR/>According to your assumption R={1} cannot be a rescue team as<BR/>h1+min(h2+l2,h3+l3)=9 is not greater than 10.<BR/><BR/>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. <BR/><BR/>so the confusion may be regarding what i understood the problem as.ashwin kumar b vhttps://www.blogger.com/profile/07777870747608944808noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-69392128807973979172008-06-25T06:50:00.000-04:002008-06-25T06:50:00.000-04:00Let me explain my solution.Let us call a set of dw...Let me explain my solution.<BR/><BR/>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.<BR/><BR/>Obviously $R$ is a rescue team iff:<BR/><BR/>$$<BR/>\sum_{i \in R} h_i + \min_{j \notin R} (h_j + l_j) \geq H<BR/>$$<BR/><BR/>this is essentially a definition of $R$ re-written as formula.<BR/><BR/>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.)<BR/><BR/>Straightforward algorithm enumerates all possible rescue teams $R$ and finds the smallest one. It has exponential execution time.<BR/><BR/>However, smallest rescue team can be found much faster.<BR/>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)$.<BR/><BR/>We will enumerate all possible values of $j(X)$ from $n$ till $1$.<BR/>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.<BR/><BR/>It looks like, that efficient implementation of this algorithm will have $O(n \log n)$ comparisons and $O(n^2)$ additions.<BR/><BR/>I have a slight suspicion that this is what ashwinkumar was trying to explain.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-68173182715006523492008-06-25T05:17:00.000-04:002008-06-25T05:17:00.000-04:00Since we are talking past each other, I suggest we...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.<BR/><BR/>Your solution needs to guarantee that all dwarves who have supposedly escaped can in fact escape. The ones remaining (with <I>i</I> on top) cannot guarantee that all other escape. The order in which they escape also matters, for instance.Mihaihttps://www.blogger.com/profile/11599372864611039927noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-83546669863133265412008-06-25T05:12:00.000-04:002008-06-25T05:12:00.000-04:00As, i had mentioned. i is a loop variable from i t...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). <BR/><BR/>i-th person is at the top when all dwarfs have escaped. (You can consider the arrangment when the last dwarf has left)ashwin kumar b vhttps://www.blogger.com/profile/07777870747608944808noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-81944510055895036402008-06-25T05:05:00.000-04:002008-06-25T05:05:00.000-04:00I agree with the case when all li=0. No problem.I ...I agree with the case when all <I>li</I>=0. No problem.<BR/><BR/>I do not agree with the second part. What do you mean by "the <I>i</I>-th person is at the top"? At the top when? Many dwarves can escape. Which one is <I>i</I>?Mihaihttps://www.blogger.com/profile/11599372864611039927noreply@blogger.com