Hướng dẫn giải của CUỘC THI LẬP TRÌNH
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Lời giải này đang bị ẩn cho đến khi bạn chọn mở ra.
Chúng tôi khuyên bạn nên tự thử giải bài trước. Việc mở lời giải có thể làm lộ mất ý tưởng chính trước khi bạn có cơ hội tự giải.
Bạn phải đăng nhập để mở lời giải này.
Đăng nhập
Tác giả: Hiếu Nguyễn
, , ,
Hiểu bài toán
Bài toán yêu cầu loại bỏ ít nhất số lượng thí sinh để có thể chia剩下的 thí sinh vào 2 phòng thi sao cho:
- Các thí sinh cùng mệnh (R, G, B) phải ngồi chung phòng.
- Hai thí sinh xung khắc (có trong danh sách M cặp xung khắc) không được ngồi chung phòng.
Phân tích:
- Vì chỉ có 2 phòng, và các thí sinh cùng mệnh phải chung phòng, cách duy nhất để chia là gom tất cả thí sinh của 2 mệnh bất kỳ vào phòng 1, và mệnh còn lại vào phòng 2.
- Cần kiểm tra 3 trường hợp: (R, G) vs B; (R, B) vs G; (G, B) vs R.
- Xung khắc chỉ xảy ra giữa các cặp khác mệnh. Do đó, xung khắc chỉ có thể xảy ra giữa một bên của 'phòng 1' và một bên của 'phòng 2'.
- Để thỏa mãn điều kiện, ta cần xóa các cạnh xung khắc sao cho đồ thị 2 phía giữa 2 bên của phòng được chia hoàn toàn (tức là không còn cạnh chéo nào).
- Bài toán quy về tìm 'Bộ khớp lớn nhất' (Maximum Matching) giữa 2 bên của mỗi cách chia. Số lượng xung khắc cần loại bỏ chính là kích thước bộ khớp lớn nhất. Tìm cách chia có bộ khớp nhỏ nhất.
Các cách tiếp cận
Cách Quy hoạch động / Đồ thị
#include <bits/stdc++.h>
using namespace std;
int n, m;
string s;
vector<int> adj[55];
int mt[55];
bool visited[55];
// Tìm bộ khớp lớn nhất giữa 2 phía uSide và vSide
// maxMatch(uSide, vSide) là số cạnh xung khắc cần loại bỏ
int maxMatch(const vector<int>& uSide, const vector<int>& vSide) {
fill(mt, mt + 55, 0);
int matchSize = 0;
for (int u : uSide) {
fill(visited, visited + 55, false);
function<bool(int)> dfs = [&](int cur) {
for (int v : adj[cur]) {
// Chỉ xét v thuộc vSide
if (find(vSide.begin(), vSide.end(), v) == vSide.end()) continue;
if (visited[v]) continue;
visited[v] = true;
if (mt[v] == 0 || dfs(mt[v])) {
mt[v] = cur;
return true;
}
}
return false;
};
if (dfs(u)) matchSize++;
}
return matchSize;
}
int main() {
cin >> n >> s >> m;
for (int i = 0; i < m; ++i) {
int u, v; cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
// Phân loại thí sinh
vector<int> R, G, B;
for (int i = 1; i <= n; ++i) {
if (s[i-1] == 'R') R.push_back(i);
if (s[i-1] == 'G') G.push_back(i);
if (s[i-1] == 'B') B.push_back(i);
}
int ans = n;
// Trường hợp 1: (R, G) vs B
// Tạo side 1 (R+G) và side 2 (B)
// Tính Max Matching, số xóa = matching
auto getMatch = [&](const vector<int>& A, const vector<int>& B) {
int match = maxMatch(A, B);
return match;
};
// Tối thiểu hóa số lượng loại bỏ
ans = min(ans, getMatch(R, B) + getMatch(G, B)); // Thực chất là maxMatch(R+G, B)
// Cần sửa lại logic getMatch để nhận 2 vector hợp lại
// Dưới đây là code minh họa logic đúng:
// Case 1: (R+G) vs B
vector<int> rg = R;
rg.insert(rg.end(), G.begin(), G.end());
ans = min(ans, maxMatch(rg, B));
// Case 2: (R+B) vs G
vector<int> rb = R;
rb.insert(rb.end(), B.begin(), B.end());
ans = min(ans, maxMatch(rb, G));
// Case 3: (G+B) vs R
vector<int> gb = G;
gb.insert(gb.end(), B.begin(), B.end());
ans = min(ans, maxMatch(gb, R));
cout << ans << endl;
return 0;
}
- Time Complexity: O(N * M) ~ O(50 * 1000) = O(5*10^5)
- Space Complexity: O(N + M)
Hàm maxMatch sử dụng thuật toán Kuhn (DFS tìm augmenting path) để tìm bộ khớp lớn nhất giữa 2 tập hợp. Ta xét 3 cách chia:
- Nhóm (R, G) vào phòng 1, B vào phòng 2. Cạnh xung khắc giữa R/B hoặc G/B cần được xóa. Số lượng xóa chính là kích thước bộ khớp lớn nhất giữa tập (R,G) và tập B.
- Nhóm (R, B) vào phòng 1, G vào phòng 2.
- Nhóm (G, B) vào phòng 1, R vào phòng 2. Kết quả là giá trị nhỏ nhất trong 3 trường hợp trên.
Cách Brute Force (Tối ưu hóa)
#include <bits/stdc++.h>
using namespace std;
int n, m;
string s;
int a[55][55];
int mt[55];
bool visited[55];
int maxMatch(const vector<int>& U, const vector<int>& V) {
fill(mt, mt + 55, 0);
int match = 0;
for (int u : U) {
fill(visited, visited + 55, false);
function<bool(int)> dfs = [&](int cur) {
for (int v : V) {
if (a[cur][v] && !visited[v]) {
visited[v] = true;
if (mt[v] == 0 || dfs(mt[v])) {
mt[v] = cur;
return true;
}
}
}
return false;
};
if (dfs(u)) match++;
}
return match;
}
int main() {
cin >> n >> s >> m;
for (int i = 0; i < m; ++i) {
int u, v; cin >> u >> v;
a[u][v] = a[v][u] = 1;
}
vector<int> R, G, B;
for (int i = 1; i <= n; ++i) {
if (s[i-1] == 'R') R.push_back(i);
else if (s[i-1] == 'G') G.push_back(i);
else B.push_back(i);
}
int ans = n;
// Case 1: (R, G) vs B
vector<int> rg;
rg.insert(rg.end(), R.begin(), R.end());
rg.insert(rg.end(), G.begin(), G.end());
ans = min(ans, maxMatch(rg, B));
// Case 2: (R, B) vs G
vector<int> rb;
rb.insert(rb.end(), R.begin(), R.end());
rb.insert(rb.end(), B.begin(), B.end());
ans = min(ans, maxMatch(rb, G));
// Case 3: (G, B) vs R
vector<int> gb;
gb.insert(gb.end(), G.begin(), G.end());
gb.insert(gb.end(), B.begin(), B.end());
ans = min(ans, maxMatch(gb, R));
cout << ans << endl;
return 0;
}
- Time Complexity: O(N^3) - O(N^4)
- Space Complexity: O(N^2)
Đây là cách tiếp cận trực quan nhất sử dụng ma trận kề để lưu xung khắc. Logic xử lý tương tự như cách 1 nhưng cấu trúc code có thể khác đôi chút. Tuy nhiên độ phức tạp vẫn nằm trong mức chấp nhận được do N nhỏ.
Phân tích độ phức tạp
| Cách tiếp cận | Time | Space | Tên |
|---|---|---|---|
| 1 | O(N * M) ~ O(50 * 1000) = O(5*10^5) | O(N + M) | Quy hoạch động / Đồ thị |
| 2 | O(N^3) - O(N^4) | O(N^2) | Brute Force (Tối ưu hóa) |
Bài học kinh nghiệm
- Vì chỉ có 2 phòng, cách chia duy nhất hợp lệ là gom 2 mệnh vào 1 phòng, mệnh còn lại vào phòng kia.
- Xung khắc chỉ giữa các cặp khác mệnh, nên bài toán quy về bài toán Matching trên đồ thị 2 phía (Bipartite Graph).
Lỗi thường gặp
- Lầm tưởng rằng có thể chia tự do các thí sinh vào 2 phòng mà không theo quy luật 'cùng mệnh'.
- Xử lý sai trường hợp 2 bên trong matching (ví dụ R vs G không có cạnh, nhưng R+B và G+B có thể có cạnh).
Bình luận