Hướng dẫn cho Nhà toán học Italien

Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.

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.

Authors: SPyofgame

\(\color{red}{\text{Spoiler Alert}_{{}_{{}^{{}^{v2.0}}}}}\)

\(\color{red}{\text{Khuyến khích bạn đọc trước khi đọc phần lời giải xin hãy thử code ra thuật của mình dù nó có sai hay đúng}}\)

\(\color{red}{\text{Sau đó từ phần bài giải và thuật toán trước đó mà đối chiếu, rút nhận xét với thuật của mình và thu được bài học (không lãng phí thời gian đâu).}}\)

\(\color{orange}{\text{Hint 1 <Brute-force>}}\)

Thử từng bộ 3 số và tăng biến đếm \(res\) nếu bộ đó thỏa mãn
Duyệt từng bộ 3 số và tăng biến đếm \(total\) nếu bộ đó thỏa mãn
Kết quả bài toán là \(\frac{res}{total}\)

\(\color{green}{\text{Preference TLE Code }}\): Brute-force

\(^{^{\color{purple}{\text{Complexity : }} O(n^3)\ \color{purple}{\text{time}}\ ||\ O(n)\ \color{purple}{\text{memory}}}}\)

C++

int main()
{
    int n;
    cin >> n;

    vector<int> a(n + 2);
    for (int i = 1; i <= n; ++i)
        cin >> a[i];

    ll res = 0, total = 0;
    for (int i = 1; i <= n ; ++i)
    {
        for (int j = 1; j <= n; ++j)
        {
            for (int k = 1; k <= n; ++k)
            {
                if (i < j && j < k)
                {
                    res += (a[i] > a[j]) && (a[j] < a[k]); /// bo ba so nay thoa man
                    total++;
                }
            }
        }
    }

    cout << setprecision(6) << fixed << double(res) / total;
    return 0;
}

\(\color{orange}{\text{Hint 2 <Branch-and-bound> <Math>}}\)

Nhận xét rằng \(total = \binom{n}{3} = \frac{n \times (n - 1) \times (n - 2)}{6}\) là số cách chọn bộ \(3\) số trong \(n\) số

Số đầu tiên được chọn có \(n\) cách chọn

Số thứ hai được chọn có \(n - 1\) cách chọn khác số đầu

Số thứ ba được chọn có \(n - 2\) cách chọn khác hai số đầu

Các hoán vị cặp 3 số \((p_1, p_2, p_3)\) là \(S = \{\{p_1, p_2, p_3\}, \{p_1, p_3, p_2\}, \{p_2, p_1, p_3\}, \{p_2, p_3, p_1\}, \{p_3, p_1, p_2\}, \{p_3, p_2, p_1\}\}\)

Nhưng vì thứ tự có quan trọng nên phải cho cho số hoán vị của cặp 3 số là \(|S| = 6\)

Vậy số cách chọn là \(\frac{n \times (n - 1) \times (n - 2)}{6} = \binom{n}{3}\)

Khi ta duyệt ta có thể không cần xét các trường hợp không cần thiết

\(\color{green}{\text{Preference TLE Code }}\): Branch-and-bound, math

\(^{^{\color{purple}{\text{Complexity : }} O(n^3)\ \color{purple}{\text{time}}\ ||\ O(n)\ \color{purple}{\text{memory}}}}\)

C++

int main()
{
    int n;
    cin >> n;

    vector<int> a(n + 2);
    for (int i = 1; i <= n; ++i)
        cin >> a[i];

    ll res = 0;
    for (int i = 1; i <= n - 2; ++i)
        for (int j = i + 1; j <= n - 1; ++j)
            if (a[i] > a[j])
                for (int k = j + 1; k <= n; ++k)
                    if (a[j] < a[k]) /// bo ba so nay thoa man
                        res++; 

    ll total = 1LL * n * (n - 1) * (n - 2) / 6;
    cout << setprecision(6) << fixed << double(res) / total;
    return 0;
}

\(\color{orange}{\text{Hint 3 <Combinatorics>}}\)

Chúng ta cần đếm số bộ 3 cặp \(a[i] > a[j] < a[k]\) mà \(i < j < k\)

Gọi \([<x>]\) là hàm boolean, trả về \(1\) khi \(X\) đúng và trả về 0 khi \(X\) sai

Gọi \(Left[i] = \underset{j \in [1, i)}{\Sigma}[a[j] > a[i]]\) là số số lớn hơn \(a[i]\) nằm bên trái \(i\)

Gọi \(Right[i] = \underset{j \in (i, n]}{\Sigma}[a[j] > a[i]]\) là số số lớn hơn \(a[i]\) nằm bên phải \(i\)

Một bộ 3 số thỏa mãn là một cách chọn 2 số \(a[j], a[k]\) bất kì lớn hơn \(a_i\) thỏa \(1 \leq j < i < k \leq n\)

Số cách chọn bộ 3 số thỏa mãn tại vị trí \(i\) là \(Left[i] \times Right[i]\)

Kết quả bài toán là \(res = \underset{j \in [1, n]}{\Sigma}(Left[i] \times Right[i])\)

\(\color{green}{\text{Preference AC Code }}\): Combinatorics

\(^{^{\color{purple}{\text{Complexity : }} O(n^2)\ \color{purple}{\text{time}}\ ||\ O(n)\ \color{purple}{\text{memory}}}}\)

C++

int main()
{
    int n;
    cin >> n;

    vector<int> a(n + 2);
    for (int i = 1; i <= n; ++i)
        cin >> a[i];

    ll res = 0;
    for (int i = 2; i < n; ++i)
    {
        int left = 0;
        for (int j = 1; j < i; ++j)
            if (a[j] > a[i]) left++;

        int right = 0;
        for (int j = n; j > i; --j)
            if (a[j] > a[i]) right++;

        res += 1LL * left * right;
    }

    ll total = 1LL * n * (n - 1) * (n - 2) / 6;
    cout << setprecision(6) << fixed << double(res) / total;
    return 0;
}

\(\color{orange}{\text{Hint 4 <Data-Structure>::<Fenwick-Tree>}}\)

Nhận xét rằng việc tính \(X[i]\) là đếm số cặp nghịch thế trong mảng \(A[1 \rightarrow n]\)
Nhận xét rằng việc tính \(Y[i]\) là đếm số cặp nghịch thế trong mảng \(A[n \rightarrow 1]\)
Chúng ta sẽ sử dụng Fenwick Tree để tính \(X[i]\) và \(Y[i]\) trong \(O(n log max\_val)\) rồi duyệt trong thời gian tuyến tính để tính \(res\)
Tiếp cận bài toán

Tại số thứ \(i\), ta đếm số lượng số lớn hơn \(a_i\) và cập nhật tần số của số \(a_i\)

Việc sử dụng Fenwick Tree làm cho việc cập nhật tần số \(a_i\) mất \(O(1) \rightarrow O(log max\_val)\)

Nhưng lại giúp việc đếm số lượng số lớn hơn \(a_i\) trong \(O(n) \rightarrow O(log max\_val)\)

\(\color{green}{\text{Preference MLE Code }}\): Data-Structure::Fenwick-Tree

\(^{^{\color{purple}{\text{Complexity : }} O(n \log max\_val)\ \color{purple}{\text{time}}\ ||\ O(n)\ \color{purple}{\text{memory}}}}\)

C++

/// cau truc du lieu cay chi so nhi phan
struct fentree {
    /// one based
    int n = 0;
    vector<int> BIT;

    void init(int lim) { /// khoi tao
        n = lim;
        BIT.assign(lim + 1, 0);
    }

    void update(int p, int v) { /// tang tan so cua a[i] len
        for (; p > 0; p -= p & -p)
            BIT[p] += v;
    }

    int getValue(int p) { /// dem so luong phan tu lon hon a[i]
        int res = 0;
        for (; p <= n; p += p & -p)
            res += BIT[p];

        return res;
    }
};

int main()
{
    int n;
    cin >> n;

    vector<int> a(n + 2);
    for (int i = 1; i <= n; ++i)
        cin >> a[i];

    fentree BIT;

    BIT.init(n);
    vector<int> left(n + 2, 0);
    for (int i = 1; i <= n; ++i)
    {
        left[i] = BIT.getValue(a[i]);
        BIT.update(a[i] - 1, 1);
    }

    BIT.init(n);
    vector<int> right(n + 2);
    for (int i = n; i >= 1; --i)
    {
        right[i] = BIT.getValue(a[i]);
        BIT.update(a[i] - 1, 1);
    }

    ll res = 0;
    for (int i = 1; i <= n; ++i)
        res += 1LL * left[i] * right[i];

    ll total = 1LL * n * (n - 1) * (n - 2) / 6;
    cout << setprecision(6) << fixed << double(res) / total;
    return 0;
}

\(\color{orange}{\text{Hint 5 <Value Compression>}}\)

Tuy nhiên \(max\_value = max(a_i) = 10^9\) nên không thể làm trực tiếp trong \(\color{orange}{\text{Hint 4}}\)
Nhận xét rằng chúng ta chỉ dùng phép so sánh giá trị \(a[x] > a[y]\) nào đó chứ không quan tâm giá trị của nó

Gọi mảng \(b[]\) đã được sắp xêp chỉ gồm các giá trị phân biệt của \(a[]\)

Gọi số ta đang xét là \(b[y]\)

Có \(b[y - 1] < b[y] < b[y + 1]\) hay số lớn nhất nhỏ hơn \(b[y]\) là \(b[y - 1]\), số nhỏ nhất lớn hơn \(b[y]\) là \(b[y + 1]\)

Nếu ta đổi giá trị \(b[y] \rightarrow x \in b[y - 1] + 1 .. b[y + 1] - 1\) thì (\(b[y - 1] < b[y] < b[y + 1]\)) vẫn không thay đổi

Số lượng phần tử phân biệt tối đa trong mảng là \(n\) và \(max(n) < max(a_i)\)

Từ nhận xét này ta sẽ nén mảng thành các giá trị \(1..k\) với \(k\) là số lượng phần tử phân biệt trong mảng

Các số \(a[i] = a[j]\) sẽ cùng giá trị nén, các số bé hơn sẽ có giá trị nén bé hơn và tương tự với các số lớn hơn

\(\color{green}{\text{Preference AC Code }}\): Data-Structure::Fenwick-Tree, Value COmpression

\(^{^{\color{purple}{\text{Complexity : }} O(n \log n)\ \color{purple}{\text{time}}\ ||\ O(n)\ \color{purple}{\text{memory}}}}\)

C++

/// cau truc du lieu cay chi so nhi phan
struct fentree {
    /// one based
    int n = 0;
    vector<int> BIT;

    void init(int lim) { /// khoi tao
        n = lim;
        BIT.assign(lim + 1, 0);
    }

    void update(int p, int v) { /// tang tan so cua a[i] len
        for (; p > 0; p -= p & -p)
            BIT[p] += v;
    }

    int getValue(int p) { /// dem so luong phan tu lon hon a[i]
        int res = 0;
        for (; p <= n; p += p & -p)
            res += BIT[p];

        return res;
    }
};

int main()
{
    int n;
    cin >> n;

    set<int> S;
    vector<int> a(n + 2);
    for (int i = 1; i <= n; ++i)
    {
        cin >> a[i];
        S.insert(a[i]); /// tap hop cac phan tu phan biet duoc sap xep tang dan, k = S.size
    }

    hashmap<int, int> M; /// mang nen: x -> M[x] la gia tri nen
    int order = 1;
    for (int x : S) M[x] = order++; /// tao cac gia tri nen moi [1..k]
    for (int i = 1; i <= n; ++i)
        a[i] = M[a[i]]; /// nen mang

    fentree BIT;

    BIT.init(n);
    vector<int> left(n + 2, 0);
    for (int i = 1; i <= n; ++i)
    {
        left[i] = BIT.getValue(a[i]);
        BIT.update(a[i] - 1, 1);
    }

    BIT.init(n);
    vector<int> right(n + 2);
    for (int i = n; i >= 1; --i)
    {
        right[i] = BIT.getValue(a[i]);
        BIT.update(a[i] - 1, 1);
    }

    ll res = 0;
    for (int i = 1; i <= n; ++i)
        res += 1LL * left[i] * right[i];

    ll total = 1LL * n * (n - 1) * (n - 2) / 6;
    cout << setprecision(6) << fixed << double(res) / total;
    return 0;
}

\(\color{orange}{\text{Hint 6 <Dynamic-programming> <Online Solving>}}\)

Gọi \(f[i][k]\) là số lượng bộ \(k \in [1, 3]\) số thỏa mãn \(a_{p_1} > a_{p_2} < a_{p_3}\) tính tới \(i\)

VỚi \(k = 1\) thì \(f[i][1] = 1\) là bộ \(\{a_{p_1}\}\)

Với \(k = 2\) thì \(f[i][2] = \underset{j \in [1, i)}{\Sigma}([a[j] > a[i]] * f[j][1])\) là số bộ \(\{a_{p_1}\ > a_{p_2}\}\)

Với \(k = 3\) thì \(f[i][3] = \underset{j \in [1, i)}{\Sigma}([a[j] < a[i]] * f[j][2])\) là số bộ \(\{a_{p_1}\ > a_{p_2}\ < a_{p_3}\}\)

Kết quả cần tìm là \(res = \underset{i \in [1, n]}{\Sigma}(f[i][3])\)

\(\color{green}{\text{Preference AC Code }}\): Dynamic-programming::DP_count, Online Solving

\(^{^{\color{purple}{\text{Complexity : }} O(n ^ 2)\ \color{purple}{\text{time}}\ ||\ O(n)\ \color{purple}{\text{memory}}}}\)

C++

int main()
{
    int n;
    cin >> n;

    vector<int> a(n + 2);
    for (int i = 1; i <= n; ++i)
        cin >> a[i];

    ll res = 0;
    vector<vector<ll> > f(n + 1, vector<ll>(4, 0));
    for (int i = 1; i <= n; ++i)
    {
        f[i][1] = 1;

        for (int j = 1; j < i; ++j)
            if (a[j] > a[i])
                f[i][2] += f[j][1];

        for (int j = 1; j < i; ++j)
            if (a[j] < a[i])
                f[i][3] += f[j][2]; 

        res += f[i][3];
    }

    ll total = 1LL * n * (n - 1) * (n - 2) / 6;
    cout << setprecision(6) << fixed << double(res) / total;
    return 0;
}

\(\color{orange}{\text{Hint 7 <Data-Structure>::<Fenwick-Tree> <Dynamic-programming> <Online Solving>}}\)

Tương tự như \(\color{orange}{\text{Hint 5}}\) nhưng mình làm cả 2 chiều

\(\color{green}{\text{Preference AC Code }}\): Data-Structure::Fenwick-Tree, Dynamic-programming::DP_count, Online Solving

\(^{^{\color{purple}{\text{Complexity : }} O(n \log n)\ \color{purple}{\text{time}}\ ||\ O(n)\ \color{purple}{\text{memory}}}}\)

C++

struct fentree {
    /// one based
    int n = 0;
    vector<ll> BIT;

    void init(int lim, int val = 0) {
        n = lim;
        BIT.assign(lim + 1, val);
    }

    void update_head(int p, int v) {
        for (; p > 0; p -= p & -p)
            BIT[p] += v;
    }

    void update_tail(int p, int v) {
        for (; p <= n; p += p & -p)
            BIT[p] += v;
    }

    ll getValue_head(int p) {
        ll res = 0;
        for (; p > 0; p -= p & -p)
            res += BIT[p];

        return res;
    }

    ll getValue_tail(int p) {
        ll res = 0;
        for (; p <= n; p += p & -p)
            res += BIT[p];

        return res;
    }
};

int main()
{
    int n;
    cin >> n;

    set<int> S;
    vector<int> a(n + 2);
    for (int i = 1; i <= n; ++i)
    {
        getUnsign(a[i]);
        S.insert(a[i]);
    }

    hashmap<int, int> M;
    int order = 1;
    for (int x : S) M[x] = order++;
    for (int i = 1; i <= n; ++i)
        a[i] = M[a[i]];

    fentree f1, f2, f3;
    f1.init(n, 0);
    f2.init(n, 0);
    f3.init(n, 0);

    ll res = 0;
    vector<vector<ll> > f(n + 1, vector<ll>(4, 0));
    for (int i = n; i >= 1; --i)
    {
        f[i][1] = 1;
        f[i][2] = f2.getValue_tail(a[i]);
        f2.update_head(a[i] - 1, f[i][1]);
        f[i][3] = f3.getValue_head(a[i]);
        f3.update_tail(a[i] + 1, f[i][2]);
        res += f[i][3];
    }

    ll total = 1LL * n * (n - 1) * (n - 2) / 6;
    cout << setprecision(6) << fixed << double(res) / total;
    return 0;
}

Bình luận

2

SPyofgame 6:51 p.m. 24 Tháng 7, 2020

Khoong biết có chỗ nào mình giải thích chưa kĩ thì các bạn cứ mạnh dạn comment mình trả lời nhé

0

hongquanyl1 10:59 p.m. 3 Tháng 9, 2021

Thuật toán chính xác nhật là thuật toán nào thế anh SPyofgame. (em mới lớp 😎