ICPC Regional Hanoi 2024 Editorial - Y

Cho một mê cung gồm $n$ hành lang vuông góc liên tiếp nhau, mỗi hành lang có độ dài $l_{i}$. Bạn đứng ở điểm bắt đầu của hành lang 1.

Trước khi vượt mê cung. bạn có thể chọn trước độ dài tốc biến $m$ nguyên để di chuyển từ điểm bắt đầu của hành lang 1 đến điểm kết thúc của hành lang $n$.

Ở mỗi thời điểm nguyên bạn sẽ tốc biến đúng $m$ đơn vị độ dài về phía trước trong 1 giây, nếu cú tốc biến này không chuẩn (khoảng cách từ điểm bạn tốc biến đến điểm cuối của hành lang hiện tại nhỏ hơn $m$ đơn vị) thì bạn sẽ tốc biến đến điểm cuối của hành lang và bị choáng $1$ giây, điều này áp dụng cả với hành lang cuối. Ngược lại, bạn có thể tốc biến tiếp ngay lập tức mà không bị choáng.

Tính thời gian ngắn nhất có thể để ra khỏi mê cung khi chọn $m$ tối ưu.

Giới hạn: $1\le n\le10^6,1\le l_{i}\le10^9.$

Vì quá trình di chuyển qua các hành lang là độc lập với nhau, ta có thể sắp xếp lại các hành lang theo thứ tự: $l_1 \le l_2 \le \dots \le l_n$.

Chúng ta bắt đầu với một số nhận xét tham lam như sau về đáp án tối ưu:

1. Với $m$ cho trước thì ta có công thức tổng thời gian hoàn thành:

2. Ta nhận thấy rằng đáp án tối ưu có cận dưới và cận trên hiển nhiên là $n$ và $2n - 1$. Cận dưới xảy ra khi toàn bộ $l_i$ bằng nhau, khi đó ta chọn $m = l_i$, còn cận trên xảy ra khi ta cho $m = l_n$.
3. Luôn tồn tại $m$ tối ưu là một trong các $l_i$, nên ta chỉ cần xét $m \in \{l_1, l_2, \dots, l_n\}$. Thật vậy, giả sử giá trị $m$ tối ưu là $m_1$ không trùng với bất cứ $l_i$ nào. Khi này với các $l_i < m_1$ thì ta sẽ mất đúng 2 giây để đi qua, còn với $l_i > m_1$ thì ta sẽ mất ít nhất 2 giây để đi qua. Do đó $f(m_1) \ge 2n > 2n - 1 \ge f(l_n)$, mâu thuẫn với việc $m_1$ tối ưu nên ta có điều phải chứng minh.

Nhận xét thứ 3 gợi ý rằng chúng ta cần duyệt qua tất cả các $l_i$ khác nhau và tính nhanh được $f(l_i)$. Chúng ta chia mảng thành 3 phần:

1. Phần mà $l_j < l_i$, mỗi $j$ mất 2 giây.
2. Phần $l_j = l_i$, mỗi $j$ mất 1 giây.
3. Phần còn lại với mỗi $j$ mất $\left[ \frac{l_j}{l_i} \right] + [l_j \bmod l_i \neq 0]$ giây.

Mẫu chốt của bài toán là tính phần 3 đủ nhanh khi 2 phần trước ta có thể tính trong $\mathcal{O}(1)$. 

1
#include <bits/stdc++.h>
2

3
using namespace std;
4

5
// Hàm tính thời gian đi qua hành lang độ dài len với bước nhảy m
6
// Công thức: ceil(len/m) + (1 nếu len không chia hết cho m)
7
int calculate_cost(int len, int m) {
8
    if (len % m == 0) {
9
        return len / m;
10
    } else {
11
        return (len / m) + 2; // 1 bước cuối + 1 giây choáng
12
    }
13
}
14

15
void solve() {
16
    int n;
17
    cin >> n;
18
    vector<int> a(n);
19
    for (int i = 0; i < n; ++i) {
20
        cin >> a[i];
21
    }
22

23
    // Sắp xếp để gom nhóm các hành lang có cùng độ dài
24
    // và dễ dàng xử lý các phần tử nhỏ hơn/lớn hơn.
25
    sort(a.begin(), a.end());
26

27
    // Khởi tạo kết quả ban đầu: trường hợp tệ nhất mỗi hành lang tốn 2s
28
    // (ví dụ chọn m > max(a_i), tất cả đều nhảy quá đà và bị choáng)
29
    long long min_total_time = 2LL * n;
30

31
    for (int i = 0; i < n;) {
32
        int m = a[i]; // Chọn độ dài bước nhảy m bằng độ dài hành lang hiện tại
33

34
        // Tìm vị trí cuối cùng có giá trị bằng a[i]
35
        // Đoạn [i, j] là các hành lang có độ dài bằng m (tốn 1s)
36
        int j = i;
37
        while (j < n && a[j] == m) {
38
            j++;
39
        }
40
        // j lúc này là chỉ số của phần tử đầu tiên > m (hoặc n)
41

42
        // Tính chi phí cơ sở cho lần chọn m này:
43
        // 1. Các hành lang < m: tốn 2s (nhảy quá đà ngay bước 1)
44
        // 2. Các hành lang = m (từ i đến j-1): tốn 1s
45
        // 3. Các hành lang > m (từ j đến n-1): giả sử tạm tính tối thiểu là 2s
46
        //    (Thực tế sẽ >= 2s. Ta sẽ cộng phần chênh lệch sau)
47
        long long current_time = i * 2 + (j - i) * 1 + (n - j) * 2;
48

49
        // Tối ưu: Duyệt các phần tử lớn hơn m từ lớn về bé.
50
        // Cộng thêm chi phí thực tế chênh lệch so với giả định (2s).
51
        // Nếu tổng vượt quá kết quả tốt nhất hiện có thì dừng ngay.
52
        for (int k = n - 1; k >= j; --k) {
53
            int actual_cost = calculate_cost(a[k], m);
54
            current_time += (actual_cost - 2);
55
            if (current_time >= min_total_time) {
56
                break;
57
            }
58
        }
59

60
        min_total_time = min(min_total_time, current_time);
61

62
        // Chuyển sang nhóm độ dài tiếp theo
63
        i = j;
64
    }
65

66
    cout << min_total_time << "\n";
67
}
68

69
int main() {
70
    ios_base::sync_with_stdio(false);
71
    cin.tie(NULL);
72

73
    int tc;
74
    cin >> tc;
75
    while (tc--)
76
        solve();
77
    return 0;
78
}

Ý tưởng tóm gọn như sau: Ở một thời điểm bất kỳ, giá trị của min_total_time là ngưỡng quyết định xem l[i] hiện tại có tối ưu hơn không. Để có thể quyết định nhanh, ta duyệt qua các giá trị từ lớn đến nhỏ, nếu đến một lúc nào đó current_time lớn hơn ngưỡng tối ưu hiện tại thì ta có thể loại luôn l[i].

Độ phức tạp của 2 vòng lặp khi này không phải $\mathcal{O}(n^2)$ mà là $\mathcal{O}(n)$. Thật vậy, xét một độ dài phân biệt $m$ với tần suất freq(m):

1. current_time khởi đầu bằng $2n - \text{freq}(m)$ (mọi hành lang $> m$ được tạm tính 2 giây).
2. min_total_time luôn $\le 2n - 1$ sau lần xét đầu tiên (nhận xét 2).
3. Mỗi hành lang có độ dài $l > m$ và $l \neq 2m$ tốn ít nhất 3 giây: nếu $m < l < 2m$ thì $\left\lceil \frac{l}{m} \right\rceil = 2$ và không chia hết, nếu $l > 2m$ thì $\left\lceil \frac{l}{m} \right\rceil \ge 3$. Mỗi hành lang như vậy cộng thêm ít nhất 1 vào current_time. Hành lang $l = 2m$ tốn đúng 2 giây, cộng thêm 0.

Do đó sau khi duyệt qua không quá $\text{freq}(m)$ hành lang loại thứ nhất, current_time đã đạt min_total_time và vòng lặp trong dừng; xen giữa có thể có thêm không quá $\text{freq}(2m)$ hành lang loại thứ hai. Vậy với mỗi $m$ phân biệt, vòng lặp trong chạy không quá $\text{freq}(m) + \text{freq}(2m) + 1$ lần, và tổng đại lượng này trên mọi $m$ phân biệt là $\mathcal{O}(n)$. 

Độ phức tạp cuối cùng của bài là $\mathcal{O}(n \log n)$ do sắp xếp.

Cho đồ thị vô hướng đầy đủ gồm $n$ đỉnh, với ma trận trọng số $d_{i,j}$ biểu diễn khoảng cách giữa mọi cặp đỉnh $(i, j)$. Một đường đi đơn gồm $t$ đỉnh phân biệt, với giới hạn độ dài $2 \le t \le k$. Chi phí của một tuyến đường bằng tổng trọng số các cạnh liên tiếp trên đường đi đó.

Cho $m$ cặp đỉnh $(u, v)$. Cần chọn một tập các tuyến đường sao cho với mỗi cặp $(u, v)$, tồn tại ít nhất một tuyến đường trong tập đó chứa cả hai đỉnh $u$ và $v$. Tìm tập các tuyến đường thỏa mãn điều kiện phủ sao cho tổng chi phí của tất cả các tuyến đường được chọn là nhỏ nhất. In ra các đường đi đó.

Giới hạn: $2\le k\le n\le19,1\le m\le15$.

Đây là một bài toán ghép cơ học của ba bài toán quy hoạch động lại với nhau, và cả ba bài đều phải lưu thông tin truy vết.

Bài toán con 1: TSP DP trên tập đỉnh

Đặt $f(S, u)$ là chi phí nhỏ nhất của một đường đi đơn ghé qua chính xác tập đỉnh $S \subseteq V$ và kết thúc tại đỉnh $u \in S$. Ta có $f(\{u\}, u) = 0 \ \forall u \in V$.

Công thức truy hồi: Với mọi $S \subseteq V$ thỏa mãn $\vert{}S\vert{} < K$, với $u \in S$ và $v \in V \setminus S$:

Chi phí nhỏ nhất để tạo thành một tuyến đường hợp lệ đi qua đúng tập đỉnh $S$ là:

Truy vết: $p_1(S, u)$ là mảng lưu lại đỉnh ngay trước $u$ trên hành trình đi qua tập đỉnh $S$ và kết thúc tại $u$.

Độ phức tạp: $\mathcal{O}(n^2\times2^{n})$.

Bài toán con 2: DP tính chi phí nhỏ nhất của tuyến đường đơn phủ tập cặp

Xét một tập các cặp quan trọng $P \subseteq R$ (kí hiệu $R$ là tập tất cả các cặp quan trọng). Đặt $\text{span}(P) \subseteq V$ là tập hợp tất cả các đỉnh của các cặp nằm trong $P$:

Ta có các nhận xét sau:

1. Điều kiện hợp lệ: Nếu $\vert{}\text{span}(P)\vert{} > K$, không tồn tại một tuyến đường đơn nào có thể phủ toàn bộ tập cặp $P$.
2. Thêm đỉnh bổ trợ: Nếu $\vert{}\text{span}(P)\vert{} \le K$, tuyến đường đơn phủ $P$ có thể ghé qua các đỉnh trong $P$ cùng một tập các đỉnh bổ trợ $X \subseteq V \setminus \text{span}(P)$.

Chi phí nhỏ nhất của chỉ một tuyến đường đơn để phủ trọn vẹn tập cặp $P$ được định nghĩa bởi hàm $g(P)$, duyệt qua tất cả các tập đỉnh bổ trợ $X$ sao cho vẫn thoả mãn điều kiện hợp lệ.

Truy vết: $p_2(P) = (S_P, u_P)$ đạt chi phí cực tiểu cho hàm $g(P)$, trong đó $S_P = \text{span}(P) \cup X_P$ là tập đỉnh hoàn chỉnh và $u_P \in S_P$ là đỉnh kết thúc của tuyến đường đó.

Độ phức tạp: Không thể tính chính xác do có nhiều ràng buộc (tập đỉnh span, điều kiện hợp lệ). Tuy nhiên cũng chính vì vậy mà phần này sẽ chạy tương đối nhanh.

Bài toán con 3: DP phân hoạch tập cặp

Đặt $h(P)$ là tổng chi phí nhỏ nhất để phủ tập các cặp $P \subseteq R$ bằng một hoặc nhiều tuyến đường. Ta có $h(\emptyset) = 0$. Với mọi tập cặp $P \subseteq R$ khác rỗng, ta tách $P$ thành một tập con $Q \subseteq P$ (do một tuyến đường đơn đảm nhận) và phần còn lại $P \setminus Q$, và tính hàm $h$ như sau:

Giá trị $h(R)$ chính là kết quả tối ưu của bài toán.

Truy vết: $p_3(P)$ lưu lại tập con các cặp $Q \subseteq P$ được chọn để đảm nhận bởi 1 tuyến đường đơn tại bước chuyển trạng thái của $h(P)$.

Độ phức tạp: $\mathcal{O}(3^n)$ (do duyệt submask).

Truy vết

Bắt đầu từ tập $R$:

1. Dùng $p_3(R)$ để phân rã tập $R$ thành các tập con rời nhau $Q_1, Q_2, \dots, Q_r$.
2. Với mỗi $Q_i$, dùng $p_2(Q_i)$ để lấy tập đỉnh $S_i = \text{span}(Q_i) \cup X_i$ đạt giá trị cực tiểu của hàm $g(Q_i)$ và đỉnh kết thúc $u$.
3. Với mỗi tập $S_{i}$ và $u$ thu được, dùng $p_1(S_i, u)$ để đi ngược từ đỉnh kết thúc về đỉnh xuất phát, thu được thứ tự xuất hiện của các đỉnh trên tuyến đường.
4. Đảo ngược thứ tự đỉnh thu được của các tuyến đường và in ra đáp án.

Cho đồ thị liên thông vô hướng có $n$ đỉnh, $m$ cạnh có trọng số.

Bạn T chọn một hoán vị $p_1,p_2,\ldots,p_n$ của các đỉnh từ $1$ đến $n$, thể hiện lịch trình vận chuyển hàng gồm $n - 1$ chặng, mỗi chặng từ $p_i$ đến $p_{i + 1}$. Bạn M nhận được hoán vị của T và cần tìm hành trình cụ thể cho từng chặng đảm bảo tổng chi phí của toàn bộ lịch trình là nhỏ nhất có thể.

• Chi phí của một chặng là trọng số lớn nhất của cạnh trên đường đi qua.
• Tổng chi phí của một hoán vị là tổng chi phí của $n - 1$ chặng.

T muốn tìm một hoán vị sao cho tổng chi phí mà M tìm được là lớn nhất có thể. Tìm hoán vị này và in ra chi phí mà M tìm được cho hoán vị đó. Nếu có nhiều hoán vị thoả mãn thì có thể chọn một hoán vị bất kì.

Giới hạn: $2 \le n \le 5 \times 10^5, n - 1 \le m \le 5 \times 10^5$, trọng số cạnh không quá $10^9$.

Phân tích hành vi của M và T

Sau khi nhận được hoán vị của bạn T, bạn M muốn cực tiểu hóa tổng chi phí của $n - 1$ chặng. Do đó, với mỗi chặng, bạn M muốn tìm đường đi từ đi từ $p_i$ đến $p_{i + 1}$ sao cho cạnh có trọng số lớn nhất của đường đi là nhỏ nhất. Ta có một kết quả quen thuộc như sau: Đường đi giữa hai đỉnh $u$ và $v$ có (max trọng số cạnh) nhỏ nhất chính là đường đi trên cây khung nhỏ nhất (MST). Thật vậy:

1. Nếu ta có một đường đi từ $u$ đến $v$ có trọng số cạnh lớn nhất là $C$, thì mọi cạnh trên đường đi đó đều có trọng số $\le C$.
2. Giả sử rằng, giá trị nhỏ nhất của (trọng số cạnh lớn nhất) của một đường đi bất kì từ $u$ đến $v$ là $C_{\min}$ thì:
   1. Nếu sử dụng các cạnh trọng số $\le C_{\min}$ thì có thể đi được giữa $u$ và $v$.
   2. Nếu chỉ sử dụng các cạnh trọng số $\le C_{\min} - 1$ thì không thể đi được giữa $u$ và $v$.

Kết quả trên cũng là hệ quả trực tiếp của thuật toán Kruskal: trước khi xét một cạnh $(u, v)$ trọng số $c$ nào đó; ta đã xét qua mọi cạnh có trọng số $\le c - 1$ và thử cho chúng vào cây khung. Như vậy, nếu một cạnh $(u, v)$ trọng số $c$ mà được cho vào cây khung, đồng nghĩa với việc chỉ sử dụng các cạnh trọng số $\le c - 1$ là không đủ để liên thông $u$ và $v$.

Qua đó ta rút ra nhận xét quan trọng sau: Hành vi của bạn M thực chất là tìm ra một MST bất kỳ, và với mỗi cặp $p_i, p_{i + 1}$ trong hoán vị của bạn T, bạn M tìm đường đi từ $p_i$ đến $p_{i + 1}$ trên MST đó.

T nhận ra được suy nghĩ của M, do đó, T cũng dựng ra một MST bất kỳ. Để cực đại hóa tổng chi phí, T giải bài toán sau: Tìm hoán vị $p$ sao cho tổng (trọng số cạnh lớn nhất) trên tất cả các đường đi từ $p_i$ đến $p_{i + 1}$ là lớn nhất có thể.

Kruskal Reconstruction Tree (KRT)

Xét một MST bất kì của đồ thị. Gọi cạnh có trọng số lớn nhất trên MST đó là $C_{\max}$, và $u, v$ là hai đỉnh thuộc hai thành phần liên thông khác nhau bị tách ra bởi $C_{\max}$. Khi đó, cạnh trọng số lớn nhất trên đường đi giữa u và v luôn là $C_{\max}$. Ta có thể tiếp tục áp dụng nhận xét này một cách đệ quy:

1. dùng cạnh lớn nhất chia cây thành hai phần;
2. trong mỗi phần, tiếp tục dùng cạnh lớn nhất để chia cây thành hai phần nhỏ hơn nữa
3. lặp lại cho đến khi mỗi phần chỉ còn một đỉnh.

Quá trình chia tách này tạo thành một cây nhị phân. Các lá đại diện cho các đỉnh ban đầu, còn mỗi đỉnh trong đại diện cho cạnh đã chia một cây con thành hai phần. Cây này được gọi là Kruskal Reconstruction Tree (KRT) và có thể được dựng trong quá trình chạy thuật toán Kruskal. Đầu tiên, ta sắp xếp các cạnh theo trọng số tăng dần. Mỗi đỉnh của đồ thị ban đầu là một thành phần liên thông và được biểu diễn bởi một đỉnh lá trên KRT. Khi xét một cạnh trọng số $w$ nối hai thành phần khác nhau, ta thực hiện các bước:

1. tạo một đỉnh mới $x$ có trọng số $w$;
2. đặt hai gốc đại diện cho hai thành phần làm hai con trực tiếp của $x$;
3. dùng DSU hợp nhất hai thành phần;
4. lấy $x$ làm gốc đại diện cho thành phần mới.

Thuật toán tính kết quả tối ưu

Gọi $sz(x)$ là số lá trong cây con gốc $x$ của KRT, và $w_x$ là trọng số của đỉnh $x$. Ta bắt đầu từ gốc của KRT và đi xuống một nhánh duy nhất. Tại đỉnh hiện tại $x$, gọi hai cây con là $A$ và $B$, giả sử $sz(A) \ge sz(B)$.

Nếu $sz(A) > \frac{n}{2}$, ta tiếp tục đi xuống $A$ và coi toàn bộ cây con $B$ là một nhóm đã được tách ra khỏi nhánh chính.

Ngược lại, nếu cả hai cây con đều có không quá $\frac{n}{2}$ lá, ta dừng lại tại $x$. Đây là đỉnh đầu tiên trên đường đi mà không còn cây con nào chiếm quá nửa tổng số lá. Như vậy, các lá được chia thành ba nhóm:

• ​first: các lá trong cây con thứ nhất của $x$;
• ​second: các lá trong cây con thứ hai của $x$;
• ​other: các lá thuộc những cây con nhỏ đã bị tách ra trong quá trình đi từ gốc xuống $x$.

Đặt kích thước của ba nhóm lần lượt là $a$, $b$ và $o$. Ta có $a + b + o = n$. Đồng thời, do cách chọn đỉnh dừng, ta có $a \le \frac{n}{2}$ và $b \le \frac{n}{2}$.

Xét một bước trên đường đi, tại đó ta đi từ đỉnh $y$ xuống cây con lớn và tách ra cây con nhỏ $S$. Mọi lá thuộc $S$ có LCA với mọi lá thuộc nhánh lớn bằng $y$. Vì vậy, nếu một lá của $S$ được đặt giữa hai lá thuộc nhánh lớn trong hoán vị, nó tạo ra hai cặp liên tiếp có đóng góp bằng $w_y$ : ..., u, s, v, ... với $s \in S$ và $u,v$ thuộc nhánh lớn. Mỗi đỉnh trong một hoán vị có nhiều nhất hai hàng xóm, nên một lá của $S$ có thể tạo nhiều nhất hai cặp đi qua phép chia tại $y$. Do đó, toàn bộ cây con $S$ đóng góp nhiều nhất $2 \cdot sz(S) \cdot w_y.$

Thuật toán sẽ dựng hoán vị sao cho mọi lá của $S$ đều nằm giữa hai lá thuộc nhánh chính, nên giới hạn này đạt được. Vì vậy, mỗi khi tách một cây con nhỏ $S$, ta cộng $2 \cdot sz(S) \cdot w_y$ vào đáp án. Sau đó ta tiếp tục đi xuống cây con lớn.

Dựng hoán vị thoả mãn

Sau khi tìm được đỉnh dừng $x$, ta thu thập các lá của hai cây con vào hai danh sách first​ và second​, còn tất cả lá đã bị tách ra được đưa vào other. Ta dựng hoán vị như sau, với ý tưởng chính là xen kẽ các danh sách lá sao cho đạt được các giới hạn trên đã chỉ ra.

Đầu tiên, với mỗi lá $v$ trong other:

1. lấy một lá $u$ nào đó từ danh sách đang có nhiều phần tử hơn giữa first​ và second;
2. đưa lá đó vào hoán vị;
3. đưa tiếp $v$ vào hoán vị.

Thứ tự được tạo ra có dạng: $u_1, v_1, u_2, v_2, \dots, u_o, v_o$ trong đó mỗi $u_i$ thuộc cây con của đỉnh dừng, còn mỗi $v_i$ thuộc other.

Sau khi dùng hết other, thuật toán tiếp tục lấy một lá từ danh sách đang có nhiều phần tử hơn cho tới khi cả hai danh sách rỗng. Ta có $|a-b| \le o.$ Thật vậy, giả sử $a \ge b$. Vì $a \le \frac{n}{2}$ nên $a-b \le n-a-b=o$.

Trong bước đầu tiên, ta đã lấy đúng $o$ lá từ first​ và second, mỗi lần đều lấy từ danh sách lớn hơn. Vì vậy, sau khi ghép hết với $o$ lá trong other, số phần tử còn lại của hai danh sách là bằng nhau. Ta sẽ xếp xen kẽ từng cặp phần tử của hai danh sách này ngay tiếp sau bước 1, và hoán vị sẽ có dạng: $u_1, v_1, u_2, v_2, \dots, u_o, v_o, a_1, b_1, a_2, b_2, \dots$ . Mọi cặp $a_i, b_i$​ liên tiếp còn lại đều gồm một lá thuộc first​ và một lá thuộc second, nên LCA của chúng chính là đỉnh dừng $x$. Mỗi cặp như vậy đóng góp $w_x$.

Toàn bộ hoán vị có $n-1$ cặp liên tiếp. Trong đó $2o$ cặp liên tiếp đã được tạo bởi các lá thuộc other ($u_1, v_1, u_2, v_2, \dots, u_o, v_o, a_1$), nên số cặp còn lại là $n - 1 - 2o$. Vì vậy, tại đỉnh dừng $x$, ta cộng thêm $(n-1-2o)w_x$ vào đáp án.

Chứng minh tính đúng đắn

Tại mỗi đỉnh $y$ trên đường đi xuống, cây con nhỏ $S$ có $sz(S)$ lá. Mỗi lá chỉ có tối đa hai hàng xóm trong hoán vị, nên số cặp nối một lá của $S$ với phần còn lại không thể vượt quá $2 \cdot sz(S)$. Chỉ những cặp như vậy mới có thể có LCA bằng $y$. Do đó, đóng góp tại phép chia này không thể vượt quá $2 \cdot sz(S) \cdot w_y$, Thuật toán đặt mỗi lá của $S$ giữa hai lá thuộc nhánh lớn, nên đạt đúng giới hạn trên.

Tại đỉnh dừng $x$, sau khi dành $2o$ cặp cho các lá thuộc other, chỉ còn $n-1-2o$ cặp. Trọng số của mỗi cặp này không thể lớn hơn $w_x$, vì cả hai đầu đều nằm trong cây con của $x$. Thuật toán xen kẽ hai cây con của $x$, khiến tất cả các cặp còn lại có LCA đúng bằng $x$ và cùng đóng góp $w_x$.

Như vậy, ta đã chứng minh thuật toán dựng hoán vị đạt giới hạn trên, nên hoán vị dựng được là tối ưu.

Cho một xâu nhị phân $s$ độ dài $n$ ($s_i \in \{0, 1\}$) và một số nguyên dương $m \ge 3$. Dãy $h$ được tạo theo công thức:

• $h_0 = 0$
• $h_i = (2 \cdot h_{i-1} + s_i) \bmod m$ với mọi $1 \le i \le n$

Cho xâu $k$ độ dài $n$ biểu diễn quan hệ so sánh giữa các cặp phần tử liên tiếp trong dãy $h$:

• $k_i =$ '<' nếu $h_{i-1} < h_i$
• $k_i =$ ‘=’ nếu $h_{i-1} = h_i$
• $k_i =$ '>' nếu $h_{i-1} > h_i$

Yêu cầu: Kiểm tra xem xâu $k$ có hợp lệ hay không (tức là có tồn tại xâu nhị phân $s$ nào tạo ra $k$ này hay không). 

1. Nếu xâu $k$ không hợp lệ, in ra impossible. 
2. Nếu xâu $k$ hợp lệ, với mỗi vị trí $i$ ($1 \le i \le n$), xác định xem ký tự $s_i$ có cố định (luôn là 0 hoặc luôn là 1 trong mọi xâu $s$ thỏa mãn $k$) hay không, nếu không cố định in ra ? ở vị trí đó.

Theo định nghĩa của dãy $h$ và phép chia lấy dư, tồn tại $q_{i}\in\left\lbrace0,1\right\rbrace$ sao cho: 

Xét các trường hợp của $k_{i}$: