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][...].