Bài toán

Cho một dãy số ~D = \{d_0, d_1, \ldots, d_{n - 1}\}~ và ~n~ vị trí được đánh số ~V = \{0, 1, \ldots, n - 1\}~ xếp thành vòng tròn. Ta cần tìm một hoán vị ~P: \{0, 1, \ldots, n - 1\} \rightarrow V~, trong đó ~P_i~​ là vị trí xuất phát của bộ giáp thứ ~i~ (có giá trị ~d_i~​).

Sau khi di chuyển, vị trí đích của bộ giáp thứ ~i~ là ~F_i ​= (P_i​ + d_i​) \pmod{n}~. Bài toán yêu cầu ~F = \{F_0​, \ldots, F_{n - 1}\}~ cũng phải là một hoán vị của ~V~.

Ý tưởng quy về hệ phương trình

Bài toán trên tương đương với việc tìm hai hoán vị ~x~ và ~y~ của ~V = \{0, 1, \ldots, n - 1\}~ sao cho với mọi ~i \in \{0, 1, \ldots, n - 1\}~: $$ x_i + y_i \equiv d_i \pmod{n} $$

Chứng minh tính tương đương: Giả sử ta tìm được hai hoán vị ~x, y~. Ta đặt:

• ~x_i~​ là vị trí đích của nhóm ~i~. Vì ~x~ là hoán vị nên ~F = x~ là một hoán vị đích hợp lệ.
• ~P_i ​= (n - y_i​) \pmod{n}~. Vì ~y~ là một hoán vị của ~V~, ~P~ cũng là một hoán vị của ~V~ (chỉ là một phép ánh xạ ~k \rightarrow n - k~ và ~0 \rightarrow 0~).

Ta kiểm tra ~P_i​~ có phải là vị trí xuất phát hợp lệ không: $$ \begin{align*} (P_i + d_i) \pmod{n} &\equiv ((n - y_i) + d_i) \pmod{n} \\ &\equiv (-y_i + d_i) \pmod{n} \\ &\equiv (-y_i + (x_i + y_i)) \pmod{n} \\ &\equiv x_i \pmod{n} \end{align*} $$

Vị trí đích ~x_i~​ khớp với yêu cầu. Do đó, bài toán quy về tìm hai hoán vị ~x, y~.

Điều kiện cần và đủ để tồn tại nghiệm

Mệnh đề: Tồn tại hai hoán vị ~x, y~ thỏa mãn ~x_i + y_i \equiv d_i \pmod{n}~ khi và chỉ khi $$ \sum{d_i} \equiv 0 \pmod{n} $$

Chứng minh (Điều kiện cần):

Giả sử tồn tại ~x, y~ là hai hoán vị thỏa mãn. Khi đó: $$ \begin{align*} \sum_{i = 0}^{n - 1}{d_i} &\equiv \sum_{i = 0}^{n - 1}{x_i + y_i} \pmod{n} \\ &= \sum_{i = 0}^{n - 1}{x_i} + \sum_{i = 0}^{n - 1}{y_i} \pmod{n} \end{align*} $$

Vì ~x~ và ~y~ đều là hoán vị trên ~\{0, 1, \ldots, n - 1\}~ nên $$ \sum_{i = 0}^{n - 1}{x_i} = \sum_{i = 0}^{n - 1}{y_i} = \dfrac{n(n - 1)}{2} $$

Do đó $$ \sum_{i = 0}^{n - 1}{d_i} \equiv 2 \cdot \dfrac{n(n - 1)}{2} \equiv n(n - 1) \equiv 0 \pmod{n} $$

Chứng minh điều kiện đủ:

Phần này sẽ được chứng minh thông qua bài giải bên dưới.

Xây dựng nghiệm

Ban đầu đặt $$ x_i = y_i = i, \quad \forall i \in \{0, 1, \ldots, n-2\} $$

Lý do: Ta cố ý để trống vị trí ~n - 1~. Điều này tạo ra một "khoảng trống" trong tập hợp hoán vị, sẽ được dùng để sửa trùng sau này.

Ta có ~x, y~ đều là hoán vị, nhưng ~x_i + y_i \equiv 2i~, chưa thoả mãn điều kiện ~x_i + y_i \equiv d_i \pmod{n}~. Vì thế ta cần chỉnh lại sai số qua việc tính sai số với mọi ~i~ từ ~0~ đến ~n - 2~: $$ \Delta_i = (d_i - (x_i + y_i)) \bmod{n} $$ Ta cập nhật lại ~x_i~: $$ x_i := (x_i + \Delta_i) \bmod{n} $$

Nhận xét: Sau mỗi lần cập nhật, ~x_i + y_i \equiv d_i \pmod{n}~ được thoả mãn, nhưng có thể làm ~x~ không còn là hoán vị. Nên sau khi cập nhật ~x_i~, ta phải kiểm tra xem có tồn tại ~j \neq i~ mà ~x_j = x_i~ hay không, nếu có thì phải "sửa" vị trí ~j~ thông qua ~y~ mà ta chưa sử dụng.

Thuật toán sửa trùng

Nếu trùng tại vị trí ~u~, thì tồn tại một giá trị ~y_{miss} \in \{0, \ldots n - 1\}~ chưa xuất hiện trong tập ~y~ (do ta cố ý để trống một vị trí ngay bước khởi đầu). Ta có thể cập nhật ~y_u~ thành ~y_{miss}~ mà vẫn thoả mãn hoán vị ~y~.

Chứng minh:

Tổng toàn bộ hoán vị ~\{0, 1, \ldots, n - 1\}~ là: $$ S = \dfrac{n(n - 1)}{2} $$

Tổng của hoán vị ~y~ hiện tại là: $$ sum_{y} = \sum_{i = 0}^{n - 1}{y_i} $$

Giá trị duy nhất còn thiếu $$ y_{miss} = S - sum_{y} $$

Nên sai số sử dụng cho ~y_u~ là: $$ \delta = (y_{miss} - y_u) \pmod{n} $$

Mà do khi ta cập nhật ~y_u~ như vậy, thì điều kiện ~x_u + y_u \equiv d_u \pmod{n}~ không còn thoả mãn, nên ta cũng phải cập nhật ~x_u~ và ~y_u~: $$ \begin{align*} y_u &:= (y_u + \delta) \bmod{n} = y_{miss} \\ x_u &:= (x_u - \delta + n) \bmod{n} \end{align*} $$

Khi đó: $$ x_u + y_u = (x_u - \delta) + (y_u + \delta) \equiv d_u \pmod{n} $$

Nhưng việc chỉnh sửa ~x_u~ như vậy vẫn có khả năng trùng với các vị trí khác, ta phải kiểm tra tồn tại ~i~ (~i \neq u~) nào mà ~x_i = x_u~ và phải sửa trùng tiếp tục tại vị trí ~i~.

Chứng minh tại sao không vòng lặp vô tận:

• Mỗi khi ta sửa trùng tại vị trí ~u~, ~y_u~ được cập nhật thành giá trị ~y_{miss}~ hiện tại.
• Giá trị ~y_u~ cũ trở thành ~y_{miss}~ mới.
• Chuỗi đệ quy tạo ra thành đường đi (Fix(u) -> Fix(k) -> Fix(l) -> ...), trong đó các giá trị ~y~ được hoán đổi.
• Vì ~y~ là hữu hạn, chuỗi này không thể tạo vòng lặp vô tận và dừng lại.

Một chuỗi Fix (ví dụ: ~u \rightarrow k \rightarrow j~) phải có các chỉ số phân biệt.

• Giả sử chuỗi là ~u \rightarrow k \rightarrow u~.
• Fix(u): ~y_u := y_{miss}~.
• Giả sử ~x_{u}^{new} = x_k~. Ta phải gọi Fix(k).
• Fix(k): ~y_k := y_{u}^{old}~.
• Giả sử ~x_{k}^{new} = x_u~ (cũ). Nhưng ~x_u~​ không còn giá trị cũ nữa.
• Do đó, việc sửa trùng và va chạm luôn xảy ra giữa một giá trị ~x~ mới và một giá trị ~x~ cũ. Một khi ~x_u​~ đã được cập nhật, nó không thể là mục tiêu (giá trị cũ) của một va chạm trong cùng một chuỗi nữa.
• Vì có ~n - 1~ số ~y~, một chuỗi đệ quy Fix có độ dài tối đa là ~n - 1~. Nó phải dừng.

Fact: Bản chất của thuật toán này là một thuật toán tìm đường tăng (augmenting path) trên đồ thị cặp ghép. Điều kiện ~\sum{d_i} \equiv 0 \pmod{n}~ đảm bảo rằng luôn tồn tại một cặp ghép (tức là nghiệm ~x, y~), và thuật toán Fix này là một cách để tìm ra nó.

Sửa lại hoán vị

Sau khi xử lý xong tất cả vị trí trùng cho vị trí ~0, \ldots, n - 1~, ta hoàn thành phần tử cuối:

$$ x = S - \sum_{i = 0}^{n - 2} x_i $$

$$ y = S - \sum_{i = 0}^{n - 2} y_i $$

Kiểm tra điều kiện ràng buộc phần tử cuối phải đồng dư ~d~ cuối:

$$ \begin{align*} x + y &= (S - \sum_{i = 0}^{n - 2} x_i) + (S - \sum_{i = 0}^{n - 2} y_i) \\ &= 2S - \sum_{i = 0}^{n - 2} (x[i] + y[i]) \\ &\equiv 2S - \sum_{i = 0}^{n - 2} d[i] \pmod{n} \end{align*} $$

Vì ~\sum_{i = 0}^{n - 1}{d_i} \equiv 0 \pmod{n}~ theo giả thiết: $$ d + \sum_{i = 0}^{n - 2} d[i] \equiv 0 \pmod{n} $$

Nên ta có: $$ x + y \equiv 0 - \sum_{i = 0}^{n - 2} d_i \equiv d \pmod{n} $$

Chuyển đổi nghiệm về dạng bài toán gốc

Sau khi xây dựng được ~x~ và ~y~ thỏa mãn ~x_i + y_i \equiv d_i \pmod{n}~. Vị trí xuất phát của nhóm lính ~i~ (có giá trị ~d_i~) là: $$ P_i = (n - y_i) \pmod{n} $$

Để in ra kết quả, ta cần in ra giá trị ~d_j~​ tại vị trí ~k~, với ~k = P_j~​. Cách dễ nhất là tạo một mảng ~Result_n~, sau đó ~Result_{P_i} = i~ (hoặc ~Result_{P_i} = d_i~ tùy yêu cầu), rồi in mảng ~Result~.

Độ phức tạp: Tối đa ~O(n^3)~, tuy nhiên nếu tối ưu tốt tại việc chi phí sửa trùng, thì có thể giảm xuống ~O(n^2)~ tối đa.