EFFDELIV - Editorial

editorial
, , , ,
1

Problem Link

Practice

Contest

Difficulty

Challenge

Pre-requisites

Dijkstra, knapsack problem, creativity

Problem

There is an undirected weighted graph and a set of orders. Each order is described with the node where it should be taken, the node where it should be delivered, its’ weight and the profit that the delivery boy will get upon its’ delivery. Given the stregth of the delivery boy, the maximal distance he can walk in total, the road system and the set of orders. Try to find the way to get the maximal possible profit.

Explanation

Consider a graph with 2 nodes and one edge between these nodes of the length of 1. Let the delivery boy stand at the node numbered the 1st, the distance he can walk be equal to 1. Moreover, all the orders have the pick-up node equal to 1 and the destination node equal to 2. This partial case of the problem is nothing but a knapsack problem which is indeed NP-complete, so there is no efficient precise solution.

During the contest, especially, the first few days there were only a few submissions to this problem with a non-zero score. Let’s discuss a few simple-to-code approaches, that can be the starting points for more serious solutions and their possible improvements.

Idea #1: a random walk

Let’s generate a random path in the given graph with the length not exceeding the provided constraint D. Of course, the more the length of the path is, the better. So there is no sense in stopping the generation of this path, unless all the edges outgoing from the current path’s endpoint have greater lengths than the remaining allowed distance.

Now we have a random path. For each node of this path, let’s calculate its’ last position of occurrence. Now we can iterate through the nodes of this path in order they appear and, if there is an order in the current node and the destination node will occur later (we can check it with the precomputed last occurrences’ positions) and the current carried weight plus the weight of this order doesn’t exceed the maximal weight the delivery boy can carry, we should take this order. Similarly, if we’re carrying some orders that should be delived to the current node, we can leave them now.

What can be improved

  • For a few first subtasks, where the number of the nodes is fairly small, we can try a few (for example, 1000) different random paths and take the most profitable among them.

  • Again, for small subtasks, we can use approximate algorithms like simulated annealing or local optimizations for making the most profitable path.

  • We can prioritize the orders and firstly try to take them starting with the most profitable one in every node.

  • We can store the priority queue of currently carried orders and get rid of the orders that weigh more and cost less, if we find an order that weights less and costs more (in case we don’t have enough free space for the current order).

Idea #2: greedy choice

Let’s calculate the shortest distance from the source node S to all other nodes. It can be done using Dijkstra’s algorithm. Now, let’s pick the most profitable order such that 2(distance from S to A + distance from S to B) doesn’t exceed the remaining distance we can walk. Here A is the pick-up node for the order and B is the destination node. Then, we can deliver this order by going from S to A by the shortest path, picking the parcel, then, getting back to S, then going to B and leaving the parcel, and, finally, going to S.

If, at some moment, we can’t find any order, satisfying the constraint above, then we can just finish the program.

What can be improved

  • In small subtasks we can calculate all pairwise shortest distances and don’t get back from A to S, proceeding to B, but proceed from A to B directly.
  • In this approach, we carry no more than one parcel at a time, but what if we can implement the random walk approach (Idea #1) inside. Here, the path in the graph will be equal to the concatenation of the paths from S to A, from A to S, from S to B and from B to S and the weight should be decreased by the weight of the parcel we’re going for (the one we’ve initially decided to deliver). This way we can deliver some extra parcels along with the selected one.
  • We don’t have to return to S after we’ve delivered the parcel to its’ destination junction B. We can start looking for the orders from B. The main problem would be a possibility of a time limit exceeding on large subtasks.
  • We can use approximate algorithms like A-star for faster calculation of the shortest paths from the current node. That will help us to apply some of the proposed improvements on larger subtasks.

Setter’s Solution

Can be found here

Tester’s Solution

Can be found here