Hướng dẫn giải của Con số hẹn hò
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ậpTác giả: , , ,
Editorial for ptit047: Con số hẹn hò
Hiểu bài toán
Bài toán yêu cầu tìm một số 'siêu đẹp' trong mảng. Một số a_j được gọi là 'siêu đẹp' nếu nó có một cặp số (u, v) dương (tức là u > 0 và v > 0) được tính dựa trên vị trí của nó:
- u là số lượng các số đứng trước aj (i < j) có giá trị lớn hơn aj.
- v là số lượng các số đứng sau aj (k > j) có giá trị nhỏ hơn aj. Giá trị p được định nghĩa là tích của u và v (p = u * v). Mục tiêu là tìm số a_j có giá trị p = u * v lớn nhất. Nếu có nhiều số cùng có giá trị p lớn nhất, chọn số xuất hiện đầu tiên. Nếu không tìm thấy số nào thỏa mãn (tức là không có u, v nào dương), in ra thông báo buồn.
Các cách tiếp cận
Cách Brute Force
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
// Hàm tính tổng các ước của n
long long sum_divisors(long long n) {
long long sum = 0;
for (long long i = 1; i * i <= n; ++i) {
if (n % i == 0) {
sum += i;
if (n / i != i) {
sum += n / i;
}
}
}
return sum;
}
int main() {
int n;
cin >> n;
vector<long long> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
long long max_p_sum = -1;
long long result_val = -1;
// Duyệt qua mỗi phần tử để tính u và v
for (int j = 0; j < n; ++j) {
long long u = 0;
long long v = 0;
// Tính u: số lượng phần tử trước j có giá trị > a[j]
for (int i = 0; i < j; ++i) {
if (a[i] > a[j]) {
u++;
}
}
// Tính v: số lượng phần tử sau j có giá trị < a[j]
for (int k = j + 1; k < n; ++k) {
if (a[k] < a[j]) {
v++;
}
}
// Chỉ xét nếu cả u và v đều dương
if (u > 0 && v > 0) {
long long p = u * v;
long long current_p_sum = sum_divisors(p);
if (current_p_sum > max_p_sum) {
max_p_sum = current_p_sum;
result_val = a[j];
}
}
}
if (result_val == -1) {
cout << "Neu khong co Thuong, Tai se buon biet may :(." << endl;
} else {
cout << max_p_sum << " " << result_val << endl;
}
return 0;
}
- Time Complexity: O(n^2 * sqrt(UV)) (n ~ 10^4, UV có thể lớn)
- Space Complexity: O(n)
Đây là cách tiếp cận trực tiếp nhất. Chúng ta duyệt qua từng phần tử a[j] trong mảng. Với mỗi a[j], chúng ta dùng hai vòng lặp lồng nhau để đếm:
- Vòng lặp từ 0 đến j-1 để đếm số phần tử lớn hơn a[j] (tính u).
- Vòng lặp từ j+1 đến n-1 để đếm số phần tử nhỏ hơn a[j] (tính v). Sau đó tính p = u * v, rồi tính tổng các ước của p. So sánh với giá trị lớn nhất tìm được. Phức tạp: O(n^2) cho việc tính u, v. Với n = 10^4, n^2 = 10^8, có thể chạy được trong 1 giây nếu tối ưu tốt. Tuy nhiên, hàm tính tổng ước (sqrt(p)) nếu p lớn có thể gây chậm.
Cách Tối ưu với Phân tích Xu hướng (Inversion Count)
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
// Hàm tính tổng các ước của n
long long sum_divisors(long long n) {
long long sum = 0;
for (long long i = 1; i * i <= n; ++i) {
if (n % i == 0) {
sum += i;
if (n / i != i) {
sum += n / i;
}
}
}
return sum;
}
struct Element {
long long val;
int index;
};
// Hàm so sánh cho BIT hoặc Merge Sort
bool compareElements(const Element &a, const Element &b) {
if (a.val != b.val) return a.val < b.val;
return a.index < b.index;
}
int main() {
int n;
cin >> n;
vector<long long> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
// 1. Tính mảng U (Greater Elements Before)
// Sử dụng Fenwick Tree (BIT) hoặc Merge Sort để đếm số lượng phần tử lớn hơn ở trước
// Đơn giản hơn: Dùng set/ordered_set để đếm trong lúc duyệt
// Tuy nhiên, do giới hạn code, ta có thể dùng cách đếm trực tiếp hoặc tối ưu O(n log n)
// Ở đây minh họa cách dùng BIT cho bài toán Inversion Count (đảo ngược điều kiện)
vector<int> u_counts(n, 0);
vector<int> v_counts(n, 0);
// Tính U: Số lượng phần tử trước j > a[j]
// Ta có thể dùng Fenwick Tree sau khi chuẩn hóa giá trị
// Hoặc đơn giản là dùng multiset để đếm
{
vector<long long> temp = a;
sort(temp.begin(), temp.end());
temp.erase(unique(temp.begin(), temp.end()), temp.end());
// Fenwick Tree
vector<int> bit(n + 1, 0);
auto update = [&](int idx, int val) {
for (; idx <= n; idx += idx & -idx) bit[idx] += val;
};
auto query = [&](int idx) {
int sum = 0;
for (; idx > 0; idx -= idx & -idx) sum += bit[idx];
return sum;
};
// Duyệt từ trái sang phải
for (int i = 0; i < n; ++i) {
int pos = lower_bound(temp.begin(), temp.end(), a[i]) - temp.begin() + 1;
// Số lượng phần tử nhỏ hơn hoặc bằng hiện tại đã xuất hiện là query(pos)
// Số lượng phần tử lớn hơn hiện tại đã xuất hiện là i - query(pos)
u_counts[i] = i - query(pos);
update(pos, 1);
}
}
// Tính V: Số lượng phần tử sau j < a[j]
// Tương tự, duyệt từ phải sang trái
{
vector<long long> temp = a;
sort(temp.begin(), temp.end());
temp.erase(unique(temp.begin(), temp.end()), temp.end());
vector<int> bit(n + 1, 0);
auto update = [&](int idx, int val) {
for (; idx <= n; idx += idx & -idx) bit[idx] += val;
};
auto query = [&](int idx) {
int sum = 0;
for (; idx > 0; idx -= idx & -idx) sum += bit[idx];
return sum;
};
// Duyệt từ phải sang trái
for (int i = n - 1; i >= 0; --i) {
int pos = lower_bound(temp.begin(), temp.end(), a[i]) - temp.begin() + 1;
// Số lượng phần tử nhỏ hơn a[i] đã xuất hiện (ở bên phải) là query(pos - 1)
v_counts[i] = query(pos - 1);
update(pos, 1);
}
}
long long max_p_sum = -1;
long long result_val = -1;
for (int j = 0; j < n; ++j) {
long long u = u_counts[j];
long long v = v_counts[j];
if (u > 0 && v > 0) {
long long p = u * v;
long long current_p_sum = sum_divisors(p);
if (current_p_sum > max_p_sum) {
max_p_sum = current_p_sum;
result_val = a[j];
}
}
}
if (result_val == -1) {
cout << "Neu khong co Thuong, Tai se buon biet may :(." << endl;
} else {
cout << max_p_sum << " " << result_val << endl;
}
return 0;
}
- Time Complexity: O(n log n + n * sqrt(UV))
- Space Complexity: O(n)
Phương pháp này tách biệt việc tính toán u và v.
- Tính mảng U: Duyệt mảng từ trái qua phải. Với mỗi phần tử a[i], ta cần biết có bao nhiêu phần tử đã duyệt qua có giá trị lớn hơn a[i]. Ta có thể dùng Fenwick Tree (BIT) hoặc Merge Sort để đếm inverted pairs. Nếu dùng BIT, ta cần chuẩn hóa giá trị (coordinate compression) vì giá trị a[i] có thể lên tới 10^8.
- Tính mảng V: Tương tự, duyệt từ phải qua trái. Với mỗi a[i], đếm số phần tử ở bên phải có giá trị nhỏ hơn a[i]. Sau khi có mảng U và V, ta chỉ việc duyệt một lần để tính p = U[i] * V[i] và tìm max. Cách này tối ưu hóa việc tính u và v từ O(n^2) xuống O(n log n), phù hợp với n lớn.
Phân tích độ phức tạp
| Cách tiếp cận | Time | Space | Tên |
|---|---|---|---|
| 1 | O(n^2 * sqrt(UV)) (n ~ 10^4, UV có thể lớn) | O(n) | Brute Force |
| 2 | O(n log n + n * sqrt(UV)) | O(n) | Tối ưu với Phân tích Xu hướng (Inversion Count) |
Bài học kinh nghiệm
- Bài toán chia làm 2 phần chính: Tính số lượng (u, v) và Tính tổng ước (divisor sum).
- Giá trị p = u * v có thể rất lớn (lên tới ~2.5 * 10^7 nếu n=10^4), nhưng hàm tính tổng ước của p chạy trong thời gian chấp nhận được nếu tối ưu vòng lặp sqrt(p).
- Nếu chỉ quan tâm đến tổng ước lớn nhất, ta có thể tối ưu việc tính tổng ước bằng cách nhận thấy rằng nếu p1 chia hết cho p2 thì sum_divisors(p1) thường (nhưng không luôn luôn) lớn hơn. Tuy nhiên, phương pháp chuẩn là tính trực tiếp.
Lỗi thường gặp
- Quên kiểm tra điều kiện u > 0 và v > 0 trước khi tính p.
- Sử dụng biến kiểu
intcho u, v, p hoặc tổng ước có thể gây tràn số (overflow) khi n lớn (ví dụ n=10^4, u*v có thể lên tới 25 triệu, nằm trong giới hạn int nhưng tổng ước có thể lớn hơn, nên dùnglong longlà an toàn nhất). - Trong phương pháp Brute Force, độ phức tạp O(n^2) có thể quá chậm nếu n = 10^4 và ngôn ngữ/cpp chạy không tối ưu, nhưng thực tế trong contest Việt Nam (n=10^4) thì O(n^2) ~ 10^8 thao tác thường qua được nếu code gọn.
- Lỗi logic khi tính v: Phải đếm số phần tử sau j có giá trị < a[j], không phải >.
Bình luận