Parks of Jakarta (Problem E, 2017 ICPC Asia Jakarta Regional Contest, 2017)
Time limit: 1 sec
Memory limit: 256MB
Author: Ivan Adrian Koswara

# Problem Statement

There are three parks in Jakarta, called Park 1, Park 2, and Park 3. The new governor of Jakarta wants to add decorations to these parks by adding bricks. These bricks are going to be stacked on top of another on these three parks. There are $N$ bricks in Jakarta, indexed from $1$ to $N$. A brick with index $i$ is smaller than a brick with index $i + 1$. We do not want to put a bigger brick on top of a smaller brick. Therefore, we can put a brick with index $i$ on top of a brick with index $j$ if and only if $i < j$.

We define a brick configuration as a distribution of these $N$ bricks on the three parks. Note that there must only be one stack of bricks in each park, and the bricks must be stacked in the order as explained on the previous paragraph. For example, if $N = 3$, then a possible brick configuration is: brick 1 (on the top) and brick 2 (on the bottom) are in park 1, no brick is in park 2, and brick 3 is in park 3.

We can change a brick configuration to another by doing an operation, which we will:

- Pick two different parks $i$ and $j$. Take the topmost brick on the stack in park $i$ and put it on the top of the stack in park $j$. If there is no brick in park $i$, then this operation is not valid. If this operation causes the stack in park $j$ to violate the stack order condition, then this operation is also not valid.
- Since we need to rent a truck to transport the brick from park $i$ to park $j$, we need to pay $R_{i,j}$ units of money for this operation. Note that the cost of transporting a brick from park $i$ to park $j$ might be different with the cost of transporting a brick from park $j$ to park $i$.

Initially, the bricks are in some brick configuration, which we will call the initial brick configuration. The new governor of Jakarta wants to try $M$ brick configurations. Therefore, from the initial brick configuration, we must do several operations such that each of the $M$ brick configurations (in any order) wanted by the new governor is seen at least once. In the end, the new governor also wants us to put all the bricks in (any) one park. We want to minimise the total cost to satisfy his demand.

Formally, let $G_1, G_2, \cdots, G_M$ be the brick configurations wanted by the new governor. We want to construct a sequence of brick configurations $C_0, C_1, \cdots, C_k$ ($k \geq 0$) with the minimum cost where:

- $C_0$ is the initial brick configuration
- There exists a sequence of integers $x_1, x_2, \cdots, x_M$ ($0 \leq x_i \leq k$) where $C_{x_i} = G_i$. Note that the sequence is not necessarily increasing.
- $C_k$ is a brick configuration where all the bricks are stacked in (any) one of the parks.
- For all $0 \leq i < k$, we can achieve $C_{i+1}$ from $C_i$ by doing a single operation (described in paragraph three above).
- The cost of this sequence is the sum of cost needed to change $C_i$ to $C_{i+1}$ for all $0 \leq i < k$.

Let us help the new governor of Jakarta!

# Input

The first line contains two integers: $N$ $M$ ($1 \leq N \leq 40$; $0 \leq M \leq 16$) in a line denoting the number of bricks and the number of configurations. The next three lines, each contains three integers. The $j$-th integer on the $i$-th line is $R_{i,j}$ ($0 \le R_{i,j} \le 1000$; $R_{i,i} = 0$) denoting the cost of moving a brick from the $i$-th city to the $j$-th city. The next three lines denote the initial brick configuration, with the format explained in the next paragraph. The next $M$ blocks describe the configurations wanted by the new governor, where each block contains three lines, with the format of each configuration explained in the next paragraph.

Each configuration is denoted by three lines. The $i$-th line begins with an integer $K$ ($0 \le K \le N$) denoting the number of bricks in park $i$, followed by $K$ integers: $A_1\ A_2\ \cdots\ A_K$ ($1 \le A_i \le N$) denoting the brick indices in park $i$. It is guaranteed that $A_i < A_j$ for all $1 \le i < j \le K$. It is also guaranteed that each of the integers between 1 and $N$, inclusive, appears exactly once on the union of the array $A$ on the three lines. For example, the sample brick configuration given on the second paragraph will be illustrated in the first sample input.

# Output

The output contains the minimum total cost (in units of money) to satisfy the new governor's demand, in a line.

# Sample Input
```
3 0
0 1 1000
1 0 1
1000 1 0
2 1 2
1 3
```
# Output for Sample Input
```
5
```
# Sample Input
```
3 2
0 2 2
2 0 2
2 2 0
2 1 2
1 3
0
3 1 2 3
0
0
0
0
3 1 2 3
```
# Output for Sample Input
```
22
```
# Explanation for the 1st sample case

In the first sample, we initially have brick 1 and brick 2 in park 1, and brick 3 in park 3. Since $M = 0$, our goal is to only reach a brick configuration where all bricks are in the same (any) park. Therefore, we can do the following operations:

- Move brick 3 from park 3 to park 2. This costs 1 unit of money.
- Move brick 1 from park 1 to park 2. This costs 1 unit of money.
- Move brick 1 from park 2 to park 3. This costs 1 unit of money.
- Move brick 2 from park 1 to park 2. This costs 1 unit of money.
- Move brick 1 from park 3 to park 2. This costs 1 unit of money.

Therefore, all of the bricks are now in park 2 and we spend 5 units of money. There is no solution that costs less than 5 units of money. Note that we do not necessarily minimise the number of operations.

# Explanation for the 2nd sample case

In the second sample, the optimal solution can be achieved if we satisfy the second configuration first before the first one. From the initial configuration, we can get to the second configuration with 4 operations with the total cost of 8 units. From the second configuration, we can get to the first configuration with 7 operations with the total cost of 14 units. Since the first configuration already has all the bricks stacked in one park, we don’t need any additional operation. Therefore, the total cost is 22 units.

Sample inputs:
3 0
0 1 1000
1 0 1
1000 1 0
2 1 2
0
1 3

3 2
0 2 2
2 0 2
2 2 0
2 1 2
1 3
0
3 1 2 3
0
0
0
0
3 1 2 3

Sample outputs:
5

22

# Solution Analysis
Analysis author: Ivan Adrian Koswara

Notice that this is essentially Tower of Hanoi, but with a couple of twists. First, the positions of the disks (the stones) aren't necessarily in a single pile (park); they may be distributed anywhere. Second, the cost of moving a stone is not necessarily the same between piles, and so the standard solution of solving Tower of Hanoi problems must be adapted. Finally, there are many configurations to visit, with an option of what the final configuration can be; this adds an extra layer on top of the problem.

First, observe that this problem is made of two parts. The first, small-scale part is how to efficiently bring configuration $A$ to configuration $B$, for any two configurations of stones. The second, large-scale part is how to solve the actual problem: how to visit all intermediate configurations and then gather them all in one park.

We will figure out how to solve the small-scale part. The idea, as in Tower of Hanoi problems in general, is to notice the following fact: in order to move stone number $K$ from a park to another, we need all stones $1, 2, \dots, K - 1$ to be gathered in the third park. This gives a nice dynamic programming solution: for any $K$, most of the time we want to gather stones $1, 2, \dots, K$ into a single park, and in doing so we don't need to care about the larger stones.

We use dynamic programming to solve the following problem: "What's the optimal cost to bring disks $1, 2, \dots, K$ from a configuration $P$ to a configuration $Q$?" Obviously, if $P$ and $Q$ can be any configuration, there are a lot of states to keep track of. The trick is to notice that there are only four possible $P$'s that matter, and also only four possible $Q$'s. The configuration "all in Park 1", "all in Park 2", and "all in Park 3" are some of the options for $P$ and $Q$. In addition, the starting configuration, cut to include only stones up to $K$, is another option for $P$; likewise, the ending configuration is another option for $Q$.

However, these are all. It's never beneficial to leave stones in any other configuration; if we leave stones $1, 2, \dots, K$ in configuration $R$ that is not one of these, we won't be able to move any stone greater than $K$, and so we must continue moving configuration $R$ to another configuration without being able to do any meaningful work in between. On the other hand, leaving all stones in one pile allows us to move stone $K+1$ from one of the other two piles to the other, and starting with all stones in configuration $A$ and ending with all stones in configuration $B$ are exactly what we're looking for, so these states are important.

The DP states will be recorded as $\text{dp}[K][P][Q]$, where $K$ indicates how many stones are being considered, and $P$ and $Q$ are state numbers: $1, 2, 3$ for all in park of the same number, $0$ for starting configuration (only for $P$), and $4$ for ending configuration (only for $Q$). The base case is $\text{dp}[0][P][Q] = 0$; we never need to get any cost for moving zero stones. Now we set up a recurrence.

For ease, we will first assume $P$ and $Q$ are some of $1, 2$, and $3$; that is, all stones are in one park and we want to move all of them to another. We will adapt it to the cases $0$ and $4$ later. If $P = Q$, we're already done (and the cost is $0$), so assume they are different and let $R$ be the remaining park.

In order to move stones $1, 2, \dots, K$ from $P$ to $Q$, we need to move stone $K$ from $P$ to $Q$. There are two ways to do this: either directly, or going through $R$. (It might be cheaper to go through $R$! This is different from standard Tower of Hanoi.) In either case, to move stone $K$, we need all stones $1, 2, \dots, K-1$ to go to the third park.

The first method will incur the following cost:
- Move stones $1, 2, \dots, K-1$ from $P$ to $R$: $\text{dp}[K-1][P][R]$
- Move stone $K$ from $P$ to $Q$: $\text{cost}[P][Q]$ ($R_{P,Q}$ in description)
- Move stones $1, 2, \dots, K-1$ from $R$ to $Q$: $\text{dp}[K-1][R][Q]$

They add up to $\text{dp}[K-1][P][R] + \text{cost}[P][Q] + \text{dp}[K-1][R][Q]$. Similarly, the second method costs $\text{dp}[K-1][P][Q] + \text{cost}[P][R] + \text{dp}[K-1][Q][P] + \text{cost}[R][Q] + \text{dp}[K-1][P][Q]$. We simply test both of these and take the minimum; that's the value of $\text{dp}[K-1][P][Q]$.

What if $P = 0$? Stone $K$ will still start from a particular park, say $P_0$, and from that we can still find $R$. Then the cost of the second method changes subtly, since we want to move to park $P_0$: it becomes $\text{dp}[K-1][0][Q] + \text{cost}[P_0][R] + \text{dp}[K-1][Q][P_0] + \text{cost}[R][Q] + \text{dp}[K-1][P_0][Q]$. The other cases are similar; at worst we'll just have several implications of very similar lines.

Finally, we just run this in order for $K = 0, 1, 2, \dots, N$, and our result is stored in $\text{dp}[N][0][4]$. Since the numbers of options for $P$ and $Q$ are constant, and each evaluation is constant, this takes $O(N)$ time. With $N = 40$, this is a breeze and we can repeat this quite a lot of times.

Which is good, since we'll need it for the second part. The idea is to first consider the following $M+4$ configurations: the initial state, the $M$ intermediate states, and the $3$ possible ending states: all in Park 1, all in Park 2, and all in Park 3. We consider all pairwise optimal costs between these, from any single configuration to any of the others. With $M = 16$, we can definitely take the $O(NM^2)$ time needed to find all of these costs. This is a preprocessing cost; we don't even need to recompute these values any more.

Once we have these costs, we're now basically solving a variant of the Traveling Salesman Problem: starting from the given configuration, we want to visit all intermediate configurations in some order, and reach one of the three ending configurations, with as low cost as possible. This can be solved using standard methods. One example is to use bitmask-based dynamic programming, using two states: "current configuration" and "which intermediate configurations have been visited". This will have $O(M \cdot 2^M)$ states, but with $M = 16$ this is not a problem.

Special judge (C++ scorer):