Hướng dẫn giải của Lò cò
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 tìm đường đi dài nhất (về số lượng đỉnh) trong một đồ thị có hướng được tạo ra từ một tập hợp các số nguyên dương. Đồ thị được tạo như sau: Với mọi bộ ba chỉ số i, j, k phân biệt mà giá trị tại đó Ai + Aj = A_k, ta có hai cạnh có hướng từ i -> k và j -> k. Yêu cầu là tìm đường đi qua nhiều đỉnh nhất có thể (đường đi không được lặp lại đỉnh).
Các cách tiếp cận
Cách Quy hoạch động trên đồ thị DAG
#include <bits/stdc++.h>
using namespace std;
int n;
int a[1005];
int f[1005]; // f[i] là độ dài đường đi dài nhất kết thúc tại đỉnh i
vector<int> adj[1005]; // Danh sách kề
int main() {
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
// Xây dựng đồ thị
// Tối ưu: Dùng mảng đếm để kiểm tra t tồn tại nhanh
int cnt[2005] = {0}; // Giả sử giá trị tối đa là 1000, tổng tối đa 2000
int pos[2005]; // Lưu chỉ số xuất hiện đầu tiên của giá trị (hoặc dùng vector)
// Tuy nhiên, để đơn giản và chính xác với điều kiện i, j, k phân biệt,
// ta duyệt O(n^2) để xây dựng đồ thị.
// Để tránh xây dựng đồ thị quá lớn, ta chỉ xét các cạnh hợp lệ.
// Do A_i <= 1000, ta có thể dùng mảng đếm giá trị.
vector<int> values;
for(int i=1; i<=n; i++) values.push_back(a[i]);
sort(values.begin(), values.end());
values.erase(unique(values.begin(), values.end()), values.end());
// Sử dụng map để lưu vị trí các giá trị
map<int, vector<int>> posMap;
for (int i = 1; i <= n; i++) {
posMap[a[i]].push_back(i);
}
// Xây dựng cạnh
// Duyệt mọi cặp (i, j) để tìm k sao cho a[k] = a[i] + a[j]
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (i == j) continue;
int target = a[i] + a[j];
if (posMap.count(target)) {
for (int k : posMap[target]) {
if (k != i && k != j) {
adj[i].push_back(k);
}
}
}
}
}
// Quy hoạch động (Tìm đường đi dài nhất trên DAG)
// Sắp xếp topological có thể khó do điều kiện đặc biệt,
// nhưng ta có thể dùng DFS + Memoization (đồ thị có hướng, không có chu trình).
// Ta cần kiểm tra chu trình: bài toán nay không có chu trình vì tổng giá trị tăng.
function<int(int)> dp = [&](int u) {
if (f[u] != 0) return f[u];
int res = 1;
for (int v : adj[u]) {
res = max(res, dp(v) + 1);
}
return f[u] = res;
};
int ans = 0;
for (int i = 1; i <= n; i++) {
ans = max(ans, dp(i));
}
cout << ans;
return 0;
}
- Time Complexity: O(N^2)
- Space Complexity: O(N^2)
Cách tiếp cận này xây dựng trực tiếp đồ thị có hướng dựa trên điều kiện Ai + Aj = A_k. Sau đó, vì đồ thị không chu trình (vì giá trị tăng dần dọc theo cạnh), ta sử dụng quy hoạch động kết hợp DFS (hoặc Topo sort) để tìm đường đi dài nhất. Tuy nhiên, việc xây dựng đồ thị trực tiếp có thể tốn kém bộ nhớ nếu có nhiều cạnh.
Cách Quy hoạch động theo giá trị (Optimized)
#include <bits/stdc++.h>
using namespace std;
int n;
int a[1003];
int f[1003]; // f[i] là độ dài đường đi dài nhất kết thúc tại vị trí i
int dem[2005]; // Mảng đếm số lượng xuất hiện của các giá trị
int dp[2005]; // dp[x] là độ dài đường đi dài nhất kết thúc tại giá trị x
int main() {
int maxn = 1;
cin >> n;
// Đọc dữ liệu và khởi tạo
for(int i = 1; i <= n; i++) {
cin >> a[i];
dp[a[i]] = 1; // Mỗi đỉnh đều là đường đi độ dài 1
dem[a[i]]++;
f[i] = 1;
}
// Sắp xếp để xử lý theo thứ tự tăng dần
sort(a + 1, a + n + 1);
// Duyệt qua từng số a[i] (xem như 'k' trong công thức a[i] = a[j] + a[k'])
for(int i = 2; i <= n; i++) {
for(int j = 1; j < i; j++) {
int res = a[i] - a[j]; // 'res' chính là số thứ ba trong bộ ba
// Điều kiện: res phải tồn tại (dem[res] > 0)
// Và đảm bảo các chỉ số phân biệt.
// Do a[i] và a[j] là 2 chỉ số phân biệt, ta chỉ cần res khác a[j] hoặc có ít nhất 2 số bằng res.
if (dem[res] > 0) {
// Nếu res == a[j]: cần ít nhất 2 số bằng giá trị này
if (res == a[j]) {
if (dem[res] >= 2) {
f[i] = max(f[i], f[j] + 1);
}
} else {
// res != a[j]: chỉ cần t tồn tại
// Tuy nhiên, ta cần update dp[a[i]] từ dp[a[j]] và dp[res]
// Logic từ code mẫu:
// Nếu có >= 2 số res: có thể lấy max(f[j]+1, f[res]+1)
// Nếu có 1 số res và res != a[j]: có thể lấy max(f[j]+1, f[res]+1)
// Code mẫu tối ưu hóa logic:
if (dem[res] >= 2) {
f[i] = max(f[i], max(f[j] + 1, dp[res] + 1));
} else if (dem[res] == 1) {
f[i] = max(f[i], max(f[j] + 1, dp[res] + 1));
}
}
}
}
// Sau khi xử lý xong a[i], cập nhật dp[a[i]]
dp[a[i]] = max(dp[a[i]], f[i]);
maxn = max(maxn, f[i]);
}
cout << maxn;
return 0;
}
- Time Complexity: O(N^2)
- Space Complexity: O(1000)
Thay vì xây dựng đồ thị, ta quy hoạch động trực tiếp. Gọi f[i] là độ dài đường đi dài nhất kết thúc tại vị trí i (hoặc giá trị a[i]). Với mỗi a[i], ta duyệt các a[j] trước đó (j < i) để tìm a[k] = a[i] - a[j]. Nếu a[k] t tồn tại và thỏa mãn điều kiện phân biệt chỉ số, ta cập nhật f[i] = max(f[i], f[j] + 1, f[k] + 1). Cách này tránh xây dựng đồ thị rườm rà và tối ưu bộ nhớ.
Cách Hash Map và Quy hoạch động (Phân tích từ Solution 1 & 3)
#include <bits/stdc++.h>
using namespace std;
int f[1003], a[1003], n, dem[1003];
int main() {
int maxn = 1;
cin >> n;
for(int i = 1; i <= n; i++) {
cin >> a[i];
f[a[i]] = 1; // Khởi tạo độ dài max cho mỗi giá trị
dem[a[i]]++;
}
sort(a + 1, a + n + 1);
// Duyệt qua từng số a[i]
for(int i = 2; i <= n; i++) {
// Duyệt các số trước đó a[j]
for(int j = 1; j < i; j++) {
int res = a[i] - a[j];
// Kiểm tra xem 'res' có trong input không
// Cập nhật f[a[i]] dựa trên f[a[j]] và f[res]
if (dem[res] >= 2) {
// Nếu res xuất hiện ít nhất 2 lần, ta có thể chắc chắn tìm được 2 số phân biệt
// để tạo thành bộ 3 (a[j], res, a[i])
f[a[i]] = max(f[a[j]] + 1, max(f[res] + 1, f[a[i]]));
}
else if (dem[res] == 1 && a[j] != res) {
// Nếu res xuất hiện 1 lần, ta cần đảm bảo a[j] != res để phân biệt
f[a[i]] = max(f[a[i]], max(f[res] + 1, f[a[j]] + 1));
}
maxn = max(f[a[i]], maxn);
}
}
cout << maxn;
return 0;
}
- Time Complexity: O(N^2)
- Space Complexity: O(1000)
Đây là cách tiếp cận được dùng trong các solution mẫu. Ta sử dụng mảng f lưu độ dài đường đi dài nhất kết thúc bằng giá trị x. Với mỗi cặp (a[i], a[j]), ta tính số còn lại res. Logic chính là cập nhật f[a[i]] dựa trên độ dài đường đi tốt nhất có thể dẫn đến a[i] thông qua a[j] và res. Cách này xử lý các trùng lặp của giá trị một cách cẩn thận.
Phân tích độ phức tạp
| Cách tiếp cận | Time | Space | Tên |
|---|---|---|---|
| 1 | O(N^2) | O(N^2) | Quy hoạch động trên đồ thị DAG |
| 2 | O(N^2) | O(1000) | Quy hoạch động theo giá trị (Optimized) |
| 3 | O(N^2) | O(1000) | Hash Map và Quy hoạch động (Phân tích từ Solution 1 & 3) |
Bài học kinh nghiệm
- Bài toán có thể được mô hình hóa như tìm đường đi dài nhất trên đồ thị có hướng (DAG) vì giá trị của node đích (Ak) luôn lớn hơn giá trị của node nguồn (Ai, A_j).
- Thay vì xây dựng đồ thị với số cạnh lớn, ta có thể sử dụng quy hoạch động trực tiếp trên các giá trị.
- Vấn đề mấu chốt là xử lý các trường hợp giá trị trùng lặp để đảm bảo các chỉ số i, j, k là phân biệt.
Lỗi thường gặp
- Bỏ qua điều kiện các vòng tròn phải khác nhau (i, j, k phân biệt), dẫn đến dùng chung một chỉ số cho nhiều vai trò.
- Xử lý sai trường hợp Ai = Aj = A_k / 2 (ví dụ 2+2=4). Cần đảm bảo có ít nhất 2 số 2 để tạo thành cặp và 1 số 4.
- Không tối ưu hóa việc kiểm tra sự tồn tại của giá trị res, dẫn đến TLE nếu duyệt lại toàn bộ mảng.
Bình luận