Hướng dẫn cho Trò chơi ô số (C.P.VNOI 2021 LMH R4)
Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.
Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.
Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.
Tóm tắt đề bài
Cho một bảng kích thước \(2 \times n\), mỗi số từ \(1\) đến \(n\) xuất hiện đúng 2 lần trong bảng. Một phép ĐẢO là hoán đổi hai số trong cùng một cột. Cấu hình hoàn hảo là cấu hình mà mỗi hàng là một hoán vị của các số từ \(1\) đến \(n\).
Yêu cầu:
- Tính số lượng cấu hình hoàn hảo có thể tạo ra.
- Tính số phép ĐẢO ít nhất để đạt được một cấu hình hoàn hảo.
Phân tích
- Điều kiện: \(n \leq 10^5\). Số lượng cấu hình có thể rất lớn, cần dùng số nguyên lớn (BigInt).
- Ràng buộc: Mỗi số \(i \in [1, n]\) xuất hiện đúng 2 lần. Để mỗi hàng là một hoán vị, hai vị trí của số \(i\) phải nằm ở hai hàng khác nhau.
- Mối quan hệ:
- Gọi hai vị trí của số \(i\) là \((r_1, c_1)\) và \((r_2, c_2)\).
- Nếu \(c_1 = c_2\), cột này đã chứa hai số \(i\) giống nhau. Để thỏa mãn điều kiện hoán vị, một số \(i\) phải ở hàng 1 và một số \(i\) phải ở hàng 2. Cột này cố định, không thể đảo (vì đảo cũng không thay đổi giá trị các hàng).
- Nếu \(c_1 \neq c_2\), chúng ta có sự ràng buộc giữa cột \(c_1\) và \(c_2\). Nếu ta giữ nguyên cột \(c_1\) sao cho số \(i\) ở hàng \(r_1\), thì ở cột \(c_2\), số \(i\) bắt buộc phải ở hàng \(1 - r_1\) để không bị trùng hàng.
Hướng giải quyết (Tối ưu)
1. Xây dựng đồ thị
Ta coi mỗi cột là một đỉnh của đồ thị (\(n\) đỉnh). Với mỗi số \(i \in [1, n]\), giả sử nó xuất hiện ở cột \(c_1\) và \(c_2\):
- Nếu \(c_1 = c_2\): Cột này chứa hai số giống nhau. Cột này bị "khóa", không thể xoay để thay đổi trạng thái (vì xoay hay không thì hàng 1 vẫn có số \(i\) và hàng 2 vẫn có số \(i\)).
- Nếu \(c_1 \neq c_2\): Có một cạnh nối giữa \(c_1\) và \(c_2\).
- Nếu ở trạng thái ban đầu, số \(i\) ở \(c_1\) và \(c_2\) đang nằm cùng một hàng (\(r_1 = r_2\)), thì nếu ta đảo cột \(c_1\), ta không được đảo cột \(c_2\) (và ngược lại) để \(i\) nằm ở 2 hàng khác nhau. Đây là quan hệ "khác phía" (trọng số cạnh \(w=1\)).
- Nếu ở trạng thái ban đầu, số \(i\) ở \(c_1\) và \(c_2\) đang nằm ở hai hàng khác nhau (\(r_1 \neq r_2\)), thì nếu ta đảo cột \(c_1\), ta bắt buộc phải đảo cột \(c_2\) (và ngược lại). Đây là quan hệ "cùng phía" (trọng số cạnh \(w=0\)).
2. Giải quyết trên từng thành phần liên thông
Với mỗi thành phần liên thông (TPLT):
- Sử dụng thuật toán DFS/BFS để tô màu các đỉnh bằng 2 màu (0 và 1). Màu 0 nghĩa là giữ nguyên cột, màu 1 nghĩa là đảo cột.
- Nếu xuất hiện mâu thuẫn trong quá trình tô màu (đồ thị không thỏa mãn điều kiện tô màu tương ứng với trọng số cạnh), kết quả là 0 cấu hình.
- Trong mỗi TPLT:
- Nếu TPLT có chứa một cột "bị khóa" (cột có 2 số giống nhau), thì trạng thái của toàn bộ TPLT đó bị cố định (chỉ có 1 cách chọn duy nhất để khớp với cột bị khóa).
- Nếu TPLT không chứa cột nào bị khóa, ta có 2 cách chọn trạng thái (đảo ngược toàn bộ màu 0 thành 1 và 1 thành 0).
- Số phép đảo ít nhất cho một TPLT là \(\min(\text{số đỉnh màu 0}, \text{số đỉnh màu 1})\). Tuy nhiên, nếu TPLT bị cố định bởi một cột bị khóa, ta phải chọn số phép đảo theo đúng trạng thái mà cột bị khóa yêu cầu.
3. Kết quả
- Số cấu hình hoàn hảo = \(2^k\), với \(k\) là số TPLT không bị khóa.
- Tổng số phép đảo = Tổng số phép đảo nhỏ nhất của từng TPLT.
Độ phức tạp
- Thời gian: \(O(n)\) để xây dựng đồ thị và duyệt BFS/DFS. Việc nhân BigInt \(2^k\) mất \(O(n^2/ \text{word\_size})\) nhưng thực tế rất nhanh.
- Bộ nhớ: \(O(n)\) để lưu đồ thị và các mảng đánh dấu.
Code tham khảo
C++
C++
#include <bits/stdc++.h>
using namespace std;
struct BigInt {
vector<int> digits;
BigInt(long long v = 0) {
if (v == 0) digits.push_back(0);
while (v > 0) {
digits.push_back(v % 10);
v /= 10;
}
}
void multiplyBy2() {
int carry = 0;
for (int i = 0; i < digits.size(); i++) {
int prod = digits[i] * 2 + carry;
digits[i] = prod % 10;
carry = prod / 10;
}
if (carry) digits.push_back(carry);
}
void print() {
if (digits.empty()) { cout << 0; return; }
for (int i = digits.size() - 1; i >= 0; i--) cout << digits[i];
}
};
const int MAXN = 1e5 + 5;
vector<pair<int, int>> adj[MAXN];
int side_color[MAXN], n;
vector<int> pos[MAXN];
bool self_loop[MAXN];
int main() {
ios::sync_with_stdio(false); cin.tie(0);
cin >> n;
vector<vector<int>> a(2, vector<int>(n));
for (int i = 0; i < 2; i++) {
for (int j = 0; j < n; j++) {
cin >> a[i][j];
pos[a[i][j]].push_back(j);
}
}
for (int i = 1; i <= n; i++) {
int c1 = pos[i][0], c2 = pos[i][1];
if (c1 != c2) {
int r1 = (a[0][c1] == i ? 0 : 1);
int r2 = (a[0][c2] == i ? 0 : 1);
int w = (r1 == r2 ? 1 : 0);
adj[c1].push_back({c2, w});
adj[c2].push_back({c1, w});
} else self_loop[c1] = true;
}
memset(side_color, -1, sizeof(side_color));
int free_components = 0;
long long min_swaps = 0;
for (int i = 0; i < n; i++) {
if (side_color[i] == -1) {
vector<int> q = {i};
side_color[i] = 0;
int head = 0, c0 = 0, c1 = 0;
bool has_fixed = false;
int fixed_val = -1;
while(head < q.size()){
int u = q[head++];
if (side_color[u] == 0) c0++; else c1++;
if (self_loop[u]) {
has_fixed = true;
fixed_val = side_color[u];
}
for (auto& edge : adj[u]) {
int v = edge.first, w = edge.second;
if (side_color[v] == -1) {
side_color[v] = side_color[u] ^ w;
q.push_back(v);
} else if (side_color[v] != (side_color[u] ^ w)) {
cout << "0\n0\n"; return 0;
}
}
}
if (has_fixed) min_swaps += (fixed_val == 0 ? c1 : c0);
else {
free_components++;
min_swaps += min(c0, c1);
}
}
}
BigInt ans(1);
for (int i = 0; i < free_components; i++) ans.multiplyBy2();
ans.print();
cout << "\n" << min_swaps << endl;
return 0;
}
Python
Python
import sys
def solve():
n = int(sys.stdin.readline())
a = [list(map(int, sys.stdin.readline().split())) for _ in range(2)]
pos = [[] for _ in range(n + 1)]
for r in range(2):
for c in range(n):
pos[a[r][c]].append(c)
adj = [[] for _ in range(n)]
self_loop = [False] * n
for i in range(1, n + 1):
c1, c2 = pos[i]
if c1 != c2:
r1 = 0 if a[0][c1] == i else 1
r2 = 0 if a[0][c2] == i else 1
w = 1 if r1 == r2 else 0
adj[c1].append((c2, w))
adj[c2].append((c1, w))
else:
self_loop[c1] = True
side_color = [-1] * n
free_components = 0
min_swaps = 0
for i in range(n):
if side_color[i] == -1:
stack = [i]
side_color[i] = 0
comp_nodes = []
has_fixed = False
fixed_val = -1
idx = 0
while idx < len(stack):
u = stack[idx]
idx += 1
comp_nodes.append(u)
if self_loop[u]:
has_fixed = True
fixed_val = side_color[u]
for v, w in adj[u]:
if side_color[v] == -1:
side_color[v] = side_color[u] ^ w
stack.append(v)
elif side_color[v] != (side_color[u] ^ w):
print(0)
print(0)
return
c0 = sum(1 for node in comp_nodes if side_color[node] == 0)
c1 = len(comp_nodes) - c0
if has_fixed:
min_swaps += c1 if fixed_val == 0 else c0
else:
free_components += 1
min_swaps += min(c0, c1)
print(2 ** free_components)
print(min_swaps)
solve()
Bình luận