## Monday, August 15, 2016

### Codeforces Round #366 (Div. 1) - B. Ant Man

Problem Statement:
http://codeforces.com/contest/704/problem/B

Summary:
We are given a graph with nodes 1 to n, such that the cost of going from node i to node j is:
1) |x[i] - x[j]| + c[i] + b[j] if j < i
2) |x[i] - x[j]| + d[i] + a[j] if i < j.
Given a start node s and an end node e, find a hamiltonian path from s to e (hamiltonian path: a path that visits all nodes in the graph once) such that the total cost is minimised. (Also, x[i] is monotonically increasing. n <= 5000).

Solution:
Tough and fun problem. The solution uses dynamic programming over the prefix of the nodes.

Let's simplify the cost function.

For the case where j < i, we have:
|x[i]-x[j]| + c[i] + b[j] = (c[i] + x[i]) + (b[j] - x[j]).

For the case where i < j, we have:
|x[i]-x[j]| + d[i] + a[j] = (d[i] - x[i]) + (a[j] + x[j]).

See that we can group terms of the same index together. Hence we can pre-compute the arrays left_out[i] = c[i] + x[i], left_in[j] = b[j]-x[j], right_out[i] = d[i]-x[i] and right_in[j] = a[j]+x[j].
It has the nice property that if we choose to jump to the right from node i to node j for example, we can can easily compute the cost as right_out[i] + right_in[j].

Now we can discuss the DP formulation. The idea is to analyse the property of the optimal path. The path will form a DAG. Moreover, each node along the path will have one degree in and one degree out, except node s which has one degree out, and node e which has one degree in. In the spirit of DP, what if we only consider the first i nodes 1 to i (i.e. throw away nodes [i+1 to n] from the path)?

In that case, our induced graph will contain several fragment of paths.

(induced graph)
+-------------------- |[in]
V                     |
[1]  [2]-->[3] [4]---> |[out]
^     \          |
|      \         |
|       +------> |[in_out]
+--------------- |
truncation


One important observation is that the two ends of the path must not be in this induced graph (otherwise the original path is not connected), and there cannot be a cycle in the induced graph (obviously since the original path is a DAG).

Hence we have three types of fragments:
1. 'in_out': The fragment does not contain the end points of the original path. Hence it has one in-degree edge and one out-degree edge.
2. 'in' : The fragment ends with node e. It will hence only have one in-degree edge.
3. 'out': The fragment starts with node s. It will hence only have one out-degree edge.

From that, we can already form a DP formulation. Let dp[i][in][out][in_out] be the dp state, where dp[n][0][0][0] is the minimum cost of a hamiltonian path that starts with s and ends with e. Hence dp[i][i][j][k] is the minimum cost associated with having an induced graph with i fragments with type 'in', j fragments with type 'out', and k fragments with type 'k'.
For each i, consider adding i to the current induced graph [1..i-1].
When i is not e and s, we will have to add an in-degree and out-degree edge. There are 4 ways we can do this (i.e. left-in left-out, left-in right-out, right-in left-out, right-in right-out). When i is either e or s, we can only add either an in-degree or out-degree edge respectively. Finally we also need to consider the special case where i is the n node, where we will tie in the fragments left in the induced graph into one final path. The following code is the implementation of the approach.

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
constexpr int NMAX = 5002;
constexpr int64_t INF = 1e18;
int n, e, s;
int64_t dp[2][2][2][NMAX];
int64_t left_in[NMAX], left_out[NMAX], right_in[NMAX], right_out[NMAX];
int a[NMAX], b[NMAX], c[NMAX], d[NMAX], x[NMAX];
void Compute(int i, int in, int out, int in_out) {
int prev = (i+1)%2;
int64_t* cur_state = &dp[i%2][in][out][in_out];
*cur_state = INF;
if (i == n) {
// Special case: i == n.
// Only compute this state if in and out are both 0.
if (in || out) return;
if (i == e) {
// --> x.
*cur_state = min(*cur_state, dp[prev][in][out+1][in_out] + right_in[i]);
} else if (i == s) {
// <-- x.
*cur_state = min(*cur_state, dp[prev][in+1][out][in_out] + left_out[i]);
} else {
// --> <-- x: uses one OUT and one IN to close the path.
*cur_state = min(*cur_state, dp[prev][in+1][out+1][in_out] + right_in[i] + left_out[i]);
}
return;
}
if (i == s) {
// <-- x or x -->
if (out > 0) {
// <-- x: Combine with the IN of in_out. in_out is reduced by one. out is increased by one.
*cur_state = min(*cur_state, dp[prev][in][out-1][in_out+1] + left_out[i]);
// x -->: out is increased by one.
*cur_state = min(*cur_state, dp[prev][in][out-1][in_out] + right_out[i]);
}
} else if (i == e) {
// --> x or x <--
if (in > 0) {
// --> x: Combine with one OUT from in_out. in_out is decreased by one, in increases by 1.
*cur_state = min(*cur_state, dp[prev][in-1][out][in_out+1] + right_in[i]);
// x <-- : in increases by one.
*cur_state = min(*cur_state, dp[prev][in-1][out][in_out] + left_in[i]);
}
} else {
// --> x -->: uses one OUT from either in_out or out, and introduces one OUT of the same type.
if (out > 0 || in_out > 0) {
*cur_state = min(*cur_state, dp[prev][in][out][in_out] + right_in[i] + right_out[i]);
}
// <-- x <--: uses one IN from either in_out or in, and introduces one IN of the same type.
if (in > 0 || in_out > 0) {
*cur_state = min(*cur_state, dp[prev][in][out][in_out] + left_out[i] + left_in[i]);
}
// --> <-- x: uses one OUT and one IN. Two choices:
// - Connect two in_out into one in_out, or
// - Connect in with in_out or out with in_out (either case, in_out is reduced by one, in and out is preserved).
if (in > 0 || out > 0 || in_out > 0) {
*cur_state = min(*cur_state, dp[prev][in][out][in_out+1] + right_in[i] + left_out[i]);
}
// x --> <--: adds one IN and one OUT. Hence adds 1 in_out.
if (in_out > 0) {
*cur_state = min(*cur_state, dp[prev][in][out][in_out-1] + left_in[i] + right_out[i]);
}
}
}

void Solve() {
for (int i=1;i<=n;++i){
left_out[i] = 1LL*x[i]+c[i];
left_in[i] = 1LL*b[i]-x[i];
right_out[i] = 1LL*d[i]-x[i];
right_in[i] = 1LL*x[i]+a[i];
}
for (int i=0;i<2;++i){
for (int in=0;in<2;++in){
for(int out=0;out<2;++out){
for (int in_out=0;in_out<NMAX;++in_out){
dp[i][in][out][in_out] = INF;
}
}
}
}
dp[0][0][0][0] = 0;
for (int i=1;i<=n;++i){
for (int in=0;in<2;++in){
for(int out=0;out<2;++out){
for (int in_out=0;in_out<=n;++in_out){
Compute(i, in, out, in_out);
}
}
}
}
cout << dp[n%2][0][0][0] << endl;
}
int main(){
scanf("%d%d%d",&n,&s,&e);
for (int i=1;i<=n;++i){
scanf("%d",&x[i]);
}
for (int i=1;i<=n;++i){
scanf("%d",&a[i]);
}
for (int i=1;i<=n;++i){
scanf("%d",&b[i]);
}
for (int i=1;i<=n;++i){
scanf("%d",&c[i]);
}
for (int i=1;i<=n;++i){
scanf("%d",&d[i]);
}
Solve();
return 0;
}


Notice that since we can only have at most one 'in' and one 'out' fragment, the DP state is actually O(4n^2). To reduce memory requirement, also notice that for each computation of dp[i][...], we only need to know the results of dp[i-1][...] (the previous state), hence we can get away with just caching the values of dp[i-1][...] while discarding all values of dp[1..i-2][...].