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][...].
No comments:
Post a Comment