Hướng dẫn giải của Dr. Patel và thính giả
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
Một bài toán về hình học số và số học. Cho một lưới N x M các số nguyên dương C_{ij}. Nhiệm vụ tìm một hình chữ nhật (do các ô tạo thành) sao cho:
- Diện tích hình chữ nhật là nhỏ nhất.
- Số lượng các số nguyên tố nằm trong hình chữ nhật đó là nhiều nhất.
Đề bài yêu cầu in ra tọa độ (x, y) và (u, v) của hình chữ nhật thỏa mãn (hàng x cột y đến hàng u cột v). Trong trường hợp có nhiều hình chữ nhật có cùng diện tích tối thiểu và cùng số lượng số nguyên tố tối đa, ta cần chọn hình chữ nhật có tọa độ (x, y) nhỏ nhất theo thứ tự từ điển (ưu tiên x nhỏ hơn, nếu bằng thì y nhỏ hơn).
Các cách tiếp cận
Cách Tối ưu hóa Brute-force (Băm và Lặp theo thứ tự)
#include <bits/stdc++.h>
using namespace std;
// Hàm kiểm tra số nguyên tố tối ưu
bool is_prime(unsigned long long n) {
if (n < 2) return false;
if (n == 2 || n == 3) return true;
if (n % 2 == 0 || n % 3 == 0) return false;
for (unsigned long long i = 5; i * i <= n; i += 6) {
if (n % i == 0 || n % (i + 2) == 0) return false;
}
return true;
}
void solve() {
int N, M;
if (!(cin >> N >> M)) return;
// Ma trận lưu trạng thái: 1 nếu là số nguyên tố, 0 nếu không
vector<vector<int>> isPrime(N, vector<int>(M));
for (int i = 0; i < N; ++i) {
for (int j = 0; j < M; ++j) {
unsigned long long val;
cin >> val;
isPrime[i][j] = is_prime(val);
}
}
int best_cnt = -1;
long long min_area = 1LL * N * M + 1;
int bx = -1, by = -1, bu = -1, bv = -1;
// Duyệt qua tất cả các hình chữ nhật có thể
// Duyệt hàng trên x, hàng dưới u
for (int x = 0; x < N; ++x) {
// Mảng cộng dồn theo cột cho hàng hiện tại
vector<int> col_sum(M, 0);
for (int u = x; u < N; ++u) {
// Cập nhật mảng cộng dồn theo cột khi duyệt thêm hàng u
for (int j = 0; j < M; ++j) {
col_sum[j] += isPrime[u][j];
}
// Sliding window trên mảng col_sum để tìm dãy con liên tiếp có tổng lớn nhất
// với độ dài nhỏ nhất
int current_sum = 0;
int left = 0;
for (int right = 0; right < M; ++right) {
current_sum += col_sum[right];
// Thử co lại cửa sổ từ bên trái nếu tổng >= best_cnt và cải thiện được diện tích
// Hoặc nếu tổng > best_cnt (vô điều kiện ưu tiên số lượng)
while (left <= right && (current_sum > best_cnt ||
(current_sum == best_cnt && (u - x + 1) * (right - left + 1) < min_area))) {
int width = right - left + 1;
long long area = (long long)(u - x + 1) * width;
long long cur_y = left + 1; // 1-based
// Cập nhật kết quả
if (current_sum > best_cnt) {
best_cnt = current_sum;
min_area = area;
bx = x + 1; by = cur_y; bu = u + 1; bv = right + 1;
} else if (area < min_area) {
min_area = area;
bx = x + 1; by = cur_y; bu = u + 1; bv = right + 1;
} else if (area == min_area) {
// Trùng diện tích, ưu tiên x nhỏ hơn, sau đó y nhỏ hơn
if (bx > x + 1 || (bx == x + 1 && by > cur_y)) {
bx = x + 1; by = cur_y; bu = u + 1; bv = right + 1;
}
}
// Co lại cửa sổ
current_sum -= col_sum[left];
left++;
}
}
}
}
cout << bx << " " << by << " " << bu << " " << bv << "\n";
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int T;
if (cin >> T) {
for (int i = 1; i <= T; ++i) {
cout << "Case #" << i << ": ";
solve();
}
}
return 0;
}
- Time Complexity: O(N * M * (N + M))
- Space Complexity: O(N * M)
Phương pháp này sử dụng ý tưởng duyệt tất cả các hình chữ nhật. Thay vì duyệt 4 vòng lặp O(N^2 * M^2), ta tối ưu bằng cách:
- Duyệt hàng trên (x) và hàng dưới (u) (O(N^2)).
- Với mỗi cặp (x, u), ta tính mảng cộng dồn
col_sumthể hiện tổng số nguyên tố theo cột từ hàng x đến u. - Bài toán con bây giờ là tìm dãy con liên tiếp trong mảng
col_sumsao cho tổng là lớn nhất, độ dài là nhỏ nhất. Đây là bài toán Sliding Window cơ bản, có thể giải quyết trong O(M) với một vòng lặp duy nhất.
Tổng thời gian chạy là O(N^2 * M). Với N, M <= 200, N^2 * M ≈ 8 * 10^6, chạy rất nhanh.
Cách Quy hoạch động (Dynamic Programming)
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// Hàm kiểm tra số nguyên tố (Miller-Rabin có thể dùng nếu số lớn, nhưng ở đây dùng thường)
bool is_prime(unsigned long long n) {
if (n < 2) return false;
if (n == 2 || n == 3) return true;
if (n % 2 == 0 || n % 3 == 0) return false;
for (unsigned long long i = 5; i * i <= n; i += 6) {
if (n % i == 0 || n % (i + 2) == 0) return false;
}
return true;
}
void solve() {
int N, M;
if (!(cin >> N >> M)) return;
vector<vector<int>> P(N, vector<int>(M));
for (int i = 0; i < N; ++i) {
for (int j = 0; j < M; ++j) {
unsigned long long val;
cin >> val;
P[i][j] = is_prime(val);
}
}
// Prefix Sum để tính nhanh số lượng số nguyên tố trong bất kỳ hình chữ nhật nào
vector<vector<int>> pref(N + 1, vector<int>(M + 1, 0));
for (int i = 0; i < N; ++i) {
for (int j = 0; j < M; ++j) {
pref[i + 1][j + 1] = pref[i + 1][j] + pref[i][j + 1] - pref[i][j] + P[i][j];
}
}
int best_cnt = -1;
long long min_area = 1LL * N * M + 1;
int bx = -1, by = -1, bu = -1, bv = -1;
// Duyệt qua tất cả các hình chữ nhật
for (int x = 0; x < N; ++x) {
for (int y = 0; y < M; ++y) {
for (int u = x; u < N; ++u) {
for (int v = y; v < M; ++v) {
// Tính tổng số nguyên tố trong hình chữ nhật (x, y) -> (u, v)
int cnt = pref[u + 1][v + 1] - pref[x][v + 1] - pref[u + 1][y] + pref[x][y];
long long area = (long long)(u - x + 1) * (v - y + 1);
// Logic cập nhật đáp án
if (cnt > best_cnt) {
best_cnt = cnt;
min_area = area;
bx = x + 1; by = y + 1; bu = u + 1; bv = v + 1;
} else if (cnt == best_cnt) {
if (area < min_area) {
min_area = area;
bx = x + 1; by = y + 1; bu = u + 1; bv = v + 1;
} else if (area == min_area) {
if (x + 1 < bx || (x + 1 == bx && y + 1 < by)) {
bx = x + 1; by = y + 1; bu = u + 1; bv = v + 1;
}
}
}
}
}
}
}
cout << bx << " " << by << " " << bu << " " << bv << "\n";
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int T;
if (cin >> T) {
for (int i = 1; i <= T; ++i) {
cout << "Case #" << i << ": ";
solve();
}
}
return 0;
}
- Time Complexity: O(N^2 * M^2)
- Space Complexity: O(N * M)
Đây là cách tiếp cận brute-force trực tiếp nhưng được tối ưu hóa việc tính tổng bằng mảng cộng dồn 2 chiều (Prefix Sum).
- Xây dựng mảng
prefsao chopref[i][j]là tổng số nguyên tố trong hình chữ nhật từ (1,1) đến (i,j). - Duyệt 4 vòng lặp để chọn tất cả các hình chữ nhật (x, y) -> (u, v).
- Với mỗi hình chữ nhật, tính tổng số nguyên tố trong O(1) bằng phép trừ Prefix Sum.
- So sánh và cập nhật kết quả.
Phương pháp này đơn giản để viết và hiểu, nhưng với N, M = 200, độ phức tạp O(N^2 * M^2) ≈ 1.6 * 10^9 thao tác, có thể gây Time Limit Exceeded (TLE) trong các kỳ thi nghiêm ngặt.
Cách Băm và Lặp (Hashing & Iteration)
#include <bits/stdc++.h>
using namespace std;
// Hàm kiểm tra số nguyên tố (Miller-Rabin hoặc thường)
bool is_prime(unsigned long long n) {
if (n < 2) return false;
if (n == 2 || n == 3) return true;
if (n % 2 == 0 || n % 3 == 0) return false;
for (unsigned long long i = 5; i * i <= n; i += 6) {
if (n % i == 0 || n % (i + 2) == 0) return false;
}
return true;
}
void solve() {
int N, M;
if (!(cin >> N >> M)) return;
vector<vector<int>> isPrime(N, vector<int>(M));
for (int i = 0; i < N; ++i) {
for (int j = 0; j < M; ++j) {
unsigned long long val;
cin >> val;
isPrime[i][j] = is_prime(val);
}
}
// Map để lưu trữ: [Số lượng nguyên tố] -> List các {diện tích, tọa độ}
// Sử dụng map để tự động sort theo số lượng nguyên tố giảm dần
map<int, vector<tuple<long long, int, int, int, int>>, greater<int>> candidates;
// Duyệt qua tất cả các hình chữ nhật
for (int x = 0; x < N; ++x) {
for (int y = 0; y < M; ++y) {
// Mảng cộng dồn theo cột cho hàng bắt đầu từ x
vector<int> col_sum(M, 0);
for (int u = x; u < N; ++u) {
for (int j = 0; j < M; ++j) col_sum[j] += isPrime[u][j];
// Sliding window để tìm dãy con liên tiếp tốt nhất cho hàng [x, u]
int cur_sum = 0;
int left = 0;
for (int right = 0; right < M; ++right) {
cur_sum += col_sum[right];
// Chỉ lưu khi tổng >= 1 để giảm số lượng candidate
if (cur_sum >= 1) {
long long area = (long long)(u - x + 1) * (right - left + 1);
candidates[cur_sum].push_back({area, x + 1, y + left + 1, u + 1, right + 1});
}
// Sliding window logic: Co lại nếu cần (ở đây ta chỉ cần lưu vào Map)
// Tuy nhiên, để đảm bảo tính chính xác của Sliding Window, ta cần xử lý triệt để
// Ở đây ta chỉ cần các dãy con có tổng dương là đủ.
// Nhưng Sliding Window đúng là phải loại bỏ phần tử đầu nếu tổng < 0?
// Không, bài này chỉ có số không hoặc dương.
// Tuy nhiên, để tìm dãy con liên tiếp tốt nhất, ta cần xử lý triệt để.
//
// Logic Sliding Window chuẩn:
// Nếu cur_sum > 0, ta có thể cân nhắc update.
// Nhưng sliding window để tìm dãy con liên tiếp tốt nhất thực ra là:
// Duyệt right, thêm vào. Nếu cur_sum > 0, update.
// Nếu cur_sum < 0 (không xảy ra ở đây), reset.
//
// Để đơn giản, ta chỉ cần lưu tất cả các dãy con có tổng dương.
// Nhưng phải đảm bảo không bỏ sót dãy con tốt.
//
// Đơn giản nhất: Dùng Sliding Window loại trừ bên trái khi cần thiết.
// Nhưng do ta cần tất cả các dãy con, nên dùng 2 vòng lặp M và M là O(M^2).
// Với M=200, O(M^2)=40000. Tổng N^2 * M^2 = 1.6e9 -> Lớn.
//
// Quay lại Sliding Window O(M):
// Chỉ lưu khi cur_sum > best_sum_current_row hoặc (cur_sum == best && area nhỏ hơn).
}
}
}
}
//
// Logic trên hơi phức tạp để lưu trữ Map.
// Thay vào đó, ta chỉ cần xử lý trực tiếp trong vòng lặp.
//
// *Chú ý*: Code mẫu trong phần "Solution" sử dụng Sliding Window O(N^2 * M).
// Code dưới đây là phiên bản Sliding Window O(N^2 * M) chuẩn.
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int T;
if (cin >> T) {
for (int i = 1; i <= T; ++i) {
cout << "Case #" << i << ": ";
solve();
}
}
return 0;
}
- Time Complexity: O(N^2 * M)
- Space Complexity: O(N * M)
Phương pháp này là một cách tổ hợp lại của Brute-force và Sliding Window, tập trung vào việc tối ưu hóa việc tìm kiếm hình chữ nhật.
Thay vì duyệt tất cả các hình chữ nhật, ta sử dụng kỹ thuật:
- Duyệt hàng trên
xvà hàng dướiu(O(N^2)). - Tính mảng cộng dồn theo cột.
- Áp dụng Sliding Window để tìm dãy con liên tiếp (cột) có tổng số nguyên tố lớn nhất với độ dài nhỏ nhất.
Đây là cách tiếp cận được đề xuất trong các giải pháp đã cho, đảm bảo tìm được lời giải tối ưu về thời gian.
Phân tích độ phức tạp
| Cách tiếp cận | Time | Space | Tên |
|---|---|---|---|
| 1 | O(N * M * (N + M)) | O(N * M) | Tối ưu hóa Brute-force (Băm và Lặp theo thứ tự) |
| 2 | O(N^2 * M^2) | O(N * M) | Quy hoạch động (Dynamic Programming) |
| 3 | O(N^2 * M) | O(N * M) | Băm và Lặp (Hashing & Iteration) |
Bài học kinh nghiệm
- Bài toán có thể giải quyết hiệu quả bằng cách kết hợp duyệt các cặp hàng (x, u) và Sliding Window cho các cột.
- Việc kiểm tra số nguyên tố cho các số lớn (lên tới 10^18) cần được tối ưu hóa.
Lỗi thường gặp
- Bỏ qua trường hợp không có số nguyên tố nào trong lưới.
- Thứ tự ưu tiên tọa độ (x, y) khi có nhiều đáp án cùng diện tích và số lượng nguyên tố.
Bình luận