wu :: forums - Print Page


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

        riddles >> cs >> Trip problem
        
(Message started by: witee on Apr 2^nd, 2010, 5:21am)

Title: Trip problem
Post by witee on Apr 2^nd, 2010, 5:21am

You are starting out on a long (really long) trip. On the way, there are N gas stations, the locations of which are given as a_1,a_2,...,a_N. Initially you are located at the gas station at a_1, and your destination is at location a_N. Your car can only store enough fuel to travel atmost M units without refilling. You can stop at any station and refill the car by any amount. Now you wish to plan your trip such that the number of intermediate stops needed to reach the destination is minimum, and also how many ways are there to plan your trip accordingly. :o

how to do that ..any idea?

Title: Re: Trip problem
Post by towr on Apr 2^nd, 2010, 6:11am

[hide]Keep a counter for each station, initialized to 0; set the counter for the first one to 1.
For each station find the (later) stations within M units distance and add to their counter the value of the counter of the station you're processing.

This is assuming you're only going forward. If the stations aren't on a fixed route and you can go in circles, well, then if there's any way to get to the end there's an infinite number of ways. So clearly that can't be intended.[/hide]

Title: Re: Trip problem
Post by sateesp on Apr 2^nd, 2010, 7:53am

I think we can use Greedy Strategy here. We need to minimize the number of intermediate stops.
So we start with full tank.
At each station, we will make a following decision. “We will stop at the gas station only when we can’t reach next station with available fuel

Title: Re: Trip problem
Post by witee on Apr 2^nd, 2010, 11:15am

can u explain with the below example..

n=6 m=3
a_1=0
a_2=1
a_3=3
a_4=4
a_5=7
a_6=10

what is the answer 4 this example?

Title: Re: Trip problem
Post by sateesp on Apr 3^rd, 2010, 11:21am

I assume, the value of a_i is the distance between the starting point to this gas station.
So, initially we start from the gas station a_1 and we will fill tank completely. I can go to till a_3 without refilling.
Filling will happen at a_3, fill tank with 3 liters
Filling will happen at a_4, fill tank with 1 liter
Fill will happen at a_5, fill tank with 3 liters.

We need to stop at 4 stations before we reach the destination.

Title: Re: Trip problem
Post by witee on Apr 4^th, 2010, 4:24am

answer is 3!!

Title: Re: Trip problem
Post by towr on Apr 4^th, 2010, 6:30am

on 04/04/10 at 04:24:46, witee wrote:

answer is 3!!

4 if you count the first station.
As you can read, he only fills up during the trip in a3, a4 and a5. But you do need to start the trip with a full tank as well, so it makes sense to count filling up at a1.

Title: Re: Trip problem
Post by witee on Apr 4^th, 2010, 6:58am

@towr...
ok i am agree wid ur solution..
but can u explain the approach u suggested above on the example i supplied 2 u?

Title: Re: Trip problem
Post by towr on Apr 4^th, 2010, 7:20am

My approach gives the total number of ways to get from a1 to a6 (and every place in between)

1,0,0,0,0,0, one way to get at a1, since it's simply where you start
1, 1,1,0,0,0, from a1 you can get to a2 and a3
1,1, 2,1,0,0, from a2 you can get to a3 and a4, since there's one way to get to a2 there's one extra way to get to each of those
1,1,2, 3,0,0 from a3 you can only get to a4, since there are two ways to get to a3 there are two extra ways to get to a4
1,1,2,3, 3,0 from a4 you can only get to a5, since there are three ways to get to a4 there are three ways to get to a5
1,1,2,3,3, 3 from a5 you can only get to a6, since there are three ways to get to a5 there are three ways to get to a6

So there are three ways to get from a1 to a6
a1 -> a2 -> a3 -> a4 -> a5 -> a6
a1 -> a2 -> a4 -> a5 -> a6
a1 -> a3 -> a4 -> a5 -> a6

Title: Re: Trip problem
Post by witee on Apr 5^th, 2010, 1:55pm

bt ur approach will fail if i/p is

n=6, m=3
0
1
2
3
4
5

ur solution is giving 13 answer bt coreect answer is 2 only(couting initial position also)

correct me if i am wrong

Title: Re: Trip problem
Post by towr on Apr 5^th, 2010, 3:00pm

There's a lot more than just two ways to get to the end in that example.

Title: Re: Trip problem
Post by witee on Apr 5^th, 2010, 10:47pm

In the question we have to find the minimum destination path!!!

Title: Re: Trip problem
Post by malchar on Apr 6^th, 2010, 12:08am

Quote:

and also how many ways are there to plan your trip accordingly.

For starters, whenever you reach a gas station but still have some fuel left in the vehicle, you could have gotten that much less fuel at your last stop and instead gotten that much at the station you're at now. You can also split this amount into whatever smaller chunks are allowed and divide the fuel between the station you're at now and the station you just left.

Title: Re: Trip problem
Post by towr on Apr 6^th, 2010, 12:49am

on 04/05/10 at 22:47:47, witee wrote:

In the question we have to find the minimum destination path!!!

You asked two things in your problem, how to find a minimum paths, and how many paths there are.

Title: Re: Trip problem
Post by witee on Apr 6^th, 2010, 5:12am

@towr..

how many paths which uses minimum number of intermediate stops(found in part 1)??this is the 2nd part ?

Title: Re: Trip problem
Post by towr on Apr 6^th, 2010, 5:22am

Ah, I misunderstood..

Well, I suppose you can use dynamic programming. You can first use the greedy approach to find the minimum number of steps, then build a table that keeps for each station the number of ways up to min_steps it takes to get there.
Actually, you can do better, because for each station there is just one minimum number of steps to get there; if you take longer to get to that station, you'll take longer to get to a later station through there. So you can just keep the minimum number of steps for each station and how many ways to get there by that number of steps.

Title: Re: Trip problem
Post by witee on Apr 6^th, 2010, 6:31am

@towr
can u explain/give the pseudo code the table making part(if we have found the minimum number of steps).
i.e finding the number of ways part..and it should be efficient 1(DP implementation).

Title: Re: Trip problem
Post by towr on Apr 6^th, 2010, 8:45am

It's basically the same as what I said before, except now you keep track of the number of steps.
If you can get two a[i] in x steps, and you can get to a[j] from a[j], then you can get to a[j] in x+1 steps.
So add the number of ways you can get to a[i] in x steps, to the number of ways you could already get to a[j] in x+1 steps.

If we take the previous example again
n=6 m=3
a_1=0
a_2=1
a_3=3
a_4=4
a_5=7
a_6=10

you get
in 0 steps: 1,0,0,0,0,0
in 1 steps: 0,1,1,0,0,0
in 2 steps: 0,0,1,2,0,0
in 3 steps: 0,0,0,1,2,0
in 4 steps: 0,0,0,0,1,2 <-- that 2 is all the ways to get to the end in the minimum number of steps
in 5 steps: 0,0,0,0,0,1

Title: Re: Trip problem
Post by witee on Apr 6^th, 2010, 10:25am

@towr

sorry towr iam not able to understand your approach...explain with this example

n=6 m=3;
0
1
2
3
4
5

Title: Re: Trip problem
Post by witee on Apr 9^th, 2010, 9:52pm

@towr

Your method is giving TLE,how to do Top to Down DP
instead of bottom to Up DP.that is the efficient 1!!

Title: Re: Trip problem
Post by towr on Apr 10^th, 2010, 4:14am

What is "TLE"?

Title: Re: Trip problem
Post by witee on Apr 10^th, 2010, 5:24am

Time Limit Exceeded i.e the time assigned for the solution for some input data.

Title: Re: Trip problem
Post by towr on Apr 10^th, 2010, 2:31pm

How did you implement it?
Because you only need to keep two rows at a time, and only need to keep a stretch of at most m elements in a row (if two stations are more than m apart, you can't get from the first to the end in as few steps as from the last).

Title: Re: Trip problem
Post by witee on Apr 13^th, 2010, 4:01pm

@towr

thanx .. finally i got accepted!!!

Title: Re: Trip problem
Post by jack_alyz on Aug 31^st, 2010, 5:02am

Easier way to understand this problem:
1. consider every station as node in graph.
2. Draw edge i->j , where i<j and a[j]-a[i] <= M
3. write DP recursion as
S(n) = 1+min { i s.t. (i,n) \in E} S(i)

answer is S(n)-1, as it would suggest to refuel at nth station, which is not required given we already reached to a_n.