Coding Challenge
Coding Challenge là một chuyên mục thuộc Tạp chí VNOI, được xây dựng với mục tiêu mang đến cho cộng đồng lập trình thi đấu Việt Nam một sân chơi hữu ích và thiết thực nhằm giúp các độc giả củng cố kiến thức thuật toán và thúc đẩy tinh thần học hỏi, chia sẻ trong cộng đồng.
Hoạt động được tổ chức định kỳ hai lần mỗi tháng trên Fanpage VNOI, Group Facebook “Diễn đàn Tin học Việt Nam” và nền tảng chấm bài trực tuyến VNOJ. Toàn bộ các bài toán trong Coding Challenge được biên soạn bởi đội ngũ Tình nguyện viên thuộc Team Contest của VNOI. Chất lượng các bài toán Coding Challenge được đảm bảo về tính chuyên môn, có sự đa dạng về chủ đề và độ khó cũng như đáp ứng yêu cầu về tính chặt chẽ và chính xác.
Độc giả của Tạp chí VNOI có thể tham gia giải các bài toán thuộc Coding Challenge và gửi lời giải về cho Tạp chí. Những bài giải chất lượng sẽ được chọn lọc để đăng tải trong các số Tạp chí tiếp theo. Bên cạnh việc được ghi nhận và giới thiệu rộng rãi đến cộng đồng, các tác giả có lời giải được đăng tải sẽ nhận những phần quà tri ân từ VNOI nhằm khuyến khích tinh thần ham học hỏi và chia sẻ kiến thức đến cộng đồng
Các lời giải được chọn lọc để đăng công khai sẽ được đánh giá dựa trên tiêu chí về sự rõ ràng, mạch lạc, sáng tạo; có sự đầu tư trong diễn giải tư duy, cấu trúc và tính dễ hiểu. Đối với các bài toán có nhiều subtask, tác giả cần trình bày đầy đủ ý tưởng và hướng giải quyết cho tất cả các phần.
Phần thưởng dành cho mỗi lời giải được đăng tải trên Tạp chí là một bộ quà tặng gồm sổ tay, bút, sticker và móc khóa. Đặc biệt, với các tác giả có từ 03 bài giải trở lên được đăng trong chuyên mục, Ban biên tập Tạp chí sẽ gửi tặng một chiếc áo VNOI như lời tri ân cho những đóng góp tích cực đối với Coding Challenge.
Sau 03 số đầu tiên, Coding Challenge đã ghi nhận những kết quả rất ấn tượng. Đã có tổng cộng 2316 lượt nộp bài trên hệ thống và 26 lời giải chất lượng được gửi về cho Tạp chí. Đây là nguồn động lực to lớn để đội ngũ Tạp chí VNOI tiếp tục phát triển và mở rộng sân chơi học thuật này trong thời gian tới.
Coding Challenge #1
Coding Challenge #1 có tên là Đường đi. Đây là một bài toán về chủ đề đường đi ngắn nhất trên đồ thị, với điểm khác biệt là cách xây dựng tập cạnh thông qua các truy vấn nối và tô màu đỉnh.
Bài toán này chứng kiến 182 độc giả tham gia giải và 30 bài giải đạt điểm tuyệt đối. Đội ngũ Tạp chí VNOI xin phép chọn lọc ra 2 lời giải được các độc giả gửi về cho Tạp chí.
Đề Bài
Đề bài gốc có thể được đọc trên hệ thống VNOJ Coding Challenge #1 - Đường đi
Cho một đồ thị vô hướng gồm ~N~ đỉnh, ban đầu đồ thị này không có cạnh nào. Mỗi đỉnh thứ ~i~ được gán một màu ~c_i~. Bạn cần thực hiện lần lượt ~Q~ thao tác, mỗi thao tác thuộc một trong hai loại sau:
Loại 1:
1 x y- nối toàn bộ các đỉnh có màu ~x~ với toàn bộ các đỉnh có màu ~y~.Loại 2:
2 u v- đổi màu của toàn bộ các đỉnh ~i~ có ~c_i = u~ thành ~c_i = v~.
Sau khi thực hiện xong tất cả các thao tác, hãy in ra độ dài đường đi ngắn nhất từ đỉnh ~1~ tới toàn bộ các đỉnh trong đồ thị.
Input
Dòng đầu tiên chứa hai số nguyên ~N, Q~ ~(1 \le N, Q \le 3 \times 10^5)~.
Dòng thứ hai chứa ~N~ số nguyên ~c_1, c_2, ..., c_N~ - màu ban đầu của từng đỉnh ~(1 \le c_i \le N)~.
~Q~ dòng tiếp theo, mỗi dòng chứa 3 số nguyên ~t, x, y~ mô tả các thao tác ~(1 \le t \le 2, 1 \le x, y \le N)~.
Output
- In ra ~N~ số nguyên, số thứ ~i~ là độ dài đường đi ngắn nhất từ đỉnh ~1~ tới đỉnh ~i~. Nếu không tồn tại đường đi, in ra ~-1~.
Scoring
| Subtask | Điểm | Giới hạn |
|---|---|---|
| ~1~ | 20% | ~N, Q \le 100~ |
| ~2~ | 30% | Chỉ có thao tác loại ~1~ |
| ~3~ | 20% | Tất cả thao tác loại ~2~ xuất hiện trước thao tác loại ~1~ |
| ~4~ | 30% | Không có giới hạn bổ sung |
Sample Input 1
5 4
1 2 3 2 1
1 1 2
2 3 2
1 2 3
1 1 3
Sample Output 1
0 1 -1 1 2
Notes
• Ban đầu: chưa có cạnh nào;
• Thao tác 1 1 2: Nối toàn bộ đỉnh màu ~1~ với toàn bộ đỉnh màu ~2~ ~\Rightarrow~ Tạo cạnh giữa các đỉnh ~{1, 5}~ với ~{2, 4}~;
• Thao tác 2 3 2: Đổi toàn bộ đỉnh màu ~3~ thành màu ~2~ ~\Rightarrow~ Đỉnh ~3~ có màu ~2~;
• Thao tác 1 2 3: Không có thay đổi gì vì không còn đỉnh nào có màu ~3~;
• Thao tác 1 1 3: Không có thay đổi gì vì không còn đỉnh nào có màu ~3~.
Sau cùng, đường đi ngắn nhất từ đỉnh ~1~ đến các đỉnh khác là:
• Đỉnh ~1~ ~\rightarrow~ chính nó: ~0~
• Đỉnh ~2~: ~1~ ~\rightarrow~ ~2~ (độ dài ~1~)
• Đỉnh ~3~: Không tồn tại đường đi (~-1~)
• Đỉnh ~4~: ~1~ ~\rightarrow~ ~4~ (độ dài ~1~)
• Đỉnh ~5~: ~1 \rightarrow 2 \rightarrow 5~ (độ dài ~2~)
Minh họa test ví dụ
Lời giải #1
Subtask 1
- Giới hạn bổ sung: ~N, Q \le 100~
Ý tưởng:
Vì giới hạn của subtask này là nhỏ, chúng ta có thể giải quyết subtask này bằng cách thực hiện chính xác như những gì đề yêu cầu.
Với thao tác loại ~1~ với hai màu ~x~ và ~y~, chúng ta duyệt tuần tự để tìm tập các đỉnh có màu ~x~ và tập các đỉnh có màu ~y~ rồi với mỗi cặp đỉnh từ hai tập, ta thêm cạnh nối hai chiều giữa hai đỉnh.
Với thao tác loại ~2~ với hai màu ~u~ và ~v~, chúng ta duyệt tuần tự và gán màu ~v~ cho các đỉnh có màu ~u~
~ c[i] \leftarrow v \quad \forall \, (c[i] = u) ~
Sau khi thực hiện xong tất cả các thao tác, để tìm ra độ dài đường đi ngắn nhất từ đỉnh ~1~ tới toàn bộ các đỉnh trong đồ thị, ta có thể sử dụng thuật toán BFS từ đỉnh ~1~ trên đồ thị không trọng số dựng được.
Độ phức tạp:
Cách giải như trên có độ phức tạp về thời gian là ~O(Q \cdot N^2)~ trong trường hợp xấu nhất
Quá trình đọc dữ liệu có độ phức tạp về thời gian là ~O(N + Q)~
Với mỗi thao tác loại ~1~, vì mỗi màu có ~O(N)~ đỉnh có màu đó, ta sẽ phải xem xét qua ~O(N^2)~ cặp đỉnh cho hai màu ~x~ và ~y~.
Với mỗi thao tác loại ~2~, ta phải quyệt qua ~O(N)~ đỉnh.
Bước chạy thuật toán BFS sẽ có độ phức tạp về thời gian là ~O(N + |E|)~ với ~|E|~ là số cạnh của đồ thị sau khi ta đã dựng xong. Vì dữ liệu có thể chứa ~O(Q)~ thao tác loại ~1~, ta có ~|E| = O(Q \cdot N^2)~. Nói cách khác, bước xử lý tìm đường đi ngắn nhất có độ phức tạp ~O(Q \cdot N^2)~
Tương tự, độ phức tạp bộ nhớ của cách giải trên là ~O(Q \cdot N^2)~ trong trường hợp tệ nhất bởi ta phải lưu ~O(Q \cdot N^2)~ cạnh đồng thời cùng một lúc
Code minh họa:
#include <bits/stdc++.h>
using namespace std;
template<class A, class B>
bool maximize(A &a, const B& b) {
if (a < b) {
a = b;
return true;
}
return false;
}
template<class A, class B>
bool minimize(A &a, const B& b) {
if (a > b) {
a = b;
return true;
}
return false;
}
constexpr int MAX_N = 300'005, INF = 0X3F3F3F3F;
int N, Q, c[MAX_N];
vector<int> graph[MAX_N];
signed minimumDistance[MAX_N];
void addEdges(const int x, const int y) {
for (int i = 1; i <= N; ++i) {
if (c[i] != x)
continue;
for (int j = 1; j <= N; ++j) {
if (c[j] != y)
continue;
graph[i].push_back(j);
graph[j].push_back(i);
}
}
}
void changeColors(const int u, const int v) {
for (int i = 1; i <= N; ++i)
if (c[i] == u)
c[i] = v;
}
void runBFS() {
queue<int> q;
minimumDistance[1] = 0;
q.push(1);
for (; !q.empty(); q.pop()) {
const int &x = q.front();
for (const int &y : graph[x])
if (minimize(minimumDistance[y], minimumDistance[x] + 1))
q.push(y);
}
}
int main() {
#ifdef LOCAL
freopen("input.INP", "r", stdin);
#endif // LOCAL
cin.tie(0) -> sync_with_stdio(0);
cout.tie(0);
cin >> N >> Q;
for (int i = 1; i <= N; ++i) {
minimumDistance[i] = INF;
cin >> c[i];
}
for (int q = 1, t = 0, x = 0, y = 0; q <= Q; ++q) {
cin >> t >> x >> y;
if (t == 1)
addEdges(x, y);
else
changeColors(x, y);
}
runBFS();
for (int i = 1; i <= N; ++i)
cout << ((minimumDistance[i] < INF) ? minimumDistance[i] : (-1)) << ' ';
cout << '\n';
return 0;
}
Subtask 2
- Giới hạn bổ sung: Chỉ có thao tác loại ~1~
Ý tưởng:
Với giới hạn của subtask này, ta có nhận xét rằng với hai đỉnh ~x~ và ~y~ đều khác ~1~ và có cùng màu thì đường đi ngắn nhất từ đỉnh ~1~ đến đỉnh ~x~ và ~y~ nên bằng nhau. Nếu ta đặt ~d[i]~ là độ dài đường đi ngắn nhất từ đỉnh ~1~ đến đỉnh ~i~, ta có: ~\forall x, y \, (c[x] = c[y]) \land (x \neq 1) \land (y \neq 1) \rightarrow d[x] = d[y]~
Chứng minh chi tiết:
- Giả sử tồn tại hai đỉnh ~x~ và ~y~ đều khác ~1~ và có cùng màu nhưng đường đi ngắn nhất từ đỉnh ~1~ đến hai đỉnh ~x~ và ~y~ lại khác nhau. Không làm mất tính tổng quát, ta xét trường hợp ~d[x] < d[y]~
- Xét một đường đi ngắn nhất bất kì từ ~1~ đến ~x~, gọi ~z~ là đỉnh ngay trước ~x~ trên đường đi đó (~1 \rightarrow ... \rightarrow z \rightarrow x~). Vì đồ thị chứa cạnh từ ~z~ tới ~x~, danh sách thao tác phải bao gồm ít nhất một thác như sau:
1 c[z] c[x]. Vì đỉnh ~x~ và ~y~ có cùng màu (~c[x] = c[y]~), đồ thị cũng chứa cạnh từ ~z~ tới ~y~. Điều này đồng nghĩa với việc tồn tại đường đi từ ~1~ tới ~y~ với độ dài ~d[z] + 1 = d[x]~ mà ~d[x] < d[y]~ (theo giả định trước đó) ~\Rightarrow~ Tồn tại đường đi từ ~1~ tới ~y~ với độ dài ngắn hơn ~d[y]~; mâu thuẫn với định nghĩa của ~d[y]~
Từ nhận xét này, ta nhận thấy rằng trừ đỉnh ~1~, các đỉnh chỉ có thể được phân biệt với nhau bằng màu (nói cách khác, không có sự phân biệt giữa các đỉnh cùng màu). Dựa vào đây, ta có thể dùng màu để đại diện cho các đỉnh đó. Cụ thể hơn, thay vì xây dựng đồ thị như đề bài (với số cạnh trong trường hợp tệ nhất đạt xấp xỉ ~Q \cdot N^2~), ta có thể xây dựng một đồ thị khác ~G' = (V', E')~ có các đỉnh là các màu và có cạnh giữa ~x'~ và ~y'~ nếu tồn tại thao tác
1 x' y'. ~\Rightarrow~ Số cạnh của đồ thị ~G'~ sẽ không vượt quá ~Q~ (~|E'| = O(Q)~), cho phép chúng ta tìm đường đi ngắn nhất giữa đỉnh đại diện cho màu của đỉnh ~1~ và các đỉnh còn lại trong ~V'~ với độ phức tạp cho phép. Nếu đặt ~T = \{(t_i, x_i, y_i) \, | \, 1 \leq i \leq Q\}~ là tập hợp các thao tác sử dụng, ta có:- ~V' = \{c[u] \, | \, 1 \leq u \leq N \}~
- ~E' = \{(x, y) \, | \, ((1, x, y) \in T) \land (x, y \in V') \}~
Với các đỉnh ~x~ có màu khác với màu của đỉnh ~1~ (~c[x] \neq c[1]~), độ dài đường đi ngắn nhất từ ~1~ tới ~x~ sẽ bằng với độ dài đường đi ngắn nhất từ ~c[1]~ tới ~c[x]~ trong ~G'~.
Với các đỉnh ~x~ không phải là đỉnh ~1~ nhưng có cùng màu với đỉnh ~1~ (~c[x] = c[1]~), ta sẽ có ba trường hợp sau:
- Tồn tại thao tác
1 c[1] c[1](nối giữa các đỉnh có màu ~c[1]~ với nhau) ~\Rightarrow~ Độ dài đường đi ngắn nhất từ ~1~ tới ~x~ bằng ~1~. - Không tồn tại thao tác như trên nhưng ~c[1]~ có cạnh nối tới màu khác (trong ~G'~) ~\Rightarrow~ Độ dài đường đi ngắn nhất từ ~1~ tới ~x~ bằng ~2~ (ta tốn một bước để từ đỉnh ~1~ đi đến một đỉnh bất kì có màu kề với ~c[1]~ rồi đi đến ~x~).
- Các điều kiện trên đều không thỏa ~\Rightarrow~ Không tồn tại đường đi giữa ~1~ và ~x~
- Tồn tại thao tác
Độ phức tạp:
Cách giải như trên có độ phức tạp về thời gian là ~O(N + Q)~ trong trường hợp xấu nhất bởi việc dựng đồ thị và tìm đường đi ngắn nhất (với thuật toán BFS) có độ phức tạp ~O(N + Q)~.
Tương tự, độ phức tạp bộ nhớ của cách giải trên là ~O(N + Q)~ trong trường hợp tệ nhất.
Code minh họa:
#include <bits/stdc++.h>
using namespace std;
template<class A, class B>
bool maximize(A &a, const B& b) {
if (a < b) {
a = b;
return true;
}
return false;
}
template<class A, class B>
bool minimize(A &a, const B& b) {
if (a > b) {
a = b;
return true;
}
return false;
}
constexpr int MAX_N = 300'005, INF = 0X3F3F3F3F;
int N, Q, c[MAX_N];
bool existed[MAX_N];
vector<int> graph[MAX_N];
signed minimumDistance[MAX_N];
void runBFS() {
queue<int> q;
minimumDistance[c[1]] = 0;
q.push(c[1]);
for (; !q.empty(); q.pop()) {
const int &x = q.front();
for (const int &y : graph[x])
if (minimize(minimumDistance[y], minimumDistance[x] + 1))
q.push(y);
}
}
int main() {
bool sourceFlag = false;
#ifdef LOCAL
freopen("input.INP", "r", stdin);
#endif // LOCAL
cin.tie(0) -> sync_with_stdio(0);
cout.tie(0);
cin >> N >> Q;
for (int i = 1; i <= N; ++i) {
minimumDistance[i] = INF;
cin >> c[i];
existed[c[i]] = true;
}
for (int q = 1, t = 0, x = 0, y = 0; q <= Q; ++q) {
cin >> t >> x >> y;
if (!existed[x] || !existed[y])
continue;
graph[x].push_back(y);
graph[y].push_back(x);
if (x == c[1] && y == c[1])
sourceFlag = true;
}
runBFS();
cout << 0 << ' ';
for (int i = 2; i <= N; ++i) {
if (c[i] != c[1]) {
cout << ((minimumDistance[c[i]] < INF) ? minimumDistance[c[i]] : (-1)) << ' ';
continue;
}
cout << (sourceFlag ? 1 : ((!graph[c[1]].empty()) ? 2 : (-1))) << ' ';
}
cout << '\n';
return 0;
}
Subtask 3
- Giới hạn bổ sung: Tất cả thao tác loại ~2~ xuất hiện trước thao tác loại ~1~
Ý tưởng:
Ta nhận thấy rằng, nếu ta có thể cập nhật được màu các đỉnh sau khi xử lý xong các thao tác loại ~2~ (với độ phức tạp hợp lý), bài toán sẽ được đưa về subtask ~2~.
Ta có nhận xét rằng mỗi thao tác loại ~2~ có thể được xem như gồm hai bước:
- Gộp hai tập đỉnh lại thành một tập đỉnh.
- Đánh số (tên màu) lại tập đỉnh mới.
Ví dụ như trong sample test được đưa ra, thao tác
2 3 2(thao tác thứ ~2~ trong danh sách các thao tác) có thể được xem như việc gộp tập đỉnh ~\{2, 4\}~ (có màu ~2~) và ~\{3\}~ (có màu ~3~) thành tập đỉnh mới ~\{2, 3, 4\}~ và đánh màu ~2~ cho tập đỉnh này.
Dựa trên nhật xét này và giới hạn của subtask, chúng ta có thể sử dụng cấu trúc dữ liệu Disjoint Set Union để thực hiện các thao tác loại ~2~ và cập nhật màu của đỉnh.
Lưu Ý: Ý tưởng chỉ có thể giải quyết subtask ~3~ (và subtask ~2~), không thể áp dụng trong mọi trường hợp. Khi các thao tác loại ~1~ và loại ~2~ được thực hiện đan xen, một màu có thể có tập đỉnh thay đổi theo thời gian.
Độ phức tạp:
Độ phức tạp về thời gian của ý tưởng nêu trên có thể là ~O(Q \cdot \alpha(N) + N)~ hoặc ~O(Q \cdot \log(N) + N)~ (tùy thuộc vào cách ta cài đặt cấu trúc dữ liệu Disjoint Set Union):
- Nếu cấu trúc dữ liệu Disjoint Set Union được cài đặt với cả hai phương pháp gộp theo kích cỡ và nén đường đi thì độ phức tạp trung bình cho mỗi lần gộp tập đỉnh là ~O(\alpha(N))~ (với ~\alpha(N)~ là hàm Ackermann nghịch đảo). Nếu chỉ một trong hai phương pháp được sử dụng thì độ phức tạp cho mỗi lần gộp tập đỉnh là ~O(\log(N))~.
- Độ phức tạp của các bước xử lý còn lại của cách giải đã nêu sẽ tương tự với cách giải cho subtask ~2~ trước đó, tức ~O(N + Q)~.
Độ phức tạp về bộ nhớ của cách giải trên sẽ tương tự với subtask ~2~, tức ~O(N + Q)~.
Code minh họa:
#include <bits/stdc++.h>
using namespace std;
template<class A, class B>
bool maximize(A &a, const B& b) {
if (a < b) {
a = b;
return true;
}
return false;
}
template<class A, class B>
bool minimize(A &a, const B& b) {
if (a > b) {
a = b;
return true;
}
return false;
}
constexpr int MAX_N = 300'005, INF = 0X3F3F3F3F;
class DisjointSetUnion {
private:
mutable vector<int> roots;
public:
DisjointSetUnion() {};
void resize(const int n) {
roots.resize(n, -1);
}
int getRoot(const int x) const {
return (roots[x] < 0) ? x : (roots[x] = getRoot(roots[x]));
}
int unite(int x, int y) {
x = getRoot(x);
y = getRoot(y);
if (x == y)
return x;
if (roots[x] > roots[y])
swap(x, y);
roots[x] += roots[y];
return roots[y] = x;
}
};
signed roots[MAX_N], minimumDistance[MAX_N];
vector<int> graph[MAX_N];
DisjointSetUnion dsu;
int N, Q, c[MAX_N];
void runBFS() {
queue<int> q;
minimumDistance[c[1]] = 0;
q.push(c[1]);
for (; !q.empty(); q.pop()) {
const int &x = q.front();
for (const int &y : graph[x])
if (minimize(minimumDistance[y], minimumDistance[x] + 1))
q.push(y);
}
}
int main() {
bool firstTypeOperationPhase = false, sourceFlag = false;
#ifdef LOCAL
freopen("input.INP", "r", stdin);
#endif // LOCAL
cin.tie(0) -> sync_with_stdio(0);
cout.tie(0);
cin >> N >> Q;
dsu.resize(N + 1);
for (int i = 1; i <= N; ++i) {
cin >> c[i];
minimumDistance[i] = INF;
int &root = roots[c[i]];
root = (root ? dsu.unite(root, i) : i);
}
for (int q = 1, t = 0, x = 0, y = 0; q <= Q; ++q) {
cin >> t >> x >> y;
if (t == 2) {
int &rootX = roots[x];
if (rootX == 0)
continue;
int &rootY = roots[y];
rootY = (rootY ? dsu.unite(rootX, rootY) : rootX);
rootX = 0;
continue;
}
if (!firstTypeOperationPhase) {
for (int i = 1; i <= N; ++i)
if (roots[i])
c[dsu.getRoot(roots[i])] = i;
for (int i = 1; i <= N; ++i)
c[i] = c[dsu.getRoot(i)];
firstTypeOperationPhase = true;
}
if (roots[x] == 0 || roots[y] == 0)
continue;
graph[x].push_back(y);
graph[y].push_back(x);
if (x == c[1] && y == c[1])
sourceFlag = true;
}
runBFS();
cout << 0 << ' ';
for (int i = 2; i <= N; ++i) {
if (c[i] != c[1]) {
cout << ((minimumDistance[c[i]] < INF) ? minimumDistance[c[i]] : (-1)) << ' ';
continue;
}
cout << (sourceFlag ? 1 : ((!graph[c[1]].empty()) ? 2 : (-1))) << ' ';
}
cout << '\n';
return 0;
}
Subtask 4
Ý tưởng:
Việc xử lý trên đồ thị xây dựng như ở subtask ~1~ yêu cầu độ phức tạp thời gian lớn bởi đồ thị sẽ chứa rất nhiều cạnh (~O(Q \cdot N^2)~ cạnh). Tuy nhiên, ta nhận thấy rằng các thao tác này chỉ phụ thuộc vào mối quan hệ giữa các tập đỉnh chứ không bắt buộc phải giữa từng cặp đỉnh cụ thể. Do đó, ta có thể tìm cách xây dựng một đồ thị nén, trong đó:
- Khoảng cách ngắn nhất từ đỉnh ~1~ đến cách đỉnh khác trong đồ thị gốc vẫn được giữ nguyên trong đồ thị mới này.
- Số lượng cạnh không quá lớn.
Để xây dựng một đồ thị có ít cạnh hơn nhưng vẫn giữ nguyên khoảng cách ngắn nhất, ta có thể tạo các đỉnh đại diện cho từng tập đỉnh cùng màu (ở một thời điểm).
Chúng ta có thể xem xét một đồ thị ví dụ như sau để dễ hình dung ý tưởng hơn.
Giả sử ta cần thêm các cạnh nối từ tất cả các đỉnh xanh đến tất cả các đỉnh cam. Mục tiêu của ta không phải là tạo đủ mọi cạnh giữa hai tập, mà chỉ cần đảm bảo rằng tồn tại đường đi có độ dài 1 từ tập xanh đến tập cam.
Thay vì thêm ~r \times b~ cạnh (với ~r~ là số đỉnh xanh và ~b~ là số đỉnh cam), ta tạo hai đỉnh mới:- Đỉnh ~B~ với ý nghĩa là với mọi đỉnh có thể đến được từ đỉnh ~B~ thì cũng có thể đến được từ các đỉnh xanh tới tổng trọng số không đổi.
- Đỉnh ~R~ với ý nghĩa là với mọi đỉnh có thể đến được đỉnh ~R~ thì cũng có thể đến được các đỉnh cam tới tổng trọng số không đổi. Sau đó:
- Thêm các cạnh có trọng số ~0~ từ mỗi đỉnh xanh tới ~B~, và từ ~R~ tới mỗi đỉnh cam.
- Thêm một cạnh có trọng số ~1~ từ ~B~ tới ~R~. Khi đó, đi từ một đỉnh xanh ~x~ tới một đỉnh cam ~y~ tương đương với đi qua đường ~x \rightarrow B \rightarrow R \rightarrow y~ có tổng trọng số ~1~. Bằng cách nén như vậy, số cạnh giảm từ ~r \times b~ xuống còn ~r + b + 1~.
Mở rộng từ ý tưởng như trên, với mỗi tập đỉnh tại một điểm trong quá trình thực hiện các thao tác, ta sẽ tạo hai đỉnh đi và về (tương tự đỉnh ~B~ và ~R~ trong ví dụ trên) để đại diện cho tập đó. Cụ thể hơn:
- Với mỗi màu và tập đỉnh của nó ở thời điểm ban đầu (khi chưa thực hiện bất kì thao tác nào trong danh sách), ta tạo hai đỉnh cùng cạnh trọng số ~0~ tương ứng (như ví dụ trên).
- Khi ta xử lý thao tác loại ~2~, ta (có thể) sẽ có một tập đỉnh mới. Trong trường hợp đó, ta cũng tạo hai đỉnh mới đại diện cho tập đỉnh của màu sau khi được gộp lại và thực hiện nối như sau:
- Ta nối các đỉnh đi của hai tập cũ đến đỉnh đi mới với trọng số ~0~.
- Ta nối đỉnh về mới đến các đỉnh về của hai tập cũ với trọng số ~0~.
- Khi ta xử lý thao tác loại ~1~, ta chỉ cần thêm cạnh trọng số ~1~ giữa đỉnh đến và đỉnh đi của các tập đỉnh được xem xét trong thác tác (ta sẽ thêm tối đa hai cạnh bởi cạnh bởi cạnh trong đồ thị gốc là vô hướng).
- Sau khi ta dựng xong đồ thị (sau khi xử lý xong hết các thao tác trong danh sách), để tìm đường đi ngắn nhất từ đỉnh ~1~ đến các đỉnh còn lại, ta có thể sử dụng thuật toán BFS 0-1 bởi các cạnh của đồ thị có trọng số ~0~ hoặc ~1~ (hoặc thuật toán Dijkstra nhưng với độ phức tạp lớn hơn).
Ý tưởng cho subtask này có nhiều điểm tương đồng với cách xây dựng Kruskal Reconstruction Tree.
Độ phức tạp:
Độ phức tạp về thời gian của ý tưởng nêu trên là ~O(N + Q)~
- Việc dựng đồ thị có độ phức tạp ~O(N + Q)~ bởi:
- Khi dựng đỉnh mới và cạnh ở thời điểm ban điểm, ta sẽ thêm ~C~ đỉnh và ~2 \cdot N~ cạnh với ~C~ là số màu phân biệt ban đầu (~1 \leq C \leq N~; với mỗi đỉnh ban đầu, ta sẽ thêm hai cạnh mới).
- Với mỗi thao tác loại ~2~, ta thêm tối đa hai đỉnh và bốn cạnh. Ta có ~O(Q)~ thao tác loại ~2~.
- Với mỗi thao tác loại ~1~, ta thêm tối đa hai cạnh. Ta có ~O(Q)~ thao tác loại ~1~.
- Thuật toán BFS 0-1 có độ phức tạp ~O(N + Q)~ vì đồ thị được dựng lên có ~O(N + Q)~ đỉnh và cạnh (nếu ta sử dụng thuật toán Dijkstra, độ phức tạp sẽ là ~O((N + Q)\log(N + Q) + N + Q)~).
- Việc dựng đồ thị có độ phức tạp ~O(N + Q)~ bởi:
Tương tự, ý tưởng nêu trên có độ phức tạp về bộ nhớ là ~O(N + Q)~.
Code minh họa:
#include <bits/stdc++.h>
using namespace std;
template<class A, class B>
bool maximize(A &a, const B& b) {
if (a < b) {
a = b;
return true;
}
return false;
}
template<class A, class B>
bool minimize(A &a, const B& b) {
if (a > b) {
a = b;
return true;
}
return false;
}
constexpr int MAX_N = 3E5 + 5, MAX_VERTEX_COUNT = 1E6 + 6, INF = 0X3F3F3F3F;
int N, Q, c[MAX_N];
bool minimized[MAX_VERTEX_COUNT];
pair<int, int> vertexPairs[MAX_N];
vector<pair<int, bool> > graph[MAX_VERTEX_COUNT];
signed vertexCount, minimumDistance[MAX_VERTEX_COUNT];
void runBFS() {
deque<int> q;
for (int i = 2; i <= vertexCount; ++i)
minimumDistance[i] = INF;
q.push_back(1);
for (; !q.empty();) {
const int x = q.front();
q.pop_front();
if (minimized[x])
continue;
minimized[x] = true;
for (const auto &[y, w] : graph[x])
if (minimize(minimumDistance[y], minimumDistance[x] + w)) {
if (w)
q.push_back(y);
else
q.push_front(y);
}
}
}
int main() {
#ifdef LOCAL
freopen("input.INP", "r", stdin);
#endif // LOCAL
cin.tie(0) -> sync_with_stdio(0);
cout.tie(0);
cin >> N >> Q;
vertexCount = N;
for (int i = 1; i <= N; ++i) {
cin >> c[i];
auto &[source, sink] = vertexPairs[c[i]];
if (source <= 0) {
source = ++vertexCount;
sink = ++vertexCount;
}
graph[i].emplace_back(source, 0);
graph[sink].emplace_back(i, 0);
}
for (int q = 1, t = 0; q <= Q; ++q) {
cin >> t;
if (t == 1) {
int x = 0, y = 0;
cin >> x >> y;
const auto &[sourceX, sinkX] = vertexPairs[x];
const auto &[sourceY, sinkY] = vertexPairs[y];
if (sourceX && sinkY) {
graph[sourceX].emplace_back(sinkY, 1);
graph[sourceY].emplace_back(sinkX, 1);
}
} else {
int u = 0, v = 0;
cin >> u >> v;
const auto [sourceU, sinkU] = vertexPairs[u];
const auto [sourceV, sinkV] = vertexPairs[v];
auto &[source, sink] = vertexPairs[v];
vertexPairs[u] = make_pair(0, 0);
source = ++vertexCount;
sink = ++vertexCount;
graph[sourceU].emplace_back(source, 0);
graph[sourceV].emplace_back(source, 0);
graph[sink].emplace_back(sinkU, 0);
graph[sink].emplace_back(sinkV, 0);
}
}
runBFS();
for (int i = 1; i <= N; ++i)
cout << ((minimumDistance[i] < INF) ? minimumDistance[i] : (-1)) << ' ';
cout << '\n';
return 0;
}
Trình Chấm (tự viết):
import time
import shutil
import random
import subprocess
from abc import ABC
from pathlib import Path
from typing import List, Tuple
class TestGenerator(ABC):
MIN_N: int = 1
MAX_N: int = 300_000
MIN_Q: int = 1
MAX_Q: int = 300_000
def __init__(self):
self.N: int = 0
self.Q: int = 0
self.c: List[int] = []
self.operations: List[Tuple[int, int, int]] = []
self.generate()
def generate(self):
self.N = random.randint(self.MIN_N, self.MAX_N)
self.Q = random.randint(self.MIN_Q, self.MAX_Q)
self.c = [random.randint(1, self.N) for _ in range(self.N)]
self.operations = self._generate_operations()
def _generate_operations(self) -> List[Tuple[int, int, int]]:
return [self._generate_random_operation(random.randint(1, 2)) for _ in range(self.Q)]
def _generate_random_operation(self, operation_type: int) -> Tuple[int, int, int]:
return (operation_type, random.randint(1, self.N), random.randint(1, self.N))
def write_to_file(self, filename: str) -> None:
path = Path(filename)
path.parent.mkdir(parents = True, exist_ok = True)
with path.open('w') as f:
f.write(f"{self.N} {self.Q}\n")
f.write(" ".join(map(str, self.c)) + "\n")
for t, x, y in self.operations:
f.write(f"{t} {x} {y}\n")
class Subtask1TestGenerator(TestGenerator):
MAX_N = 100
MAX_Q = 100
class Subtask2TestGenerator(TestGenerator):
def _generate_operations(self) -> List[Tuple[int, int, int]]:
return [self._generate_random_operation(1) for _ in range(self.Q)]
class Subtask3TestGenerator(TestGenerator):
def _generate_operations(self) -> List[Tuple[int, int, int]]:
second_type_operation_count = random.randint(0, self.Q)
return [self._generate_random_operation(2 if i < second_type_operation_count else 1) for i in range(self.Q)]
class Subtask4TestGenerator(TestGenerator):
pass
class Validator:
TIME_LIMIT_IN_SECONDS = 1
VERDICTS = ["AC", "WA", "TLE", "RE"]
def __init__(self, tested_program_path: str, correct_program_path: str):
self.tested_program = Path(tested_program_path)
self.correct_program = Path(correct_program_path)
for program in (self.tested_program, self.correct_program):
if not program.exists():
raise FileNotFoundError(f"Program not found: {program}")
if not program.suffix.lower() == '.exe':
raise ValueError(f"Program must be an .EXE file: {program}")
def run_program(self, program_path: Path, input_file: Path, output_file: Path) -> Tuple[str, float, bool]:
program_directory = program_path.parent
destination_input = program_directory / "input.INP"
shutil.copy(input_file, destination_input)
destination_output = program_directory / output_file.name
if destination_output.exists():
destination_output.unlink()
start_time = time.time()
try:
process = subprocess.run(
[str(program_path)],
stdout=subprocess.PIPE,
stderr=subprocess.PIPE,
timeout=self.TIME_LIMIT_IN_SECONDS,
text=True,
cwd=str(program_directory)
)
execution_time = time.time() - start_time
if process.returncode != 0:
return "RE", execution_time, False
if destination_output.exists():
with destination_output.open('r') as f:
output = f.read().strip()
else:
output = process.stdout.strip()
return "OK", execution_time, True, output
except subprocess.TimeoutExpired:
return "TLE", self.TIME_LIMIT_IN_SECONDS, False, ""
except Exception as e:
return "RE", time.time() - start_time, False, str(e)
return "IE", time.time() - start_time, False, ""
def compare_outputs(self, tested_output: str, correct_output: str) -> str:
tested_lines = [line.strip() for line in tested_output.splitlines() if line.strip()]
correct_lines = [line.strip() for line in correct_output.splitlines() if line.strip()]
if tested_lines == correct_lines:
return "AC"
return "WA"
def validate_test(self, input_file: str) -> Tuple[str, float]:
input_path = Path(input_file)
input_directory = input_path.parent
correct_verdict, correct_time, correct_success, correct_output = self.run_program(
self.correct_program, input_path, self.correct_program.parent / "output.OUT"
)
if not correct_success:
return f"Correct program failed: {correct_verdict}", correct_time
answer_file = input_directory / "answer.txt"
with answer_file.open('w') as f:
f.write(correct_output)
tested_verdict, tested_time, tested_success, tested_output = self.run_program(
self.tested_program, input_path, self.tested_program.parent / "output.OUT"
)
if not tested_success:
return tested_verdict, tested_time
output_file = input_directory / "output.out"
with output_file.open('w') as f:
f.write(tested_output)
verdict = self.compare_outputs(tested_output, correct_output)
return verdict, tested_time
SUBTASK_GENERATORS = [
Subtask1TestGenerator,
Subtask2TestGenerator,
Subtask3TestGenerator,
Subtask4TestGenerator,
]
SUBTASK_TEST_PERCENTAGES = [20, 30, 20, 30]
TOTAL_TEST_COUNT = 100
if __name__ == "__main__":
random.seed(20251004)
subtask_test_counts = [TOTAL_TEST_COUNT * percentage // 100 for percentage in SUBTASK_TEST_PERCENTAGES]
validator = Validator(
tested_program_path = "programs/tested_program/main.exe",
correct_program_path = "programs/correct_program/main.exe",
)
overall_summary = {}
for verdict in Validator.VERDICTS:
overall_summary[verdict] = 0
for subtask_index in range(len(SUBTASK_GENERATORS)):
generator = SUBTASK_GENERATORS[subtask_index]()
subtask_summary = {}
for verdict in Validator.VERDICTS:
subtask_summary[verdict] = 0
for test_index in range(subtask_test_counts[subtask_index]):
filename = f"tests/subtask{subtask_index + 1:02d}/test{test_index + 1:02d}/input.INP"
generator.generate()
generator.write_to_file(filename)
verdict, tested_time = validator.validate_test(filename)
subtask_summary[verdict] += 1
print(f"Subtask {subtask_index + 1}, Test {test_index + 1}: Verdict = {verdict}, Time = {tested_time:.3f}s")
print(f"Subtask {subtask_index + 1} Summary:")
for verdict, count in subtask_summary.items():
overall_summary[verdict] += count
print(f"\t{verdict}: {count} tests")
print("Overall Summary:")
for verdict, count in overall_summary.items():
print(f"\t{verdict}: {count} tests")
Lời giải #2
Subtask ~1~: ~N, Q \le 100~
Đây là subtask đơn giản nhất của bài toán. Đối với subtask này, ta chỉ cần xây dựng đồ thị theo yêu cầu của bài toán là giải được.
Việc tìm đường đi ngắn nhất từ đỉnh ~1~ có thể được thực hiện bằng thuật toán BFS.
Độ phức tạp của thuật toán và các subtask nói chung là bằng ~\mathcal{O}(A + B)~ với ~A~ là thời gian xây dựng đồ thị, còn ~B~ là thời gian thực hiện tìm đường đi ngắn nhất tới các đỉnh.
Đối với subtask này, ta có độ phức tạp ~\mathcal{O}(A + B)~ với ~A = \mathcal{O}(Q \times N^2), B = \mathcal{O}(|V| + |E|)~ với ~|V| = \mathcal{O}(N), |E| = \mathcal{O}(N^2)~.
Subtask ~2~: chỉ có thao tác loại ~1~
Cách nối các cặp đỉnh là không hiệu quả với giới hạn cao (~N \le 3 \times 10^5~) nên ta cần một hướng tiếp cận khác.
Ta sẽ chia các đỉnh dựa trên màu sắc của chúng. Mỗi nhóm màu sắc sẽ có hai đỉnh ảo: một đỉnh ảo đi vào và một đỉnh ảo đi ra.
Ở hình minh hoạ dưới đây, các đỉnh được nhóm theo màu, các đỉnh màu xanh lá là các đỉnh ảo đi ra còn màu đỏ là các đỉnh ảo đi vào nhóm màu đó.
Với mỗi truy vấn loại ~1~, ta sẽ xây dựng các cung nối các đỉnh ảo như sau:
- Nối đỉnh ảo đi ra của màu ~x~ với đỉnh ảo đi vào của màu ~y~
- Nối đỉnh ảo đi ra của màu ~y~ với đỉnh ảo đi vào của màu ~x~
Hình minh hoạ dưới đây là đồ thị sau truy vấn 1 1 2.
Trọng số của các cung được phân định như nhau: các cung nối đỉnh thực với đỉnh ảo hoặc đỉnh ảo với đỉnh thực có trọng số là ~0~, các cung nối các đỉnh ảo với nhau có trọng số là ~1~. Với các giá trị trọng số này, việc tìm đường đi ngắn nhất từ đỉnh ~1~ có thể được thực hiện bằng thuật toán BFS 0 - 1.
Đối với subtask ~2~, ta có độ phức tạp ~\mathcal{O}(A + B)~ với ~A = \mathcal{O}(Q), B = \mathcal{O}(|V| + |E|)~ với ~|V| = \mathcal{O}(N), |E| = \mathcal{O}(Q)~.
Subtask ~3~: Tất cả thao tác loại ~2~ xuất hiện trước thao tác loại ~1~
Các thao tác loại ~2~ là các thao tác thay đổi màu sắc của các đỉnh trên đồ thị. Vì vậy, với các thao tác loại ~2~ xuất hiện trước, ta chỉ cần thay đổi các giá trị màu sắc thành màu mới tương ứng. Sau đó, khi còn lại các thao tác loại ~1~, ta thực hiện giống như subtask ~2~.
Giống như subtask ~2~, ta có độ phức tạp ~\mathcal{O}(A + B)~ với ~A = \mathcal{O}(Q), B = \mathcal{O}(|V| + |E|)~ với ~|V| = \mathcal{O}(N), |E| = \mathcal{O}(Q)~.
Subtask ~4~: không có giới hạn bổ sung
Đối với subtask cuối cùng, hướng giải quyết sẽ tương tự với subtask ~2~, tuy nhiên sẽ có đôi chút điểm khác biệt.
Đối với các thao tác loại ~1~, việc thêm các cạnh và trọng số sẽ giống hệt như subtask ~2~.
Còn với các thao tác loại ~2~, ta xử lí như sau: tạo hai đỉnh ảo vào và ra mới cho màu ~v~. Sau đó, ta tạo cung nối đỉnh ra cũ của hai màu ~u, v~ với đỉnh ra mới của màu ~v~, và tạo cung nối đỉnh vào mới của màu ~v~ với đỉnh ra cũ của hai màu ~u, v~. Các cung mới này có trọng số là ~0~.
Ở hình minh hoạ này mô tả đồ thị sau truy vấn thao tác loại ~2~ 2 2 3.
Sau khi nối xong, ta coi đỉnh ảo vào và ra cũ của ~u, v~ "hết hạn sử dụng" - không coi các đỉnh ảo này là đại diện cho các nhóm các đỉnh chung màu nữa.
Một lưu ý nữa là nếu không có nhóm điểm màu ~u~ hoặc ~v~ hoặc cả hai thì ta không cần thiết phải nối các đỉnh ảo của nhóm màu đấy với các đỉnh ảo mới của ~v~.
Sau khi xây dựng xong, ta có thể tìm đường đi ngắn nhất từ đỉnh ~1~ bằng BFS 0 - 1.
Giống như subtask ~2~ và ~3~, ta có độ phức tạp ~\mathcal{O}(A + B)~ với ~A = \mathcal{O}(Q), B = \mathcal{O}(|V| + |E|)~ với ~|V| = \mathcal{O}(N), |E| = \mathcal{O}(Q)~.
Xin trân trọng cảm ơn các tác giả đã đồng hành cùng chuyên mục. Các tác giả có bài giải được đăng trong Tạp chí VNOI - Số 1 đã được đội ngũ Tạp chí VNOI liên hệ để nhận phần quà tri ân từ VNOI.
Bình luận