Editorial for Dãy hoán vị

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: Yunan

Subtask 1: Xây dựng dãy số $Q$ ~Q~ với $Q_{P_i}=i$ ~Q_{P_i}=i~ với mọi $1 \le i \le N$ ~1 \le i \le N~. Khi đó, dãy $Q$ ~Q~ cũng là một dãy hoán vị và ta có thể hoán đổi giá trị của $Q_i$ ~Q_i~ và $Q_j$ ~Q_j~ $(i < j)$ ~(i < j)~ nếu $j-i = 1$ ~j-i = 1~ và $|Q_i-Q_j| \ge K$ ~|Q_i-Q_j| \ge K~, hay nói cách khác, ta có thể hoán đổi hai phần tử liền kề $Q_i$ ~Q_i~ và $Q_{i+1}$ ~Q_{i+1}~ nếu $|Q_i-Q_{i+1}| \ge K$ ~|Q_i-Q_{i+1}| \ge K~. Ta có nhận xét sau:

Nhận xét 1: Cho dãy hoán vị $R$ ~R~ độ dài $N$ ~N~. Với mọi cặp số $(x,y)$ ~(x,y)~ thỏa mãn $|x-y| < K$ ~|x-y| < K~, gọi $a$ ~a~ và $b$ ~b~ là hai chỉ số thỏa mãn $Q_a=x$ ~Q_a=x~ và $Q_b=y$ ~Q_b=y~, gọi $c$ ~c~ và $d$ ~d~ là hai chỉ số thỏa mãn $R_c=x$ ~R_c=x~ và $R_d=y$ ~R_d=y~. Khi đó, điều kiện cần và đủ để dãy $Q$ ~Q~ có thể biến đổi thành dãy $R$ ~R~ là $($ ~(~ $a<b$ ~a<b~ và $c<d$ ~c<d~ $)$ ~)~ hoặc $($ ~(~ $a>b$ ~a>b~ và $c>d$ ~c>d~ $)$ ~)~.

Từ đó, ta có thể kiểm tra tất cả các hoán vị $R$ ~R~ độ dài $N$ ~N~ $($ ~(~tổng cộng $N!$ ~N!~ dãy hoán vị $)$ ~)~, với mỗi hoán vị $R$ ~R~, kiểm tra xem dãy $Q$ ~Q~ có thể biến đổi thành dãy $R$ ~R~ hay không từ nhận xét trên $($ ~(~việc kiểm tra có thể thực hiện trong $O(N)$ ~O(N)~ $)$ ~)~, nếu có thể biến đổi, xây dựng dãy $Z$ ~Z~ với $Z_{R_i}=i$ ~Z_{R_i}=i~ $(1 \le i \le N)$ ~(1 \le i \le N)~. Đáp án là dãy số có thứ tự từ điển nhỏ nhất trong số các dãy $Z$ ~Z~ tìm được.

Độ phức tạp $O(N.N!)$ ~O(N.N!)~

Subtask 2: Từ việc xây dựng dãy $Q$ ~Q~ với $Q_{P_i}=i$ ~Q_{P_i}=i~ với mọi $1 \le i \le N$ ~1 \le i \le N~, ta có nhận xét mở rộng từ nhận xét $1$ ~1~ như sau:

Nhận xét 2: Cho dãy hoán vị $A$ ~A~ độ dài $N$ ~N~. Với mọi cặp số $(x,y)$ ~(x,y)~ thỏa mãn $|x-y| < K$ ~|x-y| < K~, khi đó, điều kiện cần và đủ để dãy $P$ ~P~ có thể biến đổi thành dãy $A$ ~A~ là $($ ~(~ $P_x<P_y$ ~P_x<P_y~ và $A_x<A_y$ ~A_x<A_y~ $)$ ~)~ hoặc $($ ~(~ $P_x>P_y$ ~P_x>P_y~ và $A_x>A_y$ ~A_x>A_y~ $)$ ~)~.

Từ nhận xét trên, ta có thể xem bài toán ban đầu trở thành một bài toán đồ thị như sau:

Bài toán: Cho dãy hoán vị $P$ ~P~ độ dài $N$ ~N~. Xây dựng một đồ thị gồm $N$ ~N~ đỉnh bằng cách: thêm cạnh nối một chiều từ đỉnh $i$ ~i~ đến đỉnh $j$ ~j~ nếu $|i-j| < K$ ~|i-j| < K~ và $P_i<P_j$ ~P_i<P_j~. Tìm một mảng $label$ ~label~ có thứ tự từ điển nhỏ nhất thỏa mãn: với mọi cạnh từ $i$ ~i~ đến $j$ ~j~ thì $label_i<label_j$ ~label_i<label_j~. $($ ~(~Bài toán sắp xếp Topo $)$ ~)~

Từ việc phát biểu bài toán như trên, đỉnh có bậc vào bằng $0$ ~0~ là đỉnh $i$ ~i~ thỏa mãn: $P_i$ ~P_i~ đạt giá trị nhỏ nhất trong khoảng $[i-k+1,i+k-1]$ ~[i-k+1,i+k-1]~, từ đó có thể tìm kiếm đỉnh $i$ ~i~ trong $O(N)$ ~O(N)~. Việc xây dựng mảng $label$ ~label~ có thể thực hiện như sau:

Bước 1: Gọi $v$ ~v~ là giá trị để gán cho mảng $label$ ~label~, ban đầu $v=1$ ~v=1~.
Bước 2: Tìm đỉnh $i$ ~i~ nhỏ nhất là đỉnh có bậc vào bằng $0$ ~0~ và gán $label_i=v$ ~label_i=v~.
Bước 3: Xóa đỉnh $i$ ~i~ và các cạnh nối từ $i$ ~i~ khỏi đồ thị.
Bước 4: Tăng giá trị $v=v+1$ ~v=v+1~ và quay lại bước 2.

Độ phức tạp: $O(N^2)$ ~O(N^2)~

Subtask 3: Việc tìm kiếm đỉnh có bậc vào bằng $0$ ~0~ và xóa đỉnh khỏi đồ thị có thể thực hiện với cấu trúc Segment Tree với các thao tác cập nhật điểm và truy vấn đoạn. Bài toán có thể giải quyết với độ phức tạp $O(N.log(N))$ ~O(N.log(N))~.

Editorial for Dãy hoán vị

Comments