[CCO 2024] Heavy Light Decomposition

前置知识

分块，DP

简要题意

定义“好的数组”为一个数组内交替出现“轻元素”和“重元素”，轻元素即其在这个数组内是唯一的，重元素即其在数组内出现多次。

有 $n$ 个正整数 $a_i$，求其有多少种划分方案能使划分后的子数组均为好的数组。

分析样例

我们首先要搞懂一个东西，就是划分后好的数组，是指这个子数组是好的，在这个子数组内的轻重元素与原数组并没有关系，每个子数组是互相独立的。

对于样例一，其划分方案如下：

- $[1], [2], [3], [2], [3]$

- $[1], [2, 3, 2], [3]$

- $[1], [2], [3, 2, 3]$

- $[1, 2, 3, 2], [3]$

对于样例二，其划分方案如下：

- $[1], [2], [1], [3], [1]$

- $[1, 2, 1], [3], [1]$

- $[1, 2, 1, 3], [1]$

- $[1], [2], [1, 3, 1]$

- $[1], [2, 1, 3, 1]$

- $[1, 2, 1, 3, 1]$

不明白的建议手推一下。

思路分析

考虑转移

我们定义 $dp[i]$ 为前 $i$ 个元素的合法划分的方案数。

那么，转移方程很显然：$dp[i] = \sum dp[j]$，其中 $j < i$ 且 子数组 $[j + 1, i]$ 是好数组。

实际上含义就是在 $j$ 处划分，新增一个子数组 $[j + 1, i]$，方案累加前 $j$ 个元素的方案数。

考虑好数组的约束

如果 $[j + 1, i]$ 为好的数组，那么需要满足：

1. 类型交替：即数组内的元素轻重交替。

2. 奇偶性约束：如果重元素第一次出现在奇数位，那么奇数位全是重元素，反之。

因此我们如果直接枚举所有的 $j$ 去验证 $[j + 1, i]$ 是否为好数组，时间复杂度为 $O(n ^ 2)$。

考虑优化

对于当前的位置 $i$，我们设其元素大小为 $v$，用 $odd[v]$ 和 $even[v]$ 来记录 $v$ 在奇数和偶数位最近的出现位置，这样的话可以确定 $j$ 的下界。

为了保证子数组 $[j + 1, i]$ 满足类型交替，需要避免 $v$ 元素在数组内出现奇偶性冲突，那么若 $j + 1 < \min(odd[v], even[v])$ 的话，则会使其冲突。

因此我们使 $minL$ 取所有元素 $min(odd[v], even[v]) + 1$ 的最大值，因此 $j > minL - 1$。

然后是最重要的分块，我们将原数组分块，每个块维护两个核心内容，$sum[k][b]$ 表示 $b$ 块满足在奇偶性 $k$ 下的合法的 $dp[j]$ 之和，$kpos[k][b]$ 是在 $k$ 的奇偶性下块 $b$ 是否满足。另外，为了维护分块时的单个元素， 我们维护 $pos[k][i]$ 是单个位置的 $i$ 是否满足奇偶性 $k$。

当我们查询 $[l, r]$ 内符合条件的 $dp[j]$ 之和时，对于整块，只需要判断 $kpos$ 是否有效，然后累加 $sum$ 即可，对于单个的块边缘的元素，则需要满足 $kpos$ 和 $pos$，有效则累加 $dp[j]$。

在区间更新时，只需要标记区间有效和无效，在完整的块上更新 $kpos$，零散的元素更新 $pos$ 和 $sum$。

时间复杂度

分块的单次查询和更新的时间复杂度为 $O(\sqrt{n})$，时间复杂度为 $O(n \sqrt n)$。

简单卡常即可，最慢的点才两秒出头，对于四秒的时间限制完全够用。

代码

#include<iostream>
#include<cstdio>
#include<cmath>
#include<vector>
#include<unordered_map>
#include<cstring>
using namespace std;

const int MOD = 1e6 + 3;
const int MAXN = 5 * 1e5 + 5;

int kpos[2][MAXN], sum[2][MAXN], pos[2][MAXN];
int L[MAXN], R[MAXN], id[MAXN];
int dp[MAXN], even[MAXN], odd[MAXN];
int a[MAXN], pre[MAXN];
pair<int, int> lst[MAXN];
int n, tot = 0, B;

inline int read(){
    int x = 0, f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9'){
        if(ch == '-') f = -1;
        ch = getchar();
    }
    while(ch>='0' && ch<='9')
        x = x * 10 + ch - '0', ch = getchar();
    return x * f;
}


inline void update(int k, int l, int r, int x){
    if(l > r) return;
    int kl = id[l], kr = id[r];
    if(kl != kr){
        for(int i = kl + 1;i < kr;++ i){
            kpos[k][i] += x;
        }
        if(l == L[kl]){
            kpos[k][kl] += x;
        }
		else{
            for(int i = l;i <= R[kl];++ i){
                if(pos[k][i]){
                    sum[k][kl] = (sum[k][kl] + dp[i - 1]) % MOD;
                }
                pos[k][i] += x;
                if(pos[k][i]){
                    sum[k][kl] = (sum[k][kl] - dp[i - 1] + MOD) % MOD;
                }
            }
        }
        if(r == R[kr]){
            kpos[k][kr] += x;
        }
		else{
            for(int i = L[kr];i <= r;++ i){
                if(pos[k][i]){
                    sum[k][kr] = (sum[k][kr] + dp[i - 1]) % MOD;
                }
                pos[k][i] += x;
                if(pos[k][i]){
                    sum[k][kr] = (sum[k][kr] - dp[i - 1] + MOD) % MOD;
                }
            }
        }
    }
	else{
        if(l == L[kl] && r == R[kl]){
            kpos[k][kl] += x;
        }
		else {
            for(int i = l;i <= r;++ i){
                if(pos[k][i]){
                    sum[k][kl] = (sum[k][kl] + dp[i - 1]) % MOD;
                }
                pos[k][i] += x;
                if(pos[k][i]){
                    sum[k][kl] = (sum[k][kl] - dp[i - 1] + MOD) % MOD;
                }
            }
        }
    }
}

inline int query(int k, int l, int r){
    if(l > r) return 0;
    int res = 0;
    int kl = id[l], kr = id[r];
    if(kl != kr){
        for(int i = kl + 1;i < kr;++ i){
            if(!kpos[k][i]){
                res = (res + sum[k][i]) % MOD;
            }
        }
        if(l == L[kl]){
            if(!kpos[k][kl]){
                res = (res + sum[k][kl]) % MOD;
            }
        }
		else{
            for(int i = l; i <= R[kl]; i++){
                if(!pos[k][i] && !kpos[k][kl]){
                    res = (res + dp[i - 1]) % MOD;
                }
            }
        }
        if(r == R[kr]){
            if(!kpos[k][kr]){
                res = (res + sum[k][kr]) % MOD;
            }
        }
		else{
            for(int i = L[kr];i <= r;++ i){
                if (!pos[k][i] && !kpos[k][kr]){
                    res = (res + dp[i - 1]) % MOD;
                }
            }
        }
    }
	else{
        if(l == L[kl] && r == R[kl]){
            if(!kpos[k][kl]){
                res = (res + sum[k][kl]) % MOD;
            }
        }
		else{
            for(int i = l;i <= r;++ i){
                if (!pos[k][i] && !kpos[k][kl]){
                    res = (res + dp[i - 1]) % MOD;
                }
            }
        }
    }
    return res;
}

int main(){
	freopen("digit.in", "r", stdin);
	freopen("digit.out", "w", stdout);
	n = read();
	B = 300;
    for(int i = 1; i <= n; i += B){
        L[++ tot] = i;
        R[tot] = min(n, i + B - 1);
        for(int j = i;j <= R[tot];++ j){
            id[j] = tot;
        }
    }

//	for(int i = 1;i <= n;++ i){
//		cout << i << ' ' << id[i] << '\n;'
//	}

    dp[0] = 1;

    for(int i = 1;i <= n;++ i) a[i] = read();

    int leven = 0, lodd = 0, minL = 1;
    memset(lst, -1, sizeof(lst));

    for(int i = 1;i <= n;++ i){
        sum[0][id[i]] = (sum[0][id[i]] + dp[i - 1]) % MOD;
        sum[1][id[i]] = (sum[1][id[i]] + dp[i - 1]) % MOD;
        dp[i] = dp[i - 1];
        int v = a[i];
        if(lst[v].second != -1){
            update(lst[v].second & 1, lst[v].first + 1, lst[v].second, -1);
        }
        if(i & 1){
            lodd = max(lodd, odd[v]);
            odd[v] = i;
        }
		else{
            leven = max(leven, even[v]);
            even[v] = i;
        }
        lst[v] = {pre[v], i};
        update(lst[v].second & 1, lst[v].first + 1, lst[v].second, 1);
        pre[v] = i;
        minL = max(minL, min(odd[v], even[v]) + 1);
        if(leven < lodd){
            dp[i] = (dp[i] + query(1, max(minL, leven + 1), i - 1)) % MOD;
        }
		else if (lodd < leven){
            dp[i] = (dp[i] + query(0, max(minL, lodd + 1), i - 1)) % MOD;
        }
    }
    printf("%d", dp[n] % MOD);
    return 0;
}

更好的阅读体验：https://www.cnblogs.com/To-Carpe-Diem/p/19349977

思路

由于题目的数据范围，我们可以得知，大概是个 $n ^ 3$ 的玩意。

但是我们需要仔细想想怎么计数？

首先，这个玩意和什么有关?

第一肯定是步数，第二是点是否走过，第三是这个点和为我们要的强连通图的关系。

然后我们考虑最难的问题，就是这个强连通图怎么判断，怎么累加答案？我们走到一个点的时候怎么判断其是否能与原来的形成一个强连通呢？还是说其目前自己和其他点成强连通，需要后续的操作去整。

不难发现，其实一个点，其强连通关系只有两种，第一种就是和起点在一个强连通里面，第二种，就是不在起点的强连通里面。

我们定义 $f_{i, j, k}$ 表示目前已经走了 $i$ 步，已经访问了 $j$ 个点，与起点 $1$ 形成的强连通的大小为 $k$。（以下所说的形成强连通均是与 $1$ 形成）

考虑转移。

首先走到点，第一种情况，是没有走过，于是我们有：

$f_{i + 1, j + 1, k} \to f_{i + 1,j + 1, k} + f_{i, j, k} \times (n - j)$

第二种，是走过，但是没有形成强连通的点：

$f_{i + 1, j, k} \to f_{i + 1, j, k} + f_{i, j, k} \times (j - k)$

第三种是，走过，且已经形成了强连通：

$f_{i + 1, j, k} \to f_{i + 1, j, k} + f_{i, j, k} \times k$

于是我们的答案就在 $f_{m, n, n}$。

代码

#include<iostream>
using namespace std;

#define int long long

const int MAXN = 305;
const int MOD = 1e9 + 7;

//f[i][j][k] 走了 i 步，访问了 j 个点，以 1 为根的 scc 大小为 k
int f[MAXN][MAXN][MAXN];

int n, m;

signed main(){
	freopen("rotk.in", "r", stdin);
	freopen("rotk.out", "w", stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> m;
	
	f[0][1][1] = 1;
	
	for(int i = 0;i <= m - 1;i ++){
		for(int j = 1;j <= n;j ++){
			for(int k = 1;k <= n;k ++){
				if(!f[i][j][k]) continue;
				//没走的
				f[i + 1][j + 1][k] += f[i][j][k] * (n - j) % MOD;
				f[i + 1][j + 1][k] %= MOD;
				//走过，但不在 1 的scc
				f[i + 1][j][k] += f[i][j][k] * (j - k) % MOD;
				f[i + 1][j][k] %= MOD;
				//走过，在 1 的 scc
				f[i + 1][j][j] += f[i][j][k] * k % MOD;
				f[i + 1][j][j] %= MOD;
			}
		}
	}
	
	cout << f[m][n][n] % MOD << '\n';
	return 0;
}

更好的阅读体验：https://www.cnblogs.com/To-Carpe-Diem/p/19354572

思路

给定一棵有 $n$ 个节点的树，巡警车从 $1$ 号节点出发遍历所有边后返回，每条边需经过两次，总距离为 $2*(n-1)$。现可新建 $K$ 条边$(k = \{ 1, 2\})$，要求新建的每条边必须恰好经过一次，求规划新建边的方案，使得巡警车的总巡逻距离最小，并输出该最小值。

我们可以发现，对于 $k = 1$ 的情况，显然你求出一条直径，再把直径的两个端点连上，这样是最优的。

但是当 $k = 2$ 的时候，我们需要再连一次，但是这样的话，我们最好选比较长的，最初的想法是选次长的直径，但是我们想想，如果你选的这条新的直径，和原来的直径，有很多重合的点，那么就不是很优，我们为了处理这个重复的玩意，其实可以把原直径的所有边赋为 $-1$，这样的话，我们再找最长的直径，就不会出问题了。

但是这样需要知道一个问题， dfs 求直径是无法解决边权为负的情况，于是我们考虑树形 dp 的方式，直接再记一次直径的长度即可。

设两次的直径长度为 $L_1, L_2$，则最终答案为：

$k = 1$ 时：$2 * (n - 1) - L_1 + 1$

$k = 2$ 时：$2 * (n - 1) - (L_1 - 1) - (L_2 - 1)$

代码

#include<iostream>
#include<cstring>
using namespace std;

const int MAXN = 1e5 + 5;

struct node{
	int to, nxt, len;
}e[MAXN * 2];

int tot = 0, h[MAXN];
int d[MAXN];
bool vis[MAXN];

void add(int x, int y, int len){
	e[++ tot] = {y, h[x], len};
	h[x] = tot;
}

int n, k, d1 = 1, d2 = 0, d3 = 1, d4 = 0;
int f[MAXN];
int dp[MAXN], maxx;

void dfs(int u, int fa){
    dp[u] = 0;
    for(int i = h[u]; i; i = e[i].nxt){
        int v = e[i].to;
        if(v == fa) continue;
        e[i].len = (vis[u] && vis[v]) ? -1 : 1;
        dfs(v, u);
        maxx = max(maxx, dp[u] + dp[v] + e[i].len);
		dp[u] = max(dp[u], dp[v] + e[i].len);
    }
}

void dfs1(int u, int fa){
	for(int i = h[u];i;i = e[i].nxt){
		int v = e[i].to;
		if(v == fa) continue;
		d[v] = d[u] + e[i].len;
		if(d[v] > d[d1]){
			d1 = v;
		}
		dfs1(v, u);
	}
}

void dfs2(int u, int fa){
	f[u] = fa;
	for(int i = h[u];i;i = e[i].nxt){
		int v = e[i].to;
		if(v == fa) continue;
		d[v] = d[u] + e[i].len;
		if(d[v] > d[d2]){
			d2 = v;
		}
		dfs2(v, u);
	}
}

int main(){
	freopen("xunluo.in", "r", stdin);
	freopen("xunluo.out", "w", stdout);
	ios::sync_with_stdio(0);
    cin.tie(0);
	
	cin >> n >> k;
	for(int i = 1;i < n;i ++){
		int a, b; cin >> a >> b;
		add(a, b, 1), add(b, a, 1);
	}

	dfs1(1, 0);
	memset(d, 0, sizeof(d));
	dfs2(d1, 0);
	int l1 = d[d2];

	if(k == 1){
		cout << 2 * (n - 1) - l1 + 1 << '\n';
		return 0;
	}

	memset(vis, 0, sizeof(vis));
	int tmp = d2;
	while(tmp != 0){
		vis[tmp] = true;
		tmp = f[tmp];
	}
	maxx = 0;
	dfs(1, 0);
	int l2 = maxx;

	cout << 2 * (n - 1) - (l1 - 1) - (l2 - 1) << '\n';

	return 0;
}

更好的阅读体验：https://www.cnblogs.com/To-Carpe-Diem/p/19361912

大意

有 $n+1$ 根柱子（编号 $1 \sim n+1$），其中 $1 \sim n$ 号柱子初始时各有 $m$ 个球（球按**自底向上**的顺序摆放），$n+1$ 号柱子初始为空；所有球共包含 $n$ 种颜色，且每种颜色的球恰好有 $m$ 个。

允许执行的操作是：将某根柱子最上方的球移动到另一根柱子的最上方，操作需满足两个条件：

1. 源柱子（移出球的柱子）非空；

2. 目标柱子（移入球的柱子）上的球数量不超过 $m-1$。

要求通过不超过 $820000$ 次上述操作，使得所有同一种颜色的球都汇聚到同一根柱子上（每种颜色最终对应哪根柱子无限制）。

思路

首先，这个题是个构造题，然后我们考虑构造方法，先看特殊性质 $n = 2$ 的时候，也就是说此时只有 $3$ 个柱子和 $2$ 种颜色，那么我们应该怎么去放这个东西呢？

我们将两种颜色用白和黑表示，那么我们很容易想到去分离黑白，如何做呢？如上图，我们先在第二个柱子上空出第一个柱子中黑的个数，这样就可以将第一根柱子黑白分离，再把分离好的放回去，把剩下的没分的整到一根柱子上，再把第一根的黑白分离到两个不同的柱子上，然后把没分离的那根柱子直接按黑白分离即可。

总操作次数是：$5m - k$，$k$ 表示第一个柱子中黑的个数。

我们继续考虑 $n$ 比较大的时候怎么办，我们可以像刚刚的操作一样，对于每一个颜色 $i \in [1, n]$ 依次操作，对于颜色 $i$，先把 $[i + 1, n]$ 的柱子中的颜色 $i$ 全放在柱头，然后直接如下图进行操作即可：

但是经过计算发现以上的构造方式并不能通过本题，我们需要考虑其他的方法。

考虑分治。

我们发现对于 $n  = 2$ 的情况处理起来很容易，要是全部都能当成两个颜色做就好了，于是我们就可以对于当前处理的区间 $[l, r]$ 进行分治 $[l, mid], [mid + 1, r]$，我们将 $[l, mid]$ 的柱子全部整理成颜色小于等于 mid 的，将 $[mid + 1, r]$ 的柱子全部整理成颜色大于 mid 的，每次分治时，可以 $\mathcal{O}(n ^ 2)$ 的去枚举 $i \in [l, mid], r \in [mid + 1, r]$，对 $i$ 和 $j$ 的颜色整理。如果两个柱子中颜色小于等于 mid 的大于 $m$，就将 $i$ 整理，反之。

因此就解决了这道题。

代码

#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
using namespace std;

const int MAXN = 16005;
int n, m;
vector<int> g[MAXN];
bool vis[MAXN];
int S[MAXN], c = 0;

inline int get_id(int x) {
    x--;
    return x;
}

bool dfs(int u) {
    if (vis[u ^ 1]) return false;
    if (vis[u]) return true;
    vis[u] = true;
    S[c++] = u;
    for (int v : g[u]) {
        if (!dfs(v)) return false;
    }
    return true;
}

bool Two_SAT() {
    memset(vis, 0, sizeof(vis));
    for (int i = 0; i < 2 * n; i += 2) {
        if (!vis[i] && !vis[i + 1]) {
            c = 0;
            if (!dfs(i)) {
                while (c > 0) vis[S[--c]] = false;
                if (!dfs(i + 1)) {
                    return false;
                }
            }
        }
    }
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;

    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        int u = get_id(a);
        int v = get_id(b);
        g[u].push_back(v ^ 1);
        g[v].push_back(u ^ 1);
    }

    if (!Two_SAT()) {
        cout << "NIE" << endl;
    } else {
        vector<int> ans;
        for (int i = 0; i < 2 * n; i += 2) {
            if (vis[i]) {
                ans.push_back(i + 1);
            } else {
                ans.push_back(i + 2);
            }
        }
        sort(ans.begin(), ans.end());
        for (int x : ans) {
            cout << x << endl;
        }
    }

    return 0;
}

更好的阅读体验：https://www.cnblogs.com/To-Carpe-Diem/p/19369035

思路

那么，相当于每个党派的两个代表就是两种情况，然后直接按其说的厌恶的关系建边跑 $\text{2 - SAT}$ 即可。

每个党派 $i$ 对应2-SAT的一个布尔变量，其两个代表 $2i$、$2i+1$ 分别对应「变量为真」「变量为假」，题目中“代表a和b互相厌恶” $\to$ 约束：**不能同时选 a 和 b**，即选 a 则必须选 b 的对立代表，选 b 则必须选 a 的对立代表。

先将代表编号转为 $0$ 起始（$a \rightarrow a - 1$），记a对应节点 $u$，b 对应节点 $v$；

互斥约束转化为两条有向边：

 1. $u \rightarrow v \oplus 1$（选 a → 必须选 b 的对立代表）

 2. $v \rightarrow u \oplus 1$（选 b → 必须选 a 的对立代表）

 （$\oplus 1$ 是异或操作，可快速找到每个代表的“对立代表”：偶数变奇数，奇数变偶数）。

代码

#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
using namespace std;

const int MAXN = 16005;
int n, m;
vector<int> g[MAXN];
bool vis[MAXN];
int S[MAXN], c = 0;

inline int get_id(int x) {
    x--;
    return x;
}

bool dfs(int u) {
    if (vis[u ^ 1]) return false;
    if (vis[u]) return true;
    vis[u] = true;
    S[c++] = u;
    for (int v : g[u]) {
        if (!dfs(v)) return false;
    }
    return true;
}

bool Two_SAT() {
    memset(vis, 0, sizeof(vis));
    for (int i = 0; i < 2 * n; i += 2) {
        if (!vis[i] && !vis[i + 1]) {
            c = 0;
            if (!dfs(i)) {
                while (c > 0) vis[S[--c]] = false;
                if (!dfs(i + 1)) {
                    return false;
                }
            }
        }
    }
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;

    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        int u = get_id(a);
        int v = get_id(b);
        g[u].push_back(v ^ 1);
        g[v].push_back(u ^ 1);
    }

    if (!Two_SAT()) {
        cout << "NIE" << endl;
    } else {
        vector<int> ans;
        for (int i = 0; i < 2 * n; i += 2) {
            if (vis[i]) {
                ans.push_back(i + 1);
            } else {
                ans.push_back(i + 2);
            }
        }
        sort(ans.begin(), ans.end());
        for (int x : ans) {
            cout << x << endl;
        }
    }

    return 0;
}

更好的阅读体验：https://www.cnblogs.com/To-Carpe-Diem/p/19361885

思路

这个题目要求我们把给出的状态通过类似华容道的方式，去移动 $0$ 的位置，然后就可以调整其他数的位置。

然后我们考虑把这个棋盘的状态存下来，这样的话我们就可以直接转移，然后我们显然可以把这玩意直接弄成字符串，为了保证答案的最小，直接字符串 $hash$ 存每个字符串的最小值，然后我们每次关注 $0$ 的位置，进行 bfs 即可，新的状态取最小即可。这种已经可以 AC了。

我们继续考虑优化，这里给出 A* 的写法，我们是否有很多没必要的状态呢？A* 的剪枝就很类似于贪心的思路，我们可以维护一个东西，每次在 bfs 的时候取你觉得比较优的答案。这时候我们需要维护一个估价函数，对于这个题的话，我们可以认为，位置正确的越多，那么这个东西显然很优，先对这些正确位置比较多的进行拓展，那么我们有 $F(S)$ 就是表示当前的状态下正确的位置的个数，然后我们去维护一个小根堆，里面的值是 $S_{now} + F(S)$，这个东西越小显然越优，我们优先去拓展，如果已经到了目标状态，那么就没必要继续搜索了，这个答案一定最优。这个东西就很类似最短路的 dijkstra，每次都取最小的。然后显然我们的 $F(S)$ 是要小于等于实际的可能花费的，因此这样的拓展一定最优。

代码

#include<iostream>
#include<cmath>
#include<unordered_map>
#include<queue>
using namespace std;

string s;
int xx[] = {1, 0, 0, 0, 1, 2, 2, 2, 1};
int yy[] = {1, 0, 1, 2, 2, 2, 1, 0, 0};
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};

int f(string now){
	int sum = 0;
	for(int i = 0;i < 9;i ++){
		int x = i / 3, y = i % 3;
		int p = x * 3 + y;
		int v = now[p] - '0';
		sum += (abs(x - xx[v]) + abs(y - yy[v]));
	}
	return sum;
}

int Astar(string now){
	unordered_map<string, int> d;
	priority_queue<pair<int, string> > q;
	string tag = "123804765";
	q.push(make_pair(-f(now), now));
	d[now] = 0;
	while(!q.empty()){
		string u = q.top().second;
		if(u == tag) return d[tag];
		q.pop();
		int k = u.find('0');
		int x = k / 3, y = k % 3;
		for(int i = 0;i < 4;i ++){
			int nx = x + dx[i], ny = y + dy[i];
			if(nx < 0 || ny < 0 || nx >= 3 || ny >= 3) continue;
			if(nx * 3 + ny > 8 || nx * 3 + ny < 0) continue;
			string t = u;
			swap(t[x * 3 + y], t[nx * 3 + ny]);
			if(!d.count(t)){
				d[t] = d[u] + 1;
				q.push(make_pair(-f(t) - d[t], t));
			}
		}
	}
	return d[tag];
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> s;
	cout << Astar(s) << '\n';
	return 0;
}