Visiting points on a number line while minimizing a cost not related to distance

Question

I need some help on this ACM ICPC problem. My current idea is to model this as a shortest path problem, which is described under the problem statement.

Problem

There are N = 1000 nuclear waste containers located along a 1-D number line at distinct positions from -500,000 to 500,000, except x=0. A person is tasked with collecting all the waste bins. Each second that a waste container isn't collected, it emits 1 unit of radiation. The person starts at x = 0 and can move 1 unit every second, and collecting the waste takes a negligible amount of time. We want to find the minimum amount of radiation released while collecting all of the containers.

Sample Input:

4 Containers located at [-12, -2, 3, 7].

The best order to collect these containers is [-2, 3, 7, -12], for a minimum emitting of 50 units. Explanation: the person goes to -2 in 2 seconds and during that time 2 units of radiation are emitted. He then goes to 3 (distance: 5) so that barrel has released 2 + 5 = 7 units of radiation. He takes 4 more seconds to get to x = 7 where that barrel has emitted 2 + 5 + 4 = 11 units. He takes 19 seconds to get to x = -12 where that barrel has emitted 2 + 5 + 4 + 19 = 30 units. 2 + 7 + 11 + 30 = 50, which is the answer.

Notes

There is an obvious O(N!) solution. However, I've explored greedy methods such as moving to the closest one, or moving to the closest cluster but those haven't worked.

I've thought about this problem for quite a while, and have kind of modeled it as a graph search problem:

1. We insert 0 in as a baseline position (This will be the initial state)
2. Then, we sort the positions from least to greatest.
3. We then do a BFS/PFS, where the state consists of
   • Two integers l and r that represent a contiguous range in the sorted position array that we have visited already
   • An integer loc that tells us whether we're on the left or right endpoint of the range
   • An integer time that tells us the elapsed time
   • An integer 'cost' that tells us the total cost so far (based on nodes we've visited)
4. From each state we can move to [l - 1, r] and [l, r + 1], tweaking the other 3 integers accordingly
5. Final state is [0, N], checking both ending positions.

However, it seems that [L, R, loc] does not uniquely define a state, and we have to store L, R, loc, and time, while minimizing cost at each of these. This leads to an exponential algorithm, which is still way too slow for any good.

Can anyone help me expand on my idea or push my into the right direction?

Edit: Maybe this can be modeled as a dynamic programming optimization problem? Thinking about it, it has the same issues as the graph search solution - just because the current cost is low doesn't mean it is the optimal answer for that sub problem, since the time also affects the answer greatly.

Greedy doesn't work: I have a greedy selection algorithm that estimates the cost of moving to a certain place (e.g. if we move right, we double the distances to the left barrels and such).

Could you do a Priority-first search, with a heuristic? The heuristic could combine the cost of the current trip with the amount of time elapsed.

Answer 1

I think you can improve this by looking at the problem as a directed graph of pairs of positions.

For this example I will use the line with values -9, -6, -1, 3, and 5.

Because it's too hard to draw a graph with just text, I'm going to represent the pairs as a table. We can think of the cells as representing the state where all containers between those two positions have been collected. Each cell has two values, one representing the cost to go left, the other representing the cost to go right (to the next container).

The values can simply be calculated as the distance between the two points multiplied by the number of barrels outside of those two points + 1. Cells where both numbers have the same sign represent cases when all barrels of the opposite sign have been collected. These are calculated using only the number of barrels in the direction away from zero.

In the table values of X mean that you can't go in that direction (all the barrels in that direction have been taken). The rows represent the current position of the collector and the columns represent the location of the next opposite barrel.

    +------+------+------+------+------+
    |  -9  |  -6  |  -1  |   3  |   5  |
+---+------+------+------+------+------+
|-9 |      |      |      | X, 24| X, 14|
+---+------+------+------+------+------+
|-6 | 3, X |      |      | 9, 27| 6, 22|
+---+------+------+------+------+------+
|-1 |      |10, X |      |20, 8 |15, 18|
+---+------+------+------+------+------+
| 3 |24, 4 |27, 6 |16, 8 |      | X, 2 |
+---+------+------+------+------+------+
| 5 |14, X |22, X |18, X |      |      |
+---+------+------+------+------+------+

The rules for moving between squares can be somewhat confusing.

For negative numbered columns, the rules are as follows:

• Going right moves down one cell.
• Going left moves down one cell and then mirrors across the diagonal.
• If the right value is X, going left moves up to the diagonal (where the column and row are equal) and left by one.

For positive numbered columns, the rules are as follows:

• Going left moves up one cell.
• Going right moves up one cell and then mirrors across the diagonal.
• If the left value is X, going right moves down to the diagonal and right by one.

Now we can run Dijkstra's algorithm to calculate the best path, using these movement rules to traverse the graph. Our starting positions are (-1, 3) and (3, -1) with initial costs of 5 and 15, respectively. Once we've calculated values for the two end positions (left of (-9, -9) and right of (5, 5)) the smaller of the two is our answer.

The running time for each of the steps are:

• O(N log N) for initially sorting the input values along the line
• O(N^2) for calculating the table/graph
• O(N^2 log N) for running Dijkstra's on the graph (Note: there are at most two edges for any given vertex).

The first two steps are dominated by the last, so your overall runtime is O(N^2 log N) which should be a good enough runtime for the challenge.

Answer 2

Shortest Distance

I wrote a Java application yesterday to solve the problem. The problem is basically a shortest distance problem, as SRJ said in his comment. The radiation just shows that you can accumulate a value along with the shortest distance.

Basically, here's what I did.

• Put the container numbers in a List<Integer>
• While the List contains elements;
  • Find the element(s) that are closest
  • If there's one element, walk there and remove the element.
  • If there's two elements, copy the path and walk to both elements
• Find the path with the smallest radiation value.

Here's some output from the application

10 containers are located at [-90, -75, -47, -9, 9, 26, 48, 50, 64, 79].

You walk to position -9 and pick up the container.  The total radiation emitted is 90 units.
You walk to position 9 and pick up the container.  The total radiation emitted is 252 units.
You walk to position 26 and pick up the container.  The total radiation emitted is 388 units.
You walk to position 48 and pick up the container.  The total radiation emitted is 542 units.
You walk to position 50 and pick up the container.  The total radiation emitted is 554 units.
You walk to position 64 and pick up the container.  The total radiation emitted is 624 units.
You walk to position 79 and pick up the container.  The total radiation emitted is 684 units.
You walk to position -47 and pick up the container.  The total radiation emitted is 1,062 units.
You walk to position -75 and pick up the container.  The total radiation emitted is 1,118 units.
You walk to position -90 and pick up the container.  The total radiation emitted is 1,133 units.

I didn't optimize the algorithm in any way. I didn't even notice that the input list of numbers was sorted. (I'm a doofus.)

When I ran my code with the maximum values, 1,000 containers and a range from -500,000 to 500,000, my code took 3 seconds to execute. Most of that time was writing the 1,000 print lines to the console.

I'm not a big O person, but I think my brute force walking the shortest path algorithm is O(N squared), not O(N!).

If I took advantage of the fact that the input numbers are sorted, so that I only had to check the two numbers on either side of where I'm presently located, I could get the application down close to O(N). I only have to check 2 numbers because I'm removing the elements from the List as I get to them.

You used different algorithms, like the greedy algorithm, to find an approximate solution.

If my program had taken 3 hours to run instead of 3 seconds, then you'd have a choice to make.

Is the good enough solution good enough?

In other words, am I willing to trade processing speed for a good enough answer?

If a good enough answer is good enough, then you use approximation algorithms.

If you want the perfect answer, you have to walk all the shortest paths. There is no shortcut.

If anyone wants me to post my code, I will. I'm sure there are still bugs, as I wanted to see if I could implement a shortest walk algorithm.

Answer 3

I have a solution that will solve this problem in 2^N time, which is poor, but I think it is a helpful way of framing the problem, so I thought I would post.

Rather than model the problem as a graph, I would model it is a binary decision tree (say T). At each level you have to choose between going right or left. It is fairly easy to calculate the 'cost' of each edge. Let h(K) be the height of the current node, K, then the cost of the edge going to left_child(K) = h(K) x dist(K, left_child(K)). A similar calculation suffices for the cost of the edge to the right child. You construct this tree, and keep track of the cummulative cost of edges all the way down, and report the path to the leaf node with the smallest total cost.

Note that the cost calculation works because the length of each edge dist(K, left_child(K)) represents the time to go to the next site, while the height of the subtree is the number of sites remaining (eg. still emitting radiation).

Now the trick within this framework is to determine if there are some heuristics you can use to 'prove' that you can ignore expanding the search along some branch. My intuition is that for any such heuristic there is an arrangement of sites that will defeat it, but perhaps someone can come up with something.

A number have proposed applying shortest path solutions for graphs, I have some doubts over whether such a solution can work. Your neighbours in the 'graph' in the problem will change depending on the path you follow. For example in your original post with [-12, -2, 3, 7] if you go to -2 then -12 and 3 become 'neighbours' and if you go to 3 then -2 and 7 are neighbours. Every possible 'pair' of positive and negative values can potentially be neigbhours in the final graph. I don't know of any shortest path algorithms that are provably correct in an dynamic graph.

Answer 4

I think it makes most sense to think of every stage simply as a binary choice between going right to the nearest barrel and going left to the nearest barrel. Simply have a cost function that details the number of radiation units that would be incurred in total by making any motion and choose the one with the lowest cost.

Do NOT simply consider the closest barrel, but instead assume that by moving away from a barrel you are effectively adding twice the radiation because by moving away you have also incurred the cost of having to move back that direction later.

In your example of [-12,-2,3,7], moving left would incur a total of 14(2+2+10) on the left, and 18(2+2+5+9) on the right, for a total of 22. Moving right would incur 10(3+3+4) on the right, and 26(3+3+5+15) on the right. Clearly left is the right solution at first. A similar calculation can be done for every successive movement.

After that the problem basically reduces to a search, so the complexity should be O(nlog(n)), which is MUCH better than O(n!). I believe that this is necessarily the lowest complexity that can exist for this problem since it's basically a comparison based search algorithm for which it is not possible to do better than O(nlog(n))

Apparently I wasn't clear enough with this description, so I've decided to make it a bit more programmatic: 1. Calculate the cost incurred by going by left, and the cost incurred by going right based on current position 2. Move in the least expensive direction 3. Remove the reached barrel from consideration in calculating the cost of moving in a direction

Calculating cost: 1. Identify the closest barrel in the given direction. Let's say that $dist is the distance from current position to the nearest barrel in the given direction. 2. Cost is initialized as N*$dist where N only considers still active barrels. 3. To this, add the distance that the new position indicated by $dist would be from every barrel remaining.

Answer 5

Partial solution - I'll get back to it later.

Assume the "default" strategy is run all the way left or right, whichever is cheaper. Now ask, is it worth a little side trip the other way to pick up one barrel. It's fairly easy to calculate the answer.

For you sample input, running all the way right is cheaper than all the way left. Is going to -2 worth a side trip? It reduces the cost of running all the way right and then back to 0 by 14 (because you were "paying" 4 radiation units per move from 0 to 3 on the default strategy, now it's down to 3, you were paying 3 from 3 to 7, now it's 2, etc), plus reduces by one per move your cost of moving from 0 to -2, thus saving 2 more for a total of 16.

However, it adds a cost of going to -2 then back to 0 of 14 (4 units per move to -2, 3 per move back to 0), for a net gain of (16-14)=2. Note that to calculate this you don't have to evaluate the exact cost of solving the whole problem for each decision - you have enough information to decide just by knowing if running all the way left is cheaper than running all the way right, plus how many waste containers are on each side of you, and the distance to the nearest 2. So that's O(N^2).

Except for one important problem - I've assumed you will run all the way to the end, and we know you might double back. To clean that up, we need to update my calculation. For the sample input, I've assumed you would save 14 by emitting 1 less total radiation per unit per second while running from 0 to 7 and back. But, if you double back prior to running to 7, the savings will be reduced.

That's pretty bad, because, I don't know how to calculate the next double-back without trying all the possibilities, which puts us back to O(2^N).

Except - it's 2^N with pruning. I calculated that the "side trip" to -2 cost 14, but gained 16, if I didn't have more side trips before I made it to the rightmost number. If the rightmost number had been 5, I would immediately know the side trip to -2 couldn't pay off. (Cost still 14, maximum benefit 12). Nor do I have to consider going to -2 then making a side trip before reaching 6, since that is always inferior to just going straight to that point in the first place.

Answer 6

I think you can solve it using a breadth-first search, maintaining no more than 2 * N^2 tuples of (boolean, int, int, int, string) where the strings are as long as the path is complicated.

The tuples are (min or max boolean, min position traveled, max position traveled, total radiation emitted, path history).

I see the algorithm going like this:

1. Initialize the pool of tuples to a single entry, (min, 0, 0, 0, "")
2. Find an element in the pool that has minimal radiation emitted. If the min and max correspond to the min and max of all the barrels, then the path history is the optimal solution. Otherwise delete it from the pool.
3. Calculate the 2 descendants of this tuple, each of which corresponds to walking left or right to the next unprocessed barrel.
4. Insert the descendants into the pool. If there is already an element in the pool with the same boolean, min, and max as a new descendent, then discard the element with the higher radiation count.
5. goto 2.

Finding and removing dominated tuples will dramatically improve performance. It might be worthwhile to add a 'has bred" flag to each tuple, and leave bred tuples in the pool.

There are also some significant decisions to be made in deciding how to store the tuples, and search them for dominations and new elements to breed.