Thanks, that was cute. Offer something more challenging. :)
dunno if i'm allowed to post it here but anyways...
1 and 2 cross... 1 comes back... 5 and 10 cross... 2 comes back... 1 and 2 cross... key is to make sure that the second slowest gets masked by the lowest!
what is the generalization of this probelm?
yup, that's it :)
think of n people with speeds a_1, a_2, ... a_n
is there an algorithm that finds the minimum time to cross, given the speeds as input?
From: (Anonymous) 20070714 05:05 am (UTC)
 (Link)

I am guessing that perhaps it can be solved by greedy appproaches. If not, then its probably an interesting problem for a STOC/FOCS paper (prove NPcomplete, prove hard to approximate using PCP etc) :)
Vipul
"If not, then its probably an interesting problem for a STOC/FOCS paper"
I hope not! I'd like to think STOC and FOCS publish less frivolous stuff :)
From: (Anonymous) 20070716 09:35 pm (UTC)
 (Link)

Frivolousness is subjective. What do you think of "Cake cutting really is not a piece of cake"? :)
vinod
From: (Anonymous) 20070719 06:14 pm (UTC)
Alternate  (Link)

How about the following? 1 and 2 cross, 2 comes back, 5 and 10 cross, 1 comes back and then 1 and 2 cross (2 + 2 + 10 + 1 + 2 = 17) In the general case, there might be lots of optimal solutions. 