-2

I have been stuck on this question for some time. Could you guys direct me or point me to the right direction for solving this problem ?

We would like to encourage passengers to experience the joy of travel using our transit system, therefore we would like to determine the longest path available to advertise the public. Specifically we would like to determine the longest possible trip on the transit system that will involve TWO tickets. The destinations must be connected, and all destinations must be unique.

You will be provided input in the format of CHI:NYC:719 where CHI is one location, NYC is a connected location and 719 is the distance between the locations.

one line of output should be provided per line of input in the format of 3167:CHI:NYC:LA where 3167 is the distance of the trip, CHI is the starting, NYC is the intermediary location and LA is the final location.

sequence-------input---------------------------output

1------------------CHI:NYC:719----------------NONE

2------------------NYC:LA:2414----------------3133:CHI:NYC:LA

3------------------NYC:SEATTLE:2448------4862:LA:NYC:SEATTLE

4------------------NYC:HAWAII:4924---------7372:HAWAII:NYC:SEATTLE

Note: the start and end cities are lexicographical sorted.

closed as too broad by gnat, Doc Brown, Jörg W Mittag, Thomas Owens Nov 12 '18 at 11:32

Please edit the question to limit it to a specific problem with enough detail to identify an adequate answer. Avoid asking multiple distinct questions at once. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • See Graph Traversal – candied_orange Nov 11 '18 at 19:37
  • Since the inputs are given line by line I have to recalculate the distance over and over again. Seems more like an overkill. Is there a better approach ? I thought of using a dictionary to keep track of the furthest city for each of the city and update it as new cities come. – NoobieCoder3 Nov 11 '18 at 20:30
  • 2
    recommended reading: Open letter to students with homework problems "If your question... is just a copy paste of homework problem, expect it to be downvoted, closed, and deleted - potentially in quite short order." – gnat Nov 11 '18 at 20:43
  • This is one of those problems that more than likely requires searching the (whole) solution space. So, you try one solution, compute the distance, then try a variation. When trying solutions, keep the longest one you've seen so far, and in the end, that is the answer. Yes, there are optimizations you can perform to avoid repeated work. Though, i would offer that the real work here goes to searching of the solution space to identify solutions, rather than computing of summed distances for a given solution (i.e. don't worry about that until you have a proper solution search algorithm). – Erik Eidt Nov 11 '18 at 21:27
  • 2
    @NoobieCoder3 We don't support questions that require reading the comments to answer. Edit your question so it reflects the approach you mentioned in your comment and you'll have shown some modest effort (which we require on homework problems). – candied_orange Nov 11 '18 at 22:40
0

Technically this is not an answer to your basic question. This is an answer to your actual question which is: How do I think about this problem, surely there is a better way than brute force?

As with any problem think how you would do this yourself.

You've been given a list of connections and distances that would be traveled on them. Which connection would give you the greatest chance of being apart of the longest two connection route?

You could pick the smallest, but that would only contribute a little distance to the total traveled. How about picking the biggest? Would that be more effective?

Okay so now is the job done? No. You need another connection - but how to pick it? should you pick the next smallest, or the next largest? Is there some other property that needs to hold, oh look one city must be shared between the two edges. So can you pick the same edge? No.

Hmm, so grab all the edges that connect to the first or last city. Wait that includes the first edge, okay get rid of that edge. Now which edge should be picked? The smallest, or the biggest?

Are you done now? You've got two edges, they connect to each other. Are they the longest? How are you certain?

How can you possibly work out that you are certain? Hmm, the longest possible connection would be along the two longest edges (lets just imagine they are connected). Every other connection must be shorter than this. Is this useful? well if they are the two edges just picked great, they are the longest, nothing left to do. But. What if they are not? Hmm, not very helpful.

Okay, back to the drawing board. How do you know that you've got the longest route, given you somehow picked the correct first edge. Is it the shortest or longest edge that's connected. Can you ensure the route in that pair is the biggest possible? How?

Now how do you pick the correct first edge? So that the route is the longest possible? Nothing coming to mind. Okay, what does that second edge tell you? Well it must be shorter than the first edge, otherwise you would have picked it first. Which means the second edge must be smaller, if you picked an even smaller edge will that make the route bigger, or smaller? Maybe you can exclude those edges that can only make a shorter overall route. You can exclude that second edge too, So you only need to look at those edges that could make a longer route than this one. (otherwise you already have the longest).

hmm, so if you pick the biggest edge first, and then pair it. In that pair swapping either edge with any other edge must make a shorter route. cool. But is there another pair of edges made of edges that can be longer? Maybe 7+3 > 8+1. One edge has to get bigger, and the other slightly smaller.

So maybe you can refine the possible solutions down till there is one clear winner. Do you need to look at every row between the pair of rows? probably not 8+1 > 4+3.

The above is a series of rough questions I asked myself till I became confident I could actually write code to solve it. I'll leave understanding those questions and turning that into code as an exercise for you. To be clear the algorithm is roughly O(log(N)K), way better than brute force O(N^2).

  • Wow thanks ! You made me think in a different direction ! Ill give this a try! Thanks again. – NoobieCoder3 Nov 14 '18 at 3:22

Not the answer you're looking for? Browse other questions tagged or ask your own question.