principleMinor
Find a strategy to evade hungry lions on the real line for the longest time
Viewed 0 times
realfindthehungrylionslineevadetimeforstrategy
Problem
This is an interview question I was asked, which I don't know how to approach. I would appreciate pointers to algorithms I should look up.
You are placed on the real line, and there also are $K$ lions on the real line, which are currently sleeping. You are given the wake up time of each lion. You can walk past a lion as long as it is sleeping. As soon as any lion wakes up, it starts walking towards you to eat you. Both you and the lions can walk at a maximum speed of 1m/s.
Given your starting position and the starting positions and wake up times of the lions, find the maximum time you can stay alive (can be infinite), and the strategy you should follow.
You are placed on the real line, and there also are $K$ lions on the real line, which are currently sleeping. You are given the wake up time of each lion. You can walk past a lion as long as it is sleeping. As soon as any lion wakes up, it starts walking towards you to eat you. Both you and the lions can walk at a maximum speed of 1m/s.
Given your starting position and the starting positions and wake up times of the lions, find the maximum time you can stay alive (can be infinite), and the strategy you should follow.
Solution
Assume you start at zero. Lion #i is at $d_i$ and wakes up at $w_i$. If there is no lion with $d_i > 0$ and $w_i 0$ and $w_i < d_i$ then you can walk only $(d_i + w_i)/2$ before you are forced back.
Just check the points X that are just before a sleeping lion, or just before one of the two points where you are forced back. For each of these points X, calculate at which time you will die, and pick the best one.
(To make this easier to visualise: If all lions wake up at the same time, and you can't escape, then you want to be within the largest gap between two lions that you can reach, at the moment they wake up. So the point to move to could be anywhere, depending on where the lions are).
Just check the points X that are just before a sleeping lion, or just before one of the two points where you are forced back. For each of these points X, calculate at which time you will die, and pick the best one.
(To make this easier to visualise: If all lions wake up at the same time, and you can't escape, then you want to be within the largest gap between two lions that you can reach, at the moment they wake up. So the point to move to could be anywhere, depending on where the lions are).
Context
StackExchange Computer Science Q#100234, answer score: 2
Revisions (0)
No revisions yet.