Hướng dẫn giải của Con số hẹn hò


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.

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, xthuyen, hstiendu1_nguyenductunglam, orz

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:

  1. Vòng lặp từ 0 đến j-1 để đếm số phần tử lớn hơn a[j] (tính u).
  2. 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.

  1. 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.
  2. 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 int cho 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ùng long long là 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

Please read the guidelines before commenting.


Không có bình luận tại thời điểm này.