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.
A regular tree would suit just fine and Approach 1 would work here. I think you should also read up a bit about the search algorithms used for a B-tree and then see how you could modify it here.
To me, this question is basically about how to modify a generalized B-Tree to handle properties with a propagation element.
Like you say:
- Store the tree as a regular tree.
- Store properties with the nodes they are set on.
But:
Don't double link them - You can walk down the tree during the search (and also unfold if necessary revisiting the parent node when using typical recursive methods).
Don't create a hash-table - a hash-table is just another look-up data-structure, why use it when you can modify the tree!
DON'T DO THIS: Compute the properties inherited by nodes, by walking UP the tree ...
INSTEAD DO THIS: Store the properties as you walk through the tree locating the target node. You have to visit them anyway. During the node traversal search just pass through the property if 'propagate' is on. When at the child node; don't save it if the property also exists there and is set to 'turned off'. Keep traversing until you reach your target node, storing the properties as you go (perhaps in some simple little list).
Note that the property attributes requirements for 'propagate' and 'turned off' only impact the search algorithm by requiring logic to be placed in the traversal method.
PROBLEM 1: Computing properties on a set of nodes is slow. Dumb implementation results in O(PDN) although I have a feeling this can be improved.
SOLUTION: This is full of assumptions. What is a set? I only can assume a simple case like; set of nodes are all of the direct children of their parent node & depth of 1. Given this; Locate the parent node first with all the properties saved up until that parent node (as we just discussed in the previous point). Then for each child of that node you calculate out the properties - so for each child you have all the saved properties up to that parent node + the child's properties.
EXAMPLE: Traverse from the root node to a target node. For each node get the properties where they are 'propagated' and then traverse the next node passing through those properties. For the next node; for each property passed through check they are in the current node, if they are present and are 'turned on' then overwrite the property with the current nodes value. Then do the 'propagation' check and redo going through the nodes until the target node. Then you are left with the children - apply the same attribute logic and record the properties for each node.
PROBLEM 2: Finding out which nodes inherit a specific property in the whole tree is VERY slow and I don't see a good way to optimize it.
SOLUTION: Here, you want to search for this efficiently but the creation of your tree solution doesn't have to be so efficient. And it's not too complex because you just need to find if it is 'turned off' or not - and not involve the 'propagate' property. What you need to do here is use the tree as it is supposed to be used. If a property is not 'turned off' you want to say to the parent node that a child of theirs has a specific property and then update all the way back up to the root node. This way if a property doesn't exist at all you'll know straight away when visiting the root node that it doesn't exist.
EXAMPLE: Given a child node is set with a new property and 'turned on'; update the parent node with the same property and set to 'turned off' and use this to say the property exists in one of the nodes children. Then for each parent above that parent, set the same property and attribute. Now start to traverse from the root node the property will be set on the root node indicating that a descendant has that property. Do a traversal search and go through each child where the property is set - store each node where the property is 'turned on'.
Hopefully I can improve on this answer. Help me by indicating hard to understand parts of my answer.
Best Answer
Since you brought congestion into the picture, be careful you don't get caught by Braess' Paradox. If everyone chooses the optimal path, it results in worse travel time for everyone.