|
Hello everyone,
I have been struggling since previous month about some question that I found on some university,
and I just cant think about a good way to solve it.
Please, help me to think about a way to solve this question.
The most important thing is that the solution has to work as fast as it can with the lowest complexity
that possible.
The question :
Quote: Vik the puffin is planning a long road trip around the circle road in Iceland, during which he wants to visit
all the landmarks along a path of length L. The tank of Vik's car can take up to F units of fuel and for every
unit of distance covered, his car consumes a unit of fuel. Using Google maps, Vik knows how far each of
the N gas stations are from the beginning of the path and the price per fuel unit each station offers. At the
starting point he has T units of fuel in his car.
1. Task
Write a program that will accept the above information and will calculate the minimum amount of money
Vik needs to spend on gas. If the journey is impossible to make, it should print -1.
2. Input
The first line contains four space separated integers:
N (0 < N < 50001): The total number of gas stations
F (0 < F < 1000001): The units of fuel Vik's car can take
T (0 <= T <= F): The units of fuel Vik's car has at the beginning of the trip
L (0 < L < 1000000001): The path length of the landmarks he plans to visit
Each of the following N lines will contain two integers: the first one, D_i (0 <= D_i <= L) corresponds
to the distance of the station from the starting point, and the second one, C_i (1 <= C_i <= 1,000,000)
represents the cost per fuel unit for that station.
Note: You may assume that the trip will be on a straight line where all gas stations are
spread on this line at the positions specified by their D_i values.
3. Output
The minimum amount of money to be spent or with -1 in case the trip is not feasible.
Note: There is a newline character at the end of the last line of the output.
4. Sample input
4 20 6 34
4 40
18 15
10 7
20 12
2
5. Sample output
348
6. Explanation
The rst line of the input is 4 20 6 34 which means that:
a. There are in total N=4 gas stations on the route
b. The (max) fuel capacity of Vik's car is F=20 liters
c. The tank currently has T=6 liters of gas
d. Vik wants to travel L=34 kms in total
Then the details for the 4 gas stations are provided in the form Di Ci, where Di is the distance of this
gas station from the starting point and Ci is the cost per liter of gas:
4 40
18 15
10 7
20 12
For simplicity assume that the whole trip is done in a straight line as depicted below:
link to show the trip from the example -> Vik The Puffin — imgbb.com[^]
Obviously Vik does not have enough fuel for all 34 kms, so he needs to refuel. The cheapest gas station is
the one labeled (B) above, however Vik does not (initially) have enough fuel in his tank to reach (B), since
B-S = 10 and he has T=6. So he needs to add an extra 4 liters from gas station A, so that he can the make
it until gas station B to get as much (cheap) as he can in order to make his 34 km journey. Thus he pays
(i) 4lt * 40$/lt = 160¿ and now he can make it until (B). Since until this moment he has only traveled
10 kms, he needs gas for another 34-10=24kms. Normally he would want to refuel his car with 24 liters
(since B is the cheapest gas station) but since his (max) fuel capacity is F=20 liters he will only take 20
liters and thus pay (ii) 20 lt * 7 $/lt = 140$. He knows however that up to point (B) he has only traveled
10kms and he needs to travel another 24kms to reach his goal, whereas he has gas for 20kms. So he would
have to stop at a later gas station (after he has traveled at least 4kms) to refuel another 4 liters of gas so
that he could complete the whole 34 kms journey. Since he now has quite some gas, he may decide whether
he wants to refuel at (C) or at (D) and since (D) is cheaper, it is more than 4kms away from (B) and is
within reach (based on his gas in the tank) he will choose to refuel another 4 liters at (D) and thus pay (iii)
4lt*12$/lt=48$). After that he can successfully reach the end point of his trip.
PLEASE HELP ME WITH THIS!
Thanks in advance!
|
|
|
|
|
Quote: The most important thing is that the solution has to work as fast as it can with the lowest complexity
that possible.
I think the most important thing is that the solution "works"; worry about performance later.
Try a flow chart.
"(I) am amazed to see myself here rather than there ... now rather than then".
― Blaise Pascal
|
|
|
|
|
Member 13870192 wrote: I have been struggling since previous month about some question that I found on some university,
..but mysteriously cannot link to..
It's a straightforward problem. Create a class called Vic, and have him go on each possible route, calculating the costs on the way. Select the cheapest, and done. It is a naive brute-force solution that I called "travelling Orca's". Since it resembles having an Orca in a Taxi take the actual route and phone back the results. Is as quick and efficient as the name suggests, but it works, and is a very good starting point to explain possible optimizations.
Member 13870192 wrote: The most important thing is that the solution has to work as fast as it can with the lowest complexity
that possible.
The TSP thingy has been done to death. If you skipped class, that's your problem. You are fishing for free labor.
Bastard Programmer from Hell 
If you can't read my code, try converting it here[^]
"If you just follow the bacon Eddy, wherever it leads you, then you won't have to think about politics." -- Some Bell.
|
|
|
|
|
Member 13870192 wrote: The most important thing is that the solution has to work as fast as it can with the lowest complexity
that possible.
This question comes from a challenge site, the challenge is that you find a solution, your solution.
Your solution always start with a sheet of paper and a pencil, then you solve the problem by hand.
As you solve the problem by hand, write down how you make decisions to get to solution.
Then try the example and another order of stations in increasing order, then in decreasing order, solve by hand, compare with your procedure, improve the procedure if not optimum.
that procedure will be your program.
If you are unable to solve the problem, you will need to study data structures and algorithms.
Patrice
“Everything should be made as simple as possible, but no simpler.” Albert Einstein
|
|
|
|
|
In particular I need tutorials on heuristic algorithms concerning graphs like pagoda function, bidirectional search etc. Also heuristic algorithms not concerning graphs. Introduction, pseudocode minimal amount of mathematics. In pdf or web page free of charge.
|
|
|
|
|
I usually only have time for one tutorial.
You will need to prioritize your requested items.
"(I) am amazed to see myself here rather than there ... now rather than then".
― Blaise Pascal
|
|
|
|
|
Create a block diagram or a pseudocode of an algorithm checking the balance of html tags. Include self-closing tags and tags with attributes.
I need suggestions on how to begin this task.
|
|
|
|
|
You begin by defining what you have to look for. That are - Opening tags <name[ attributes]>
- Closing tags </name>
- Self-closing tags <name[ attributes] />
Then think about how you can detect the above and what you have to do with them. For self-closing tags it is obvious that these can be simply skipped. For opening tags you have to find the corresponding closing tag and check if they are on the same level. Such can be done by pushing an open sequence onto a stack and popping upon a closing sequence after checking for identical names.
|
|
|
|
|
Read forward for an opening tag.
Locate the first closing tag that matches; if there is another "same" opening tag before the target closing, then error.
If closing found, locate next opening after previous opening and repeat; else error.
"(I) am amazed to see myself here rather than there ... now rather than then".
― Blaise Pascal
|
|
|
|
|
Gerry Schmitz wrote: if there is another "same" opening tag before the target closing, then error.
That's not how HTML works. 
<div>
<div>
<div>
This is perfectly valid HTML.
</div>
</div>
</div>
"These people looked deep within my soul and assigned me a number based on the order in which I joined."
- Homer
|
|
|
|
|
<!-- You forgot a <div>! -->
Bastard Programmer from Hell
If you can't read my code, try converting it here[^]
"If you just follow the bacon Eddy, wherever it leads you, then you won't have to think about politics." -- Some Bell.
|
|
|
|
|
And also:
<script>
var closingTag = "</div>";
var openingTag = "<div>";
</script> which is still perfectly balanced HTML. 
"These people looked deep within my soul and assigned me a number based on the order in which I joined."
- Homer
|
|
|
|
|
OP is probably expecting a simple solution, given the description of the problem. HTML looks simple enough, but even if one only takes valid HTML into account, there are a lot of rules one might break.
The easiest way to see if it matches up might be by simply rendering it and seeing if there's an exception. The neat (read as "expensive") way would be an interpreter-pattern.
Bastard Programmer from Hell
If you can't read my code, try converting it here[^]
"If you just follow the bacon Eddy, wherever it leads you, then you won't have to think about politics." -- Some Bell.
|
|
|
|
|
I took a chance and "assumed" their "test data" would be relatively "simple".
While your example is valid, it's also not "fair".
(At times I see code that I wouldn't touch without rewriting it first).
"Fringe cases" can be dealt with easier once one has "something" going (which is usually my objective).
"(I) am amazed to see myself here rather than there ... now rather than then".
― Blaise Pascal
|
|
|
|
|
Gerry Schmitz wrote: While your example is valid, it's also not "fair".
I challenge you to find any non-trivial HTML page which doesn't include nested <div> tags.
Maybe the OP should use Regular Expressions[^] instead. 
"These people looked deep within my soul and assigned me a number based on the order in which I joined."
- Homer
|
|
|
|
|
Part 2 would have been:
Read reverse.
Locate inner block.
Remove block.
Repeat.
(From my Wiki "non-trivial" page scraper and Flesch Reading Gunning FOG Index calculator. It also removed "malformed" HTML).
"(I) am amazed to see myself here rather than there ... now rather than then".
― Blaise Pascal
modified 6-Jun-18 12:41pm.
|
|
|
|
|
Just curious if RBFS can be used in pathfinding scenario such as a map with obstacles between location A and B? I am doing an experiment and the result shows that for some situations RBFS is able to find the path but for others it is not, even there are paths available.
|
|
|
|
|
By definition, a path is not a path if there is an "obstacle" (that cannot be overcome).
(Unless one considers / programs a "dead-end" as a "branch" / u-turn).
"(I) am amazed to see myself here rather than there ... now rather than then".
― Blaise Pascal
|
|
|
|
|
It is a normal behaviour as RBFS is heuristic, so it discards some branches of the solution tree which may contain the solution. There are some heuristic algorithms, also for some graph problems, that find a solution which is not optimal but they at least find something close to the solution, which is satisfactory, whereas the other heuristic algorithms, when they miss the solution path, they will give you no results.
For finding paths in graphs, heuristic algorithms should be used only if you do not have enough memory for a regular BFS. They usually provide no solution if they miss them. I am now writing solving diamond peg solitaire with BFS, which should be ready within a couple of days on my site
informatyka-delphi.blogspot.com
If I am lucky, the graph will have up to 15 GB, compressed graph 4GB, so I shall find the solution with BFS.
|
|
|
|
|
I am trying to develop an algorithm which will be able to find minimum spanning tree from a graph.I know there are already many existing algorithms for it.However I am trying to eliminate the sorting of edges required in Kruskal's Algorithm.The algorithm I have developed so far has a part where counting of disjoint sets is needed and I need a efficient method for it.After a lot of study I came to know that the only possible way is using BFS or DFS which has a complexity of O(V+E) whereas Kruskal's algorithms has a complexity of O(ElogE).Now my question is which one is better,O(V+E) or O(ElogE)?
|
|
|
|
|
It seems reasonable to simply test both options instead of depending on hearsay.
Unlesss it's not that important; then just flip a coin.
"(I) am amazed to see myself here rather than there ... now rather than then".
― Blaise Pascal
|
|
|
|
|
Depends on how dense the graph is.
|
|
|
|
|
Hello,
Last week I studied aes gcm in lectures. But I fail to understand. Can anyone help to make me understand? Perhaps with explanations or schematic drawings. Thank you
|
|
|
|
|
|
On the link which you have shown all the explanations just discuss aes. Is aes gcm same with aes?
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
