Hướng dẫn giải của Thiết kế khu vườn
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
Cho N điểm tọa độ nguyên đôi một phân biệt. Đếm số lượng hình vuông có cạnh song song với trục tọa độ sao cho 4 đỉnh của hình vuông đều là các điểm cho trước. N ≤ 100,000 và tọa độ nằm trong [-10^6, 10^6].
Các cách tiếp cận
Cách Brute Force (Tối ưu hóa)
#include <bits/stdc++.h>
using namespace std;
static inline long long key(int x, int y) {
return ((long long)x << 32) | (unsigned int)y;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N;
if (!(cin >> N)) return 0;
unordered_set<long long> S;
S.reserve(N * 2);
vector<pair<int, int>> points(N);
map<int, vector<int>> row;
for (int i = 0; i < N; ++i) {
int x, y;
cin >> x >> y;
points[i] = {x, y};
S.insert(key(x, y));
row[y].push_back(x);
}
for (auto& entry : row) {
sort(entry.second.begin(), entry.second.end());
}
long long ans = 0;
const int B = 350; // Threshold for heavy rows
vector<int> heavyYs;
for (auto& entry : row) {
if (entry.second.size() > B) {
heavyYs.push_back(entry.first);
}
}
// Case 1: Iterate over all pairs of points in light rows
for (auto& entry : row) {
int y = entry.first;
auto& xs = entry.second;
if (xs.size() <= B) {
for (int i = 0; i < xs.size(); ++i) {
for (int j = i + 1; j < xs.size(); ++j) {
int x1 = xs[i];
int x2 = xs[j];
int d = x2 - x1;
// Check (x1, y+d) and (x2, y+d)
if (S.find(key(x1, y + d)) != S.end() && S.find(key(x2, y + d)) != S.end()) {
ans++;
}
}
}
}
}
// Case 2: Iterate over pairs of rows (one heavy, one light)
for (int y_heavy : heavyYs) {
auto& xs_heavy = row[y_heavy];
for (auto& entry : row) {
int y = entry.first;
if (y == y_heavy) continue;
auto& xs_light = entry.second;
int d = abs(y - y_heavy);
for (int x : xs_light) {
if (S.find(key(x, y_heavy)) != S.end()) {
if (S.find(key(x + d, y)) != S.end() && S.find(key(x + d, y_heavy)) != S.end()) {
ans++;
}
if (S.find(key(x - d, y)) != S.end() && S.find(key(x - d, y_heavy)) != S.end()) {
ans++;
}
}
}
}
}
// Case 3: Iterate over pairs of heavy rows
for (int i = 0; i < heavyYs.size(); ++i) {
for (int j = i + 1; j < heavyYs.size(); ++j) {
int y1 = heavyYs[i];
int y2 = heavyYs[j];
int d = y2 - y1;
auto& xs1 = row[y1];
auto& xs2 = row[y2];
// Find common x-coordinates in both rows
for (int x : xs1) {
if (S.find(key(x, y2)) != S.end()) {
if (S.find(key(x + d, y1)) != S.end() && S.find(key(x + d, y2)) != S.end()) {
ans++;
}
}
}
}
}
cout << ans << endl;
return 0;
}
- Time Complexity: O(N * sqrt(N))
- Space Complexity: O(N)
Phương pháp này chia các hàng (y-coordinates) thành hai loại: 'nhẹ' (dưới 350 điểm) và 'nặng' (trên 350 điểm).
- Với các hàng nhẹ, ta duyệt tất cả các cặp điểm trên cùng một hàng để xác định cạnh dưới của hình vuông. Độ phức tạp là O(B^2 * N/ B) ~ O(N * B).
- Với các hàng nặng, ta không thể duyệt cặp điểm. Thay vào ta dùng các hàng nhẹ để tạo cạnh dưới và kiểm tra với hàng nặng làm cạnh trên (hoặc ngược lại). Độ phức tạp O(N * B).
- Với hai hàng cùng nặng, ta chỉ cần kiểm tra các điểm chung (intersection), số lượng hàng nặng rất ít nên độ phức tạp chấp nhận được. Tổng thể, đây là phương pháp sqrt-decomposition để giảm độ phức tạp từ O(N^2) xuống mức chấp nhận được.
Cách Hash Map Optimization
#include <bits/stdc++.h>
using namespace std;
static inline long long key(int x, int y) {
return ((long long)x << 32) | (unsigned int)y;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N; cin >> N;
unordered_set<long long> S;
S.reserve(N * 2);
vector<pair<int, int>> points(N);
map<int, vector<int>> row;
for (int i = 0; i < N; ++i) {
int x, y; cin >> x >> y;
points[i] = {x, y};
S.insert(key(x, y));
row[y].push_back(x);
}
for (auto& entry : row) sort(entry.second.begin(), entry.second.end());
long long ans = 0;
const int B = 320;
vector<int> heavyYs;
for (auto& entry : row) if (entry.second.size() > B) heavyYs.push_back(entry.first);
// Light rows
for (auto& entry : row) {
int y = entry.first;
auto& xs = entry.second;
if (xs.size() > B) continue;
for (int i = 0; i < xs.size(); ++i) {
for (int j = i + 1; j < xs.size(); ++j) {
int x1 = xs[i];
int x2 = xs[j];
int len = x2 - x1;
if (S.find(key(x1, y + len)) != S.end() && S.find(key(x2, y + len)) != S.end()) ans++;
}
}
}
// Heavy rows with light rows
for (int y_heavy : heavyYs) {
auto& xs_heavy = row[y_heavy];
for (auto& entry : row) {
int y = entry.first;
if (y == y_heavy) continue;
auto& xs_light = entry.second;
int d = abs(y - y_heavy);
for (int x : xs_light) {
if (S.find(key(x, y_heavy)) != S.end()) {
if (S.find(key(x + d, y)) != S.end() && S.find(key(x + d, y_heavy)) != S.end()) ans++;
if (S.find(key(x - d, y)) != S.end() && S.find(key(x - d, y_heavy)) != S.end()) ans++;
}
}
}
}
// Heavy rows with heavy rows
for (int i = 0; i < heavyYs.size(); ++i) {
for (int j = i + 1; j < heavyYs.size(); ++j) {
int y1 = heavyYs[i];
int y2 = heavyYs[j];
int d = y2 - y1;
auto& xs1 = row[y1];
auto& xs2 = row[y2];
for (int x : xs1) {
if (S.find(key(x, y2)) != S.end()) {
if (S.find(key(x + d, y1)) != S.end() && S.find(key(x + d, y2)) != S.end()) ans++;
}
}
}
}
cout << ans << endl;
return 0;
}
- Time Complexity: O(N * sqrt(N))
- Space Complexity: O(N)
Đây là phiên bản chi tiết của phương pháp sqrt decomposition.
- Sử dụng
unordered_setđể kiểm tra sự tồn tại của điểm với thời gian O(1). - Sử dụng
maphoặcunordered_mapđể nhóm các điểm theo tọa độ y. - Chia xử lý thành 3 trường hợp: (1) Hai đỉnh dưới thuộc hàng nhẹ, (2) Một đỉnh dưới thuộc hàng nhẹ và một đỉnh trên thuộc hàng nặng (hoặc ngược lại), (3) Hai đỉnh dưới thuộc hàng nặng. Điểm khác biệt chính so với giải pháp khác là cách tổ chức code rõ ràng hơn, nhưng logic cơ bản là giống nhau.
Cách Sử dụng mảng đánh dấu (Coordinates Compression)
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
const int OFFSET = 1000000;
int n;
int x[MAXN], y[MAXN];
vector<int> row[2000005];
bool mark[2000005];
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for (int i = 0; i < n; i++) {
cin >> x[i] >> y[i];
y[i] += OFFSET;
row[y[i]].push_back(x[i]);
}
for (int i = 0; i < 2000005; i++) {
if (!row[i].empty()) sort(row[i].begin(), row[i].end());
}
long long res = 0;
int B = sqrt(n);
vector<int> heavy;
for (int i = 0; i < 2000005; i++) {
if (row[i].size() > B) heavy.push_back(i);
}
// Light rows
for (int i = 0; i < 2000005; i++) {
if (row[i].size() == 0 || row[i].size() > B) continue;
for (int j = 0; j < row[i].size(); j++) {
for (int k = j + 1; k < row[i].size(); k++) {
int d = row[i][k] - row[i][j];
if (binary_search(row[i + d].begin(), row[i + d].end(), row[i][j]) &&
binary_search(row[i + d].begin(), row[i + d].end(), row[i][k])) {
res++;
}
}
}
}
// Heavy rows
for (int i = 0; i < heavy.size(); i++) {
int y1 = heavy[i];
// Mark points in row y1
for (int x_val : row[y1]) {
mark[x_val + OFFSET] = true;
}
for (int j = i + 1; j < heavy.size(); j++) {
int y2 = heavy[j];
int d = y2 - y1;
for (int x_val : row[y2]) {
// Check for square with bottom at y1, top at y2
if (mark[x_val + OFFSET]) {
if (binary_search(row[y1].begin(), row[y1].end(), x_val + d) &&
binary_search(row[y2].begin(), row[y2].end(), x_val + d)) {
res++;
}
}
}
}
// Cleanup mark
for (int x_val : row[y1]) {
mark[x_val + OFFSET] = false;
}
}
cout << res << endl;
return 0;
}
- Time Complexity: O(N * sqrt(N))
- Space Complexity: O(Range of coordinates)
Giải pháp này sử dụng mảng lớn (khoảng 2 triệu phần tử) để lưu trữ các hàng thay vì map, giúp truy cập nhanh hơn. Tuy nhiên, vẫn áp dụng phương pháp chia nhóm hàng nặng/nhẹ.
- Hàng nhẹ: Duyệt cặp O(size^2) và dùng binary search để kiểm tra đỉnh đối diện.
- Hàng nặng: Dùng mảng đánh dấu (mark) để kiểm tra sự tồn tại của điểm thuộc hàng kia nhanh hơn O(1). Giải pháp này có vẻ sử dụng mảng quá lớn so với yêu cầu tọa độ [-10^6, 10^6] (cần mảng size ~2*10^6) và cách xử lý hàng nặng chưa thực sự tối ưu hết 2 chiều.
Phân tích độ phức tạp
| Cách tiếp cận | Time | Space | Tên |
|---|---|---|---|
| 1 | O(N * sqrt(N)) | O(N) | Brute Force (Tối ưu hóa) |
| 2 | O(N * sqrt(N)) | O(N) | Hash Map Optimization |
| 3 | O(N * sqrt(N)) | O(Range of coordinates) | Sử dụng mảng đánh dấu (Coordinates Compression) |
Bài học kinh nghiệm
- Bài toán có thể giảm độ phức tạp từ O(N^2) xuống O(N * sqrt(N)) bằng cách phân tích tần suất xuất hiện của các tọa độ y.
- Một hình vuông được xác định bởi cạnh dưới (2 điểm cùng y). Nếu biết cạnh dưới, cạnh trên có thể được suy ra dễ dàng.
- Sử dụng Hash Set để kiểm tra sự tồn tại của điểm với thời gian O(1) là chìa khóa.
Lỗi thường gặp
- Đếm trùng các hình vuông nếu không kiểm soát đúng thứ tự duyệt.
- Sử dụng map<int, vector<int>> và binary search có thể chậm hơn unordered_map + hash set trong một số trường hợp do chi phí so sánh.
- Quên xử lý trường hợp số lượng hàng nặng rất lớn (dù xác suất thấp, nhưng logic code phải đảm bảo không bùng nổ).
Bình luận