Editorial for COI '10 #4 Kamion
Submitting an official solution before solving the problem yourself is a bannable offence.
The solution to this hard problem is going to be on a simple version of this problem. In the simple version, there won't exist any roads of type , and the truck has to get empty to city
in the last step. In other words, it is allowed for the truck to pass through city
on its trip as many times as it likes, but in the last step when it enters city
it has to be empty.
The rest of this description is going to be devoted to the problem with these two restrictions, while the solution of the original problem will be left to the reader for exercise.
So, the new problem which we are about to solve says: how to get from city to city
using at most
steps with the restriction that truck has to get into city
empty. As a solution, dynamic programming is used. Let
be the number of different ways to get from city
to city
using exactly
steps starting (from city
) and ending (in city
) with an empty truck. The first road which we have to pass in our trip will have to be road type
in which we load some kind of cargo. Let's mark this road as
. Then we choose the road on which we unload exactly that piece of cargo (which has to be a road of type
). Let's mark this road as
. Then we can add to the solution all the paths, i.e.
where
. Unfortunately, a solution implemented this way will have complexity
which is not enough to get all points for this task.
A better solution is to use an additional dynamic function which will contain the number of different trips from city
to
using exactly
steps while starting and ending with an empty truck (and never empty in the middle of the trip).
Dynamic tables are calculated increasingly by number . While calculating table
, we are finding the first town and step in which our truck is going to be empty. If it happens in city
in step
, we have:
Parallel with that, we are calculating dynamic table . Let's search for roads
and
where we are loading and unloading the same type of cargo. We have:
Complexity of this solution can be represented as , which is enough to get all points for this task.
Comments