Trúc (2023HITOPENDAY_3)

Nguồn: HAUI OJ – HIT Open Day 2023 Độ khó: Trung bình Ordered Set Đếm Tìm kiếm nhị phân

Đề bài

TRÚC (mã bài 2023HITOPENDAY_3) – Input: standard input · Output: standard output · Giới hạn thời gian: 1 giây · Giới hạn bộ nhớ: 256 megabytes.

Khi tìm mua bức tranh "Trúc", Cương biết rằng trên thế giới có rất nhiều chuyên gia vẽ loại tranh này. Mỗi chuyên gia vẽ "Trúc" lại vẽ cây trúc có số "đốt" khác nhau.

Vậy là Cương đã mời về $n$ chuyên gia vẽ "Trúc", họ vẽ số đốt trúc lần lượt từ $1$ đến $n$, chuyên gia thứ $i$ vẽ tranh có số đốt trúc là $i$. Cương sẽ chọn ra người vẽ đẹp nhất và mua tranh của họ.

Anh chàng không hề biết luật ngầm trong giới vẽ "Trúc". Người nào càng vẽ được nhiều đốt lại càng giỏi.

Cương sẽ xem tranh của họ theo thứ tự nhất định. Sau khi được xem tranh, Cương sẽ cho chuyên gia đó ra về. Anh sẽ liên lạc lại họ sau nếu tranh họ đủ đẹp.

Nhưng trước khi ra về, mỗi chuyên gia, để thể hiện sự kính trọng, họ sẽ đi bắt tay với tất cả những chuyên gia giỏi hơn mình còn ở trong phòng, mỗi người một lượt. (Tội nghiệp người cuối cùng chắc chắn sẽ chẳng còn ai để bắt tay)

Thấy việc bắt tay của các chuyên gia khá hay ho — mặc dù không hiểu gì, Cương có đếm lại số lượt bắt tay của họ nhưng đôi lúc vì thấy tranh đẹp quá nên anh mải đếm. Hãy giúp Cương tính xem có chính xác bao nhiêu lượt bắt tay nhé.

Input:

• Dòng đầu tiên là 1 số $n$ — số chuyên gia Cương mời đến. $(n \le 2 \cdot 10^5)$
• Dòng thứ hai gồm $n$ số nguyên dương $a_i$ — thể hiện thứ tự xem tranh của Cương. Dữ liệu đảm bảo dãy đầu vào là hoán vị của các số nguyên từ $1$ đến $n$.

Output: Một dòng duy nhất là số lượt bắt tay sau buổi họp hôm đó.

Subtask:

• 30% điểm với thứ tự ra của các chuyên gia từ bé đến lớn.
• 40% điểm với số lượng chuyên gia trong phòng không quá $1000$.
• 30% điểm không giới hạn gì thêm.

Ví dụ – standard input

5
3 4 2 1 5

Ví dụ – standard output

5

Giải thích test (của đề):

• Người đầu tiên ra khỏi phòng là chuyên gia 3, anh bắt tay với chuyên gia 4, 5.
• Người tiếp theo ra khỏi phòng là chuyên gia 4, anh bắt tay với chuyên gia 5.
• Người tiếp theo ra khỏi phòng là chuyên gia 2, anh bắt tay với chuyên gia 5.
• Người tiếp theo ra khỏi phòng là chuyên gia 1, anh bắt tay với chuyên gia 5.
• Người cuối cùng ra khỏi phòng là chuyên gia 5, anh chẳng còn ai để bắt tay.

Tổng số lượt bắt tay là $5$.

Lời mở đầu

Bài này mình được một em học viên hỏi và mình đã hướng dẫn chi tiết cách thức giải quyết cho em ấy. Tin rằng sẽ có giá trị với nhiều bạn nên mình viết lại toàn bộ hướng dẫn thành bài giải chi tiết để bạn nào chưa giải được thì có thể tham khảo nhen. Hy vọng mang đến được giá trị cho các bạn 😇.

Đề bài dông dài quá nhỉ 😅. Tóm lại là: người ra về thứ $i$ là chuyên gia $a_i$, những người còn trong phòng lúc đó chính là những người ra về sau anh, tức là $a_{i+1}, a_{i+2}, \ldots, a_n$. Anh bắt tay với những ai giỏi hơn, tức là có số lớn hơn. Vậy:

Đề bài thực chất là

Với mỗi $a_i$, đếm xem có bao nhiêu phần tử bên phải nó mà lớn hơn nó, rồi cộng tổng lại thì ra kết quả bài toán.

Như test ví dụ $3\ 4\ 2\ 1\ 5$:

• Xét số $3$, bên phải nó có 2 số lớn hơn nó ($4, 5$) ⇒ sum $= 2$.
• Xét số $4$, bên phải nó có 1 số lớn hơn nó ($5$) ⇒ sum $= 3$.
• Xét số $2$, bên phải nó có 1 số lớn hơn nó ($5$) ⇒ sum $= 4$.
• Xét số $1$, bên phải nó có 1 số lớn hơn nó ($5$) ⇒ sum $= 5$.
• Xét số $5$, bên phải nó không còn số nào cả ⇒ sum vẫn là $5$.

Kết quả in ra $5$. (Các bạn để ý: subtask 1 thứ tự ra là $1, 2, \ldots, n$ thì ai cũng bắt tay với tất cả người còn lại, đáp án chính là $\dfrac{n(n-1)}{2}$.)

Link nộp bài

Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.

Nộp bài trên CLUE OJ

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Cách 12 vòng lặp · O(N²) · 70%Cách 2Ordered Set · O(N·logN) · 100%

Cách 1Hai vòng lặp lồng nhau – O(N²)

Cách làm cơ bản nhất là 2 vòng lặp lồng nhau. Vòng lặp cha xét từng $a_i$, vòng lặp con xét tất cả các phần tử bên phải $a_i$ để thống kê xem có bao nhiêu số $\gt a_i$ để cộng vào sum.

Source code để các bạn tham khảo nếu làm theo hướng này:

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    int a[n];
    for(int i = 0; i < n; ++i){
        cin >> a[i];
    }
    long long sum = 0;
    for(int i = 0; i < n; ++i){
        for(int j = i + 1; j < n; ++j){
            if(a[j] > a[i]){
                sum++;
            }
        }
    }
    cout << sum;
    return 0;
}

import sys

def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    a = list(map(int, data[1:1 + n]))
    total = 0
    for i in range(n):
        for j in range(i + 1, n):
            if a[j] > a[i]:
                total += 1
    print(total)

main()

C++▶ Chạy tay từng dòng codeCách 1: với mỗi i, duyệt hết j > i và đếm a[j] > a[i].

Dữ liệu vào (stdin) – sửa thoải mái5 3 4 2 1 5

Dữ liệu mẫu:

1#include <bits/stdc++.h>

2using namespace std;

3

4int main(){

5 ios::sync_with_stdio(0);

6 cin.tie(0);

7 cout.tie(0);

8 int n;

9 cin >> n;

10 int a[n];

11 for(int i = 0; i < n; ++i){

12 cin >> a[i];

13 }

14 long long sum = 0;

15 for(int i = 0; i < n; ++i){

16 for(int j = i + 1; j < n; ++j){

17 if(a[j] > a[i]){

18 sum++;

19 }

20 }

21 }

22 cout << sum;

23 return 0;

24}

ChậmVừaNhanhRất nhanh

Đánh giá độ phức tạp của cách làm này:

• Không gian: mảng $a$ ⇒ $O(N)$.
• Thời gian: 2 vòng lặp lồng nhau ⇒ $O(N^2)$. Bài Trúc này cho 1 giây, mà $N$ tối đa $2 \cdot 10^5$ thì $(2 \cdot 10^5)^2 = 4 \cdot 10^{10}$, đã vượt quá $10^8$ của 1 giây rồi.

Không gian$O(N)$

Thời gian$O(N^2)$

Chỉ ăn được 70% điểm

Với $N \le 1000$ thì $N^2 = 10^6 \lt 10^8$ nên chạy trong 1 giây ok (subtask 2, 40%). Subtask 1 (30%) tuy $N$ có thể lớn nhưng ai ra trước cũng nhỏ hơn hết những người sau, nên các bạn có thể in luôn $\dfrac{n(n-1)}{2}$ (code ở trên chưa làm phần này). Còn lại những test $N$ tới $2 \cdot 10^5$ với thứ tự lộn xộn thì $O(N^2)$ chịu không nổi đâu.

Cách 2Ordered Set (cây đỏ đen của pbds) – O(N·logN)

Các bạn nhìn nhé: với mỗi $a_i$, việc đếm trong các phần tử bên phải xem có bao nhiêu số $\gt a_i$ nếu làm theo cách vét cạn sẽ cần xét qua toàn bộ, trường hợp lớn nhất khi $a_0$ là phần tử đầu tiên thì phải xét qua toàn bộ $n - 1$ phần tử đằng sau. Vậy giờ có cách nào không cần tốn chi phí $O(N)$ cho việc xét từng $a_i$ không?

Câu trả lời là ta chỉ cần tốn $O(\log N)$ thôi. Tưởng tượng nếu các phần tử bên phải $a_i$ mà đều có thứ tự tăng dần, thì việc tìm ra vị trí phần tử đầu tiên $\gt a_i$ chỉ là tìm kiếm nhị phân, và khi có được vị trí đó ta ngay lập tức biết được từ đó đến cuối có bao nhiêu phần tử.

Ví dụ

Đằng sau $a_i$ có 10 phần tử (đã sắp tăng) với index từ $0$ đến $9$. Giả sử tìm ra tại index $6$ là phần tử đầu tiên $\gt a_i$ thì các phần tử index $6, 7, 8, 9$ đều $\gt a_i$ hết. Ta tính nhanh ra $4$ bằng cách $10 - 6 = 4$.

Nhưng vấn đề là để tạo ra được mảng tăng dần: nếu xét từ cuối mảng $a$ về đầu, cứ liên tục đưa các phần tử vào một mảng rồi gọi sắp xếp thì việc sắp xếp liên tục tốn chi phí rất lớn. Nên lúc này không dùng mảng được mà phải dùng cấu trúc cây để lưu trữ: đi từ cuối về đầu, đưa các phần tử vào cây. Cấu trúc cây (cây nhị phân tìm kiếm cân bằng) sẽ phân phần tử nhỏ hơn gốc qua bên trái, lớn hơn gốc qua bên phải, từ đó thao tác thêm, tìm kiếm hay xoá đều chỉ có chi phí $O(\log N)$.

Trong C++ có sẵn cấu trúc Ordered Set (thư viện __gnu_pbds) với hàm order_of_key(x) trả về số phần tử nhỏ hơn $x$ đang có trong cây. Các bạn tìm hiểu thêm về cấu trúc này ở bài viết Ordered Set and GNU C++ PBDS (GeeksforGeeks) nhé. Áp dụng vào bài:

• Duyệt $i$ từ $n - 1$ về $0$. Lúc xét $a_i$, trong cây đang chứa đúng các phần tử bên phải nó, có $n - 1 - i$ phần tử.
• Số phần tử $\lt a_i$ là o_set.order_of_key(a[i]). Vì dãy là hoán vị (không có số trùng) nên số phần tử $\gt a_i$ là $n - 1 - i - $ order_of_key(a[i]). Cộng vào sum.
• Rồi insert(a[i]) vào cây để phục vụ các phần tử bên trái.

Minh hoạ: cây luôn giữ các số bên phải theo thứ tự tăng

Em nhập hoán vị rồi bấm Tiếp. Hàng trên là dãy $a$ (ô vàng là $a_i$ đang xét, ô tím là những số đã nằm trong cây). Hàng dưới là nội dung cây theo thứ tự tăng dần: vạch đỏ là chỗ tìm kiếm nhị phân dừng lại, bên trái vạch là order_of_key, bên phải vạch (xanh) là những người giỏi hơn.

Hoán vị a

Ví dụ nhanh:

Đây là code của mình, các bạn tham khảo nhé:

#include <bits/stdc++.h>
using namespace std;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    int a[n];
    for(int i = 0; i < n; ++i){
        cin >> a[i];
    }
    ordered_set o_set;
    long long sum = 0;
    for(int i = n - 1; i >= 0; --i){
        sum += n - 1 - i - o_set.order_of_key(a[i]);
        o_set.insert(a[i]);
    }
    cout << sum;
    return 0;
}

import sys

# Python không có sẵn ordered_set như C++ (pbds), nên mình dùng cây Fenwick (BIT)
# để làm đúng 2 việc: insert(x) và order_of_key(x) = số phần tử < x trong tập.

def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    a = list(map(int, data[1:1 + n]))
    bit = [0] * (n + 1)

    def insert(x):
        while x <= n:
            bit[x] += 1
            x += x & -x

    def order_of_key(x):  # số phần tử < x
        x -= 1
        res = 0
        while x > 0:
            res += bit[x]
            x -= x & -x
        return res

    total = 0
    for i in range(n - 1, -1, -1):
        total += n - 1 - i - order_of_key(a[i])
        insert(a[i])
    print(total)

main()

Về bản Python

Python không có sẵn Ordered Set như __gnu_pbds của C++, nên trong bản Python mình dùng cây Fenwick (BIT) đánh dấu các giá trị đã đưa vào để làm đúng hai việc insert(x) và order_of_key(x), mỗi việc $O(\log N)$. Vì các giá trị chỉ từ $1$ đến $n$ nên dùng BIT rất gọn.

C++▶ Chạy tay từng dòng codeCách 2: duyệt từ cuối về đầu, order_of_key đếm số nhỏ hơn trong cây, suy ra số lớn hơn.

Dữ liệu vào (stdin) – sửa thoải mái5 3 4 2 1 5

Dữ liệu mẫu:

1#include <bits/stdc++.h>

2using namespace std;

3

4#include <ext/pb_ds/assoc_container.hpp>

5#include <ext/pb_ds/tree_policy.hpp>

6using namespace __gnu_pbds;

7

8#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>

9

10int main(){

11 ios::sync_with_stdio(0);

12 cin.tie(0);

13 cout.tie(0);

14 int n;

15 cin >> n;

16 int a[n];

17 for(int i = 0; i < n; ++i){

18 cin >> a[i];

19 }

20 ordered_set o_set;

21 long long sum = 0;

22 for(int i = n - 1; i >= 0; --i){

23 sum += n - 1 - i - o_set.order_of_key(a[i]);

24 o_set.insert(a[i]);

25 }

26 cout << sum;

27 return 0;

28}

ChậmVừaNhanhRất nhanh

Đánh giá độ phức tạp của cách làm này:

• Không gian: mảng $a$ và cây chứa tối đa $N$ phần tử ⇒ $O(N)$.
• Thời gian: $N$ lần order_of_key và insert, mỗi lần $O(\log N)$ ⇒ $O(N \log N)$. Với $N = 2 \cdot 10^5$ thì $N \log N \approx 2 \cdot 10^5 \cdot 18 = 3.6 \cdot 10^6$, vẫn thỏa $\lt 10^8$ nên yên tâm AC trong 1 giây.

Không gian$O(N)$

Thời gian$O(N \log N)$

Nếu dữ liệu có số trùng nhau thì sao?

Nói rõ là bài này áp dụng Ordered Set như trên được là do đề đảm bảo dữ liệu là hoán vị từ $1$ đến $N$, các phần tử phân biệt, mà cấu trúc này chỉ chứa dữ liệu phân biệt. Nếu tình huống dữ liệu có thể bị trùng nhau thì code ở trên sẽ bị sai, lúc này ta cần dùng Ordered Set phiên bản được "độ lại" để lưu được các phần tử trùng nhau (ví dụ lưu cặp (giá trị, chỉ số) hoặc dùng less_equal), các bạn có thể tìm hiểu thêm trên GeeksforGeeks với từ khoá "how to store duplicate elements in ordered set".

Ghi chú của mình: code C++ và Python của cả 2 cách đã được kiểm tra với 500 hoán vị ngẫu nhiên nhỏ (có cả dãy tăng dần, giảm dần), so khớp với nhau – khớp hết. Với hoán vị ngẫu nhiên $N = 2 \cdot 10^5$: Cách 2 (C++) chạy khoảng 0.3 giây, bản Python dùng BIT khoảng 1 giây; còn Cách 1 (C++) chạy hơn 2 phút trên máy mình ⇒ TLE đúng như phân tích. Với dãy tăng dần $N = 2 \cdot 10^5$ đáp án là $19999900000$, vượt quá int, nên nhớ dùng long long cho sum nhé.

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇