Hướng dẫn cho SKY
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
Có \(N\) tòa nhà (đánh số từ \(0\) đến \(N-1\)) và \(M\) chú doge. Doge thứ \(i\) ban đầu ở tòa nhà \(B_i\) và có năng lượng nhảy \(P_i\). Nếu một doge có năng lượng \(P\) đang ở tòa nhà \(b\), nó có thể nhảy sang tòa nhà \(b-P\) hoặc \(b+P\) (nếu tòa nhà đó tồn tại) với chi phí 1 bước nhảy. Tại một tòa nhà, các doge có thể truyền tin cho nhau với chi phí bằng 0. Cần tìm số bước nhảy ít nhất để truyền tin từ doge 0 đến doge 1.
Phân tích
Đây là bài toán tìm đường đi ngắn nhất trên đồ thị.
- Nút của đồ thị: Một trạng thái có thể được xác định bởi cặp
(tòa nhà hiện tại, năng lượng của doge đang giữ tin). - Số lượng trạng thái: Nếu làm theo cách thông thường, số lượng trạng thái có thể lên tới \(N \times N\) (vì có tối đa \(N\) giá trị \(P_i\) khác nhau), điều này là quá lớn với \(N = 30,000\).
Quan sát chủ chốt: Căn lề (Square Root Decomposition)
Ta chia các giá trị năng lượng \(P_i\) thành hai nhóm dựa trên một ngưỡng \(S\):
- Nhóm \(P_i \ge S\): Số lượng các tòa nhà mà doge này có thể nhảy tới tối đa là \(N/S\). Với \(S = \sqrt{N}\), số bước nhảy không quá lớn.
- Nhóm \(P_i < S\): Số lượng các giá trị \(P_i\) khác nhau là nhỏ.
Nếu ta coi mỗi trạng thái là (vị trí tòa nhà, năng lượng P), số lượng trạng thái sẽ là \(N \times S\). Với \(N=30,000\), chọn \(S \approx 100 \sim 170\) là hợp lý để cân bằng giữa số trạng thái và thời gian thực thi.
Hướng giải quyết
Cấu trúc đồ thị
Ta định nghĩa các trạng thái trong thuật toán Dijkstra như sau:
- Trạng thái \((u, p)\): Tin nhắn đang ở tòa nhà \(u\) và được giữ bởi một doge có năng lượng \(p\).
- Trạng thái đặc biệt \((u, 0)\): Tin nhắn đang ở tòa nhà \(u\) và sẵn sàng để chuyển cho bất kỳ doge nào khác đang đứng ở tòa nhà \(u\).
Các cạnh và trọng số
- Di chuyển giữa các tòa nhà với cùng năng lượng \(p\):
- Từ \((u, p)\) đến \((u + p, p)\) và \((u - p, p)\) với trọng số \(1\).
- Chuyển tin từ doge sang trạng thái tự do:
- Từ \((u, p)\) về \((u, 0)\) với trọng số \(0\).
- Doge tại tòa nhà \(u\) bắt đầu di chuyển:
- Nếu tại tòa nhà \(u\) có doge với năng lượng \(P_i\), ta có cạnh từ \((u, 0)\) đến \((u, P_i)\) với trọng số \(0\).
Tối ưu hóa
Để tránh tạo quá nhiều trạng thái, ta chỉ tạo trạng thái \((u, p)\) khi \(p < S\). Với \(p \ge S\), ta thực hiện nhảy trực tiếp trong quá trình Dijkstra và đẩy các vị trí mới \((u \pm k \cdot p, 0)\) vào hàng đợi ưu tiên.
Độ phức tạp
- Thời gian: \(O((N \cdot S + M) \log(N \cdot S))\) với \(S \approx \sqrt{N}\). Trong thực tế, sử dụng BFS hoặc Dijkstra tối ưu có thể chạy nhanh hơn.
- Bộ nhớ: \(O(N \cdot S)\) để lưu khoảng cách đến các trạng thái.
Code tham khảo
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 30005;
const int BORDER = 175; // Ngưỡng căn lề
const int INF = 1e9;
int N, M;
int B[MAXN], P[MAXN];
vector<int> doges[MAXN];
int dist[MAXN][BORDER + 5];
struct State {
int u, p, d;
bool operator>(const State& other) const {
return d > other.d;
}
};
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> N >> M;
for (int i = 0; i < M; ++i) {
cin >> B[i] >> P[i];
doges[B[i]].push_back(P[i]);
}
// Khởi tạo khoảng cách
for (int i = 0; i < N; ++i) {
for (int j = 0; j <= BORDER; ++j) {
dist[i][j] = INF;
}
}
priority_queue<State, vector<State>, greater<State>> pq;
// Doge 0 bắt đầu tại B[0] với năng lượng P[0]
// Ta coi trạng thái p=0 là trạng thái "đang ở tòa nhà u và chọn doge"
dist[B[0]][0] = 0;
pq.push({B[0], 0, 0});
while (!pq.empty()) {
State top = pq.top();
pq.pop();
int u = top.u;
int p = top.p;
int d = top.d;
if (d > dist[u][p]) continue;
// Nếu đã đến tòa nhà của doge 1 ở trạng thái tự do
if (u == B[1] && p == 0) {
cout << d << endl;
return 0;
}
if (p == 0) {
// Tại tòa nhà u, chọn một doge để di chuyển
for (int energy : doges[u]) {
if (energy <= BORDER) {
if (dist[u][energy] > d) {
dist[u][energy] = d;
pq.push({u, energy, d});
}
} else {
// Nếu năng lượng lớn, nhảy trực tiếp đến các vị trí có thể
// Nhảy sang phải
for (int step = 1; u + step * energy < N; ++step) {
int v = u + step * energy;
if (dist[v][0] > d + step) {
dist[v][0] = d + step;
pq.push({v, 0, dist[v][0]});
}
}
// Nhảy sang trái
for (int step = 1; u - step * energy >= 0; ++step) {
int v = u - step * energy;
if (dist[v][0] > d + step) {
dist[v][0] = d + step;
pq.push({v, 0, dist[v][0]});
}
}
}
}
} else {
// Đang di chuyển với năng lượng p <= BORDER
// 1. Nhảy sang trái/phải
if (u + p < N && dist[u + p][p] > d + 1) {
dist[u + p][p] = d + 1;
pq.push({u + p, p, d + 1});
}
if (u - p >= 0 && dist[u - p][p] > d + 1) {
dist[u - p][p] = d + 1;
pq.push({u - p, p, d + 1});
}
// 2. Dừng lại tại tòa nhà u và giải phóng tin nhắn (chuyển về p=0)
if (dist[u][0] > d) {
dist[u][0] = d;
pq.push({u, 0, d});
}
}
}
cout << -1 << endl;
return 0;
}
Bình luận