USACO 2026 - Good Cyclic Shifts
Xem PDFCho một hoán vị \(p_1,p_2,\dots,p_N\) của \(1\dots N\) (\(1\le N\le 2\cdot 10^5\)), đặt
Một hoán vị được gọi là tốt nếu có thể biến nó thành hoán vị đồng nhất bằng không quá \(f(p)\) phép hoán đổi hai phần tử kề nhau.
Cho một hoán vị, hãy tìm những phép dịch vòng của nó tạo thành hoán vị tốt.
Dữ liệu vào
Dữ liệu vào gồm \(T\) (\(1\le T\le 10^5\)) bộ test độc lập. Mỗi bộ test được mô tả như sau:
Dòng đầu tiên chứa \(N\).
Dòng thứ hai chứa \(p_1,p_2,\dots,p_N\) (\(1\le p_i\le N\)), được đảm bảo là một hoán vị của \(1\dots N\).
Tổng \(N\) trên tất cả các bộ test không vượt quá \(10^6\).
Dữ liệu ra
Với mỗi bộ test, in hai dòng:
Trên dòng đầu tiên, in số lượng phép dịch vòng tốt \(k\).
Sau đó, in một dòng gồm \(k\) số nguyên \(s\) (\(0\le s<N\)) cách nhau bởi dấu cách theo thứ tự tăng dần, biểu thị rằng \(p\) là hoán vị tốt khi được dịch vòng sang phải \(s\) lần.
Ví dụ
Ví dụ 1
Input
3
5
5 4 3 2 1
4
1 2 4 3
5
1 2 3 4 5Output
0
2
0 1
5
0 1 2 3 4Note
Xét bộ test thứ hai, trong đó \(p=[1,2,4,3]\).
- \(f(p)=(|1-1|+|2-2|+|4-3|+|3-4|)/2=1\). Vì có thể biến \(p\) thành hoán vị đồng nhất trong một thao tác bằng cách hoán đổi \(p_3\) và \(p_4\), nên \(p\) là hoán vị tốt.
- Khi dịch vòng \(p\) sang phải \(1\) lần, ta nhận được \(q=[3,1,2,4]\). Khi đó \(f(q)=(|3-1|+|1-2|+|2-3|+|4-4|)/2=2\). Vì có thể biến \(q\) thành hoán vị đồng nhất bằng hai thao tác, lần lượt hoán đổi phần tử ban đầu ở \(q_1\) với phần tử ngay bên phải nó hai lần, nên \(q\) là hoán vị tốt.
Có thể thấy rằng hai phép dịch vòng còn lại không tạo thành hoán vị tốt.
Phân nhóm
- Input 2: \(N\le 10\).
- Inputs 3-5: \(T\le 10, N\le 2000\).
- Inputs 6-11: Không có ràng buộc bổ sung.
Nguồn
USACO 2026 Contest 3, Gold Division — bài gốc tiếng Anh “Good Cyclic Shifts”. Tác giả: Akshaj Arora. https://usaco.org/index.php?page=viewproblem2&cpid=1593
Kỳ thi:
- USACO 2026 - Kỳ thi 3 - Hạng Vàng (20 Tháng 2., 2026)
Bình luận