wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> microsoft >> A culprit is on run
        
(Message started by: Eros on Jul 7^th, 2005, 8:27am)

Title: A culprit is on run
Post by Eros on Jul 7^th, 2005, 8:27am

A culprit is on run in a Porche (which has a cruise control) on a desert highway(the highway is of infinite length and with no other traffic ;) ). Our job is to catch him by laying a trap.
At every km from the start of the highway we have sensors and trap deployers. The sensors can be polled just once which will render them useless. The sensor can be just be polled to see whether the car has passed it or not (mind u the sensors will return only true or false). We have a 10 secs time interval for making the trap deployment successful. If the trap is deployed early the car will notify the culprit who will change the course and will be gone for ever.
So a strategy has to be devised to catched the culprit.

Title: Re: A culprit is on run
Post by River_Phoenix on Jul 7^th, 2005, 2:29pm

I believe this (complicated) method would work:

[hide]First trip sensors going forward until you find one which the car hasn't hit yet. So the car is in between sensors n-1 and n. Then, wait 30 seconds and try the (n+1)th sensor. If the car is past this, then we know that the car is going 1K in no more than 30 seconds. Otherwise, the car is 2K in no less than 30 seconds (1K in no less than 15 seconds). Then do a similar thing, jumping ahead 1.x sensors, and using different times. We can find an upper and lower bound on the amount of time it takes the car to travel 1K. Then we can use these to get the speed of the car in seconds/K as accurately as we want by waiting a set length of time and seeing where the car is (error bounds are 2K per that given time, since we can only determine which two markers a car is Between) -- I figured out a way on paper to get it "within epsilon". Then we can calibrate by taking the time for the car to travel 1 sensor, and add a second and subtract a second. Then go back and forth switching sensors at intervals alternating with these two times, until every other sensor is returning false. So we are within a second. Finally, wait the time for the car to travel 1 sensor, minus 5 seconds. Trip the trap![/hide]