Author |
Topic: Trip problem (Read 3002 times) |
|
witee
Newbie
Posts: 48
|
 |
Trip problem
« on: Apr 2nd, 2010, 5:21am » |
 Quote  Modify
|
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. 
how to do that ..any idea?
|
|
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender: 
Posts: 13730
|
|
Re: Trip problem
« Reply #1 on: Apr 2nd, 2010, 6:11am » |
Quote Modify
|
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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
sateesp
Newbie
Gender:
Posts: 35
|
|
Re: Trip problem
« Reply #2 on: Apr 2nd, 2010, 7:53am » |
Quote Modify
|
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
|
|
IP Logged |
|
|
|
witee
Newbie
Posts: 48
|
|
Re: Trip problem
« Reply #3 on: Apr 2nd, 2010, 11:15am » |
Quote Modify
|
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?
|
|
IP Logged |
|
|
|
sateesp
Newbie
Gender:
Posts: 35
|
|
Re: Trip problem
« Reply #4 on: Apr 3rd, 2010, 11:21am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
witee
Newbie
Posts: 48
|
|
Re: Trip problem
« Reply #5 on: Apr 4th, 2010, 4:24am » |
Quote Modify
|
answer is 3!!
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Trip problem
« Reply #6 on: Apr 4th, 2010, 6:30am » |
Quote Modify
|
on Apr 4th, 2010, 4:24am, witee wrote: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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
witee
Newbie
Posts: 48
|
|
Re: Trip problem
« Reply #7 on: Apr 4th, 2010, 6:58am » |
Quote Modify
|
@towr...
ok i am agree wid ur solution..
but can u explain the approach u suggested above on the example i supplied 2 u?
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Trip problem
« Reply #8 on: Apr 4th, 2010, 7:20am » |
Quote Modify
|
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
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
witee
Newbie
Posts: 48
|
|
Re: Trip problem
« Reply #9 on: Apr 5th, 2010, 1:55pm » |
Quote Modify
|
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
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Trip problem
« Reply #10 on: Apr 5th, 2010, 3:00pm » |
Quote Modify
|
There's a lot more than just two ways to get to the end in that example.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
witee
Newbie
Posts: 48
|
|
Re: Trip problem
« Reply #11 on: Apr 5th, 2010, 10:47pm » |
Quote Modify
|
In the question we have to find the minimum destination path!!!
|
|
IP Logged |
|
|
|
malchar
Junior Member
Gender:
Posts: 54
|
|
Re: Trip problem
« Reply #12 on: Apr 6th, 2010, 12:08am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Trip problem
« Reply #13 on: Apr 6th, 2010, 12:49am » |
Quote Modify
|
on Apr 5th, 2010, 10:47pm, 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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
witee
Newbie
Posts: 48
|
|
Re: Trip problem
« Reply #14 on: Apr 6th, 2010, 5:12am » |
Quote Modify
|
@towr..
how many paths which uses minimum number of intermediate stops(found in part 1)??this is the 2nd part ?
|
| « Last Edit: Apr 6th, 2010, 5:13am by witee » |
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Trip problem
« Reply #15 on: Apr 6th, 2010, 5:22am » |
Quote Modify
|
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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
witee
Newbie
Posts: 48
|
|
Re: Trip problem
« Reply #16 on: Apr 6th, 2010, 6:31am » |
Quote Modify
|
@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).
|
| « Last Edit: Apr 6th, 2010, 6:32am by witee » |
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Trip problem
« Reply #17 on: Apr 6th, 2010, 8:45am » |
Quote Modify
|
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
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
witee
Newbie
Posts: 48
|
|
Re: Trip problem
« Reply #18 on: Apr 6th, 2010, 10:25am » |
Quote Modify
|
@towr
sorry towr iam not able to understand your approach...explain with this example
n=6 m=3;
0
1
2
3
4
5
|
|
IP Logged |
|
|
|
witee
Newbie
Posts: 48
|
|
Re: Trip problem
« Reply #19 on: Apr 9th, 2010, 9:52pm » |
Quote Modify
|
@towr
Your method is giving TLE,how to do Top to Down DP
instead of bottom to Up DP.that is the efficient 1!!
|
|
IP Logged |
|
|
|
witee
Newbie
Posts: 48
|
|
Re: Trip problem
« Reply #21 on: Apr 10th, 2010, 5:24am » |
Quote Modify
|
Time Limit Exceeded i.e the time assigned for the solution for some input data.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Trip problem
« Reply #22 on: Apr 10th, 2010, 2:31pm » |
Quote Modify
|
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).
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
witee
Newbie
Posts: 48
|
|
Re: Trip problem
« Reply #23 on: Apr 13th, 2010, 4:01pm » |
Quote Modify
|
@towr
thanx .. finally i got accepted!!!
|
|
IP Logged |
|
|
|
jack_alyz
Newbie
Posts: 8
|
|
Re: Trip problem
« Reply #24 on: Aug 31st, 2010, 5:02am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print