mgcloud

Hi, I'm writing a programming competition tomorrow (yikes!), and was just wondering about a common type of problem that always seems to show up. I can *kind* of get my head around it, but not fully. This is not homework, and I'm allowed to bring in any materials I choose to the contest.

Basically, the problem looks like this:

I understand what it's asking for, I'm just not quite sure on the correct method to do it. I don't need code, but a general push in the right direction will be very useful.

I'll post what I've figured out so far (it might be completely wrong)

Set up some sort of linked list representing the cities. Each node in the linked list will contain (in addition to the *next pointer), an array of pointers to other nodes. These will be matched with an array of integers, representing the greatest amount of weight going from one city to the next.

I know that can represent the data, but it doesn't seem like a very efficient way to do so (we are also marked on efficiency). However, I am unaware of any structures that could fit this type of problem better (or maybe I'm just not seeing it correctly). I also can't figure out how to properly traverse that linked list so as to find the greatest weight to be driven thru all cities.

Here is a sample input/output:

KnifeMissile

I don't really understand the question. In particular, I'm confused by the combination of "trucks which can carry trucks which can carry trucks. Needless to say, your trucks are heavy" and "you must decide which truck you will drive through these cities." These seem to contradict each other and makes it seem like one detail has nothing to do with the problem.

So, can you put the problem into other words?

I think the problem may be asking for the path that traverses all the destination cities with the highest minimum of bridge capacities. Is this correct? If so, the problem is not so hard...

mgcloud

Yep, that's correct. =)

Cuball

u should read up about some graph algorithms ...


maybe dijkstra can help you

__________________
Let's GO

kel

Yep, it's a graph search, It's also a subset of the traveling salesman problem...

Representation is important, I would consider and array of linked lists
Each element in the array represents all the roads leading out of that city.

This also falls under the domain of AI searching. You are not interested in the path cost per se, you are interested in picking a path that maximizes a certain value, specifically the maximum weight that can be driven over the roads traveled to reach that city.

The link list only represents path costs, you also need to create a graph class to deal with actually traveling down different routes.

I suggest you look up IDA*, it's ideal for this situation. H(N) in this case is the maximum weight value along this path. (normalized so that the fringe is sorted correctly)

It's deliciously neat so you could code this in a reasonable amount of time. Your allowed reference materials correct? You should definitely bring Artificial Intelligence A modern Approach - Second edition Stuart Russel and Peter Norvig.

This problem isn't solvable with plain BFS because the search space is way too big and you would have to search all of it to be sure you have the best possible solution.

Last time I went to a programming contest my group had a literal library with us for reference it helped us IMMENSELY.

__________________
"It better be funny"

kel

Errr... I think I'm wrong, this problem sounds simpler then I initially thought.

__________________
"It better be funny"

mgcloud

Cool, thanks! I'll definitely be checking a lot of these algorithms out, as my knowledge of algorithms in computer science pretty much extends to the scope of ap comp sci ab (basic searches (linear, binary)/sorts (heapsort, quicksort, merge sort, etc)).

Rekna

This sounds to me like a maximum cost spanning tree (look up minimum cost spanning tree). This can easily be solved with a greedy algorithm.

Yakk

*nod*.

Build up your graph (city nodes with bridge edges between them). Almost any implimentation would work.

Then, you want to "paint" the graph with the max weight of a truck that can reach each city. Flow out greedily from city zero.

How to flow: keep track of which cities you already know how much weight can reach. Keep track of all bridges out of the known territory: store max (bridge capacity, capacity of the city it comes from), and keep this list sorted by this effective capacity.

Select the highest effective capacity bridge. Bring the city it goes to into the fold, and add the bridges out of that city to your sorted bridge list.

Repeat until bridge list empty.

You can short cut it once you have every city that you want to visit in your known capacity set.

Now, find the min capacity city you have to visit.

Will take O((n lg(n)) time at worst, n = cities + bridges.

Other than the fact both are graph problems, this really isn't the travelling salesman problem.

Oh yes, and all of the above gave good, if less explicit, advice.

General programming contest advice:
Learn "dynamic programming".

Figure out this cute problem: "How can we fit the most amount of cars on a two-lane ferry? Does always putting the next car on the side with the most remaining room solve the problem? Can we exploit the fact that the sum of accumulated car lengths on each lane of the ferry is always an integer?" (from http://www.cs.sunysb.edu/~skiena/392/lectures/week11/ )

Learn a hell of alot of graph algorithms.

Learn some numeric computation: I got burned not knowing shit about this once.

__________________
Last edited by JHVH : 10-29-4004 BC at 09:00 PM. Reason: Time for a rest.

Rekna

Here is some more good advice for a programming contest, some friends of mine got burned on this part

Do not try to do equality on floats. Instead declare a variable epsilon that is very small .0001 or less. Then when you want to see if two floats are equal see if they are within +- epsilon of eachother.