Best way for three people to visit some graph nodes in a given order

Question

UPD. I solved the problem.

Let DP[i][vertex_a][vertex_b] is the state with i cities visited and two players standing at vertices vertex_a, vertex_b (is is guaranteed one of then stands at list[i]). WLOG assume vertex_a ≤ vertex_b as this DP table doesn't carry information about players positions. Only three states can be reached from DP[i][vertex_a][vertex_b], namely DP[i + 1][vertex_a][vertex_b], DP[i + 1][list[i]][vertex_b], DP[i + 1][vertex_a][list[i]]. We also only need to store two layers of DP, so only sizeof(int) * 2 * 200 * 200 bytes needed to compute optimal path cost. To get the path there would be last_move_id[i][vertex_a][vertex_b] carrying information about the player that made move at state DP[i][vertex_a][vertex_b] and last_move_positions[i][vertex_a][vertex_b] storing the number of vertex from which player reached list[i]. As vertex number doesn't exceed 200 it's save to store those as byte, so sizeof(byte) * 1000 * 200 * 200 bytes for each array. To maintain these arrays there'd have to be another array positions[i][vertex_a][vertex_b][3] carrying information about position of each player, only last two layers are needed, so sizeof(byte) * 2 * 200 * 200 * 3 bytes for this one. Time complexity O(N * L * L).

My C++ implementation uses 76Mb and 320 ms.

I am struggling with the following competitive programming problem from a Russian online judge http://informatics.mccme.ru/moodle/mod/statements/view.php?chapterid=3379 . According to rules, one must provide the source of the problem as far as I remember

Unfortunately, there's no English version of website so I'll try to describe the problem.

Input consists of the complete digraph G with L vertices and some list of vertices (length at most N). Three people start at vertices 1, 2, 3 respectively. They have to visit each vertex from the input list, order matters, vertex i + 1 is necessarily visited after i. At one point of time only one person can make a move (if one person goes from some previous vertex to vertex i others stand still, they can't move in parallel). If person/player stands at vertex i and has to move to vertex j he must take an edge (i, j) instead of some shortest path to vertex j (Floyd–Warshall algorithm can't used to speed up computations here). It is sufficent for a vertex to be visited by a single person which means that all of them can be visited by person 1 while other would stand still. The cost of edge (i, i) is always 0, there are no multi-edges, all edge weights are non-negative and G is represented as L x L adjacency matrix. Output the cost of shortest possible path for these three people to visit vertices from list amd output what person visited each vertex. Input list of vertices to be visited is a multiset (N may be bigger than L)

I've found this problem somewhat similar to Two-Person Traversal of a Sequence of Cities problem, except this is a Three-Person version and they start at different positions and a major difference that people have to visit a specific sequence of vertices with repetitions allowed. I've investigated the solutions of this problem and the time complexity would be O(L^3) for Two-Person Traversal of a Sequence of Cities and it would be O(N^4) for my problem, which is too slow as even O(N^3) algorithm won't meet time limits, I think something like O(LN^2) could work though.

Constraints:

3 ≤ L ≤ 200, 1 ≤ N ≤ 1000

0 ≤ edge weight ≤ 2000

Time limit: 1s, memory limit is 256 Mb

I also know for sure this problem can be solved using than 64 Mb.

This problem is tagged as 2D dynamic programming.

I cannot really come up with this exact 2D dynamics. I thought of a pretty straightforward way to solve this problem:

The initial state of three people is (1, 2, 3). When processing the first vertex we compute:

1:(list[1], 2, 3) = (1, 2, 3) + weight(1, list[1])

1:(1, list[1], 3) = (1, 2, 3) + weight(2, list[1])

1:(1, 2, list[1]) = (1, 2, 3) + weight(3, list[1]).

As one can see this is a 4D dynamic table, but I think that keeping the number of current iteration is unnecessary making it into 3D one. Moreover, one can notice that for computing (i+1)-th layer one only needs information about i-th one, which makes it a great memory optimisation. Nonetheless, if we forget that there are only at most 200 vertices in the graph and think about states as tuples (i, j, k), where i, j, k are the numbers of last stage players 1, 2, 3 made move at, which means that at m-th stage one of i, j, k equals to m. Following this logic and considering all possible repetitions the number of distinct tuples at m-th stage is:

Number_at_stage(m) = Number_at_stage(m - 1) + 6 * (m - 1), Number_at_stage(1) = 3, Number_at_stage(2) = 9, Number_at_stage(1000) = 2991009.

Number_at_stage(1) I got from the following thoughts:

(0, 0, 0) -> (1, 0, 0), (0, 1, 0), (0, 0, 1)

I've summed the number of distinct tuples at stages 1..1000 and got a horrific number of 997004997 which is almost a billion. This means the number of distinct tuples that represent such moves are asymptotically cubic (wasn't surprising, but obvious). I don't understand how to improve the idea. Thinking in this way, I don't know how to work with states such as (i, j, k) and (k, j, i) since they are actually equivalent in the sence that the same set of steps can be made based on these. I just do not know how to process such states and keeping information what person visited what city (simple multi-dimensional array?).

My next thought would be to have a two dimensional DP(i, j) storing the optimal sum of distances for sublist with elements from i to j. The answer would be stored in DP(1, N) if the indexing goes from 1. I could compute all subsets of length 1, 2, ... N. There is a major issue with this idea, I don't know how to process DP(i, j) without knowing all potential positions players can stand at (all elements from list going before i and initial positions 1, 2, 3). I also don't know how to determine what player made the move with this approach.

Could you provide me some help find the 2D dynamics?

Answer 1

Given the possible states of the 3 players when list[i] is visited, and the cost so far associated with each such state, calculate the possible states and costs for list[i+1]. When you get to list[N-1], select the lowest cost. Keep predecessor links so you can traverse the entire sequence back to the start and output it.

I'm pretty sure you got that much already... Here's the part you missed:

How many distinguishable states are there when list[i] is visited? Well, it's less than L^3, because it doesn't matter which player is on which vertex. It's also less than L^3/3!, because at least one of the players is obviously on list[i]!

So, one player is on list[i] and there are only L(L+1)/2 distinguishable positions for the other players. That means there are at most 20100 possible states for each list[i], and about 20M possible states in the whole array of possibilities for each list index. If you're a little bit careful about how you store the states and links, you can fit into your 256MB memory limit.