PROBLEM LINK:
Author: Sergey Kulik
Tester: Kevin Atienza
Translators: Sergey Kulik (Russian), Team VNOI (Vietnamese) and Hu Zecong (Mandarin)
Editorialist: Kevin Atienza
DIFFICULTY:
Challenge
PREREQUISITES:
Travelling salesman problem
PROBLEM:
There is a weighted undirected graph with N nodes and M edges. The weight of each edge denotes the number of seconds it takes to traverse that edge. There are also K types of goods. Goods are sold in some of the nodes, and at different costs depending on the node, and each good has a weight W_i. You also have a budget. Your goal is to go from 1 to N with the following conditions:
- You need to buy all K types of goods along the way.
- You can’t exceed your budget.
Note that you can pass through some nodes or edges multiple times. You need to minimize your penalty. The penalty is defined as \sum_{i=1}^K T_i \cdot W_i, where T_i is the length of time since you bought the i th item until you got to the end. Intuitively, penalty is the cost you have to pay in carrying the goods.
EXPLANATION:
The problem of finding the absolute minimum penalty is similar to the more well-known Travelling Salesman Problem (TSP) in that we’re trying to find a path that minimizes some cost function. In fact, we can prove that this problem is NP-Hard by reducing the NP-Complete Hamiltonian path problem to it. We leave it to you to discover this simple reduction.
To begin, let’s describe a simple greedy solution that gives us some points for this problem.
The first step is finding a path from 1 to N that passes through every node at least once. Ideally we can find as short a path as possible, but finding the shortest path is the travelling salesman problem which is NP-Hard. Instead, we can settle on the following:
- Find the shortest paths for all pairs using Floyd’s algorithm (or multiple Dijkstra’s algorithm in the larger test groups.)
- Find the shortest path from 1 to 2, then from 2 to 3, then from 3 to 4, etc. up to N, and combine all these paths into one single path.
Assuming that the graph is randomly generated, this gives us a reasonably short path from 1 to N. Sure, it may pass through some edges multiple times, and even possibly needlessly, but that’s okay.
Next, we figure out where to buy each type of goods. Of course, we want to buy each type as late as possible to minimize the penalty, but remember that we have a budget that we cannot exceed, so a simpler idea would be to simply buy each type of goods in the cheapest way. Specifically, for each good i, find the latest node you can buy it from with the minimum cost.
This will get us accepted and will maybe give us some positive score, assuming the best score isn’t low enough to not drown this out!
More techniques
We can describe a few more techniques to possibly improve our score.
The first thought is to randomize our solution a bit. Instead of find the shortest path from 1 to 2, then from 2 to 3, etc., we can shuffle the inner nodes first. We can also try the algorithm multiple times and find the best score we get among all trials. How many times? Well, to minimize the penalty, we should do it as many times as the time limit allows! (For example, in my solution, I perform about 200 trials.)
You can also try some advanced heuristics in finding good solutions to the TSP to possibly reduce the length of our path.
Another way to possibly improve the score is during the time we try out a particular path. After figuring out when and where to buy each type, we can try to simplify the path and remove the parts of the path that aren’t required to be passed. This potentially decreases penalty.
You could also try to take into account the fact that you have some extra money to buy potentially more expensive versions of some types of goods. Some simple greedy heuristics may improve your score a bit. You just need to be mindful of your budget!
Finally, for more advanced techniques, you could learn about some well-known heuristics that have been applied to the TSP and adapt it to the current problem. One possibility is ant colony optimization, which finds "“good paths” by simulating ant behavior in finding short paths to food sources. You can read more about it here.
Please feel free to comment about your approaches in this problem. 