Cặp Số Kì Diệu (PAIRS (Chọn đội tuyển HSG QG Tiền Giang 2022-2023)

Nguồn: Chọn đội tuyển HSG QG Tiền Giang 2022-2023 · Codeforces 1541B Độ khó: Trung bình Số học Ước số Nhận xét

Đề bài

🇻🇳 Tiếng Việt🇬🇧 English (Codeforces 1541B)

Câu 2: Cặp số kì diệu (7 điểm) – Kỳ thi lập đội tuyển học sinh giỏi dự thi cấp quốc gia THPT năm học 2022-2023, Sở GD&ĐT Tiền Giang, ngày thi thứ nhất 04/10/2022.

Cho dãy số nguyên $a_1, a_2, \ldots, a_n$ chứa $n$ số nguyên phân biệt. Một cặp số $(i, j)$ với $(i \lt j)$ được gọi là kì diệu khi $a_i \cdot a_j = i + j$.

Hãy đếm số cặp số kì diệu trong dãy $a$.

Dữ liệu vào: Đọc từ tệp văn bản PAIRS.INP

• Dòng 1: Chứa số nguyên dương $t$ ($1 \le t \le 10^4$) là số bộ dữ liệu trong test này.
• Dòng đầu tiên trong mỗi bộ dữ liệu gồm số nguyên $n$ ($1 \le n \le 10^5$) là số lượng số hạng của dãy $a$.
• Dòng tiếp theo trong mỗi bộ dữ liệu gồm $n$ số nguyên phân biệt $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 2n$).

Kết quả: Ghi ra tệp văn bản PAIRS.OUT một số nguyên duy nhất là số cặp số kì diệu trong dãy $a$ (mỗi bộ dữ liệu ghi kết quả trên một dòng, như ví dụ).

Ràng buộc: Gọi $S$ là tổng các số nguyên $n$ trong mỗi test.

• Subtask 1 (50%): $S \le 10^3$.
• Subtask 2 (50%): $S \le 2 \cdot 10^5$.

Đề không ghi giới hạn thời gian, ta hiểu là 1 giây. Trên hệ thống chấm online (Codeforces) thì đọc/ghi dữ liệu chuẩn, không dùng file.

B. Pleasant Pairs – time limit per test: 2 seconds, memory limit per test: 256 megabytes.

You are given an array $a_1, a_2, \ldots, a_n$ consisting of $n$ distinct integers. Count the number of pairs of indices $(i, j)$ such that $i \lt j$ and $a_i \cdot a_j = i + j$.

Input

The first line contains one integer $t$ ($1 \le t \le 10^4$) — the number of test cases. Then $t$ cases follow.

The first line of each test case contains one integer $n$ ($2 \le n \le 10^5$) — the length of array $a$.

The second line of each test case contains $n$ space separated integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 2 \cdot n$) — the array $a$. It is guaranteed that all elements are distinct.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

Output

For each test case, output the number of pairs of indices $(i, j)$ such that $i \lt j$ and $a_i \cdot a_j = i + j$.

Note

For the first test case, the only pair that satisfies the constraints is $(1, 2)$, as $a_1 \cdot a_2 = 1 + 2 = 3$.

For the second test case, the only pair that satisfies the constraints is $(2, 3)$.

For the third test case, the pairs that satisfy the constraints are $(1, 2)$, $(1, 5)$, and $(2, 3)$.

PAIRS.INP / Input

3
2
3 1
3
6 1 5
5
3 1 5 9 2

PAIRS.OUT / Output

1
1
3

Giải thích:

• Trong bộ dữ liệu đầu tiên, cặp số kì diệu duy nhất là $(1, 2)$ vì $a_1 \cdot a_2 = 1 + 2 = 3$.
• Trong bộ dữ liệu thứ hai, cặp số kì diệu thoả mãn là $(2, 3)$.
• Trong bộ dữ liệu thứ ba, có 3 cặp số kì diệu $(1, 2)$, $(1, 5)$ và $(2, 3)$.

Lời mở đầu

Bài này mình được một bạn học viên hỏi. Lúc mình viết lời giải thì đề vừa mới thi xong nên chưa có trang nào đưa lên để nộp, phải tự làm tự check. Mình thử gửi cho một số bạn khác làm thì có vẻ các bạn trước giờ chỉ quen làm xong có trang nộp lên để check, còn giờ không có nơi nộp thì cũng không biết code làm ra có ổn hay không. Ổn ở đây trước tiên là chính xác, sau đó là chạy thoả giới hạn thời gian đề bài đưa ra. Theo mình điều này không tốt chút nào, nên ở bài này trước tiên mình hướng dẫn các bạn giải quyết bài, sau đó mình chỉ cho các bạn cách tự kiểm chứng lời giải khi không có nơi nộp nhé 😇.

Tin vui là bài này thật ra có trên Codeforces với tên Pleasant Pairs (1541B), đề giống hệt (chỉ khác là $n \ge 2$ và giới hạn 2 giây), nên các bạn có thể nộp thử ở đây:

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

Giải thích ví dụ thứ ba: $a = [3, 1, 5, 9, 2]$ (vị trí tính từ 1). Xét các cặp:

Cặp (i, j)	$a_i \cdot a_j$	$i + j$	Kì diệu?
(1, 2)	3 · 1 = 3	3	✔
(1, 5)	3 · 2 = 6	6	✔
(2, 3)	1 · 5 = 5	5	✔
(2, 5)	1 · 2 = 2	7	✘
các cặp khác	…	…	✘

Nhắc lại về giới hạn thời gian

Với hệ thống chấm giới hạn 1 giây, tổng số lần lặp toàn bài chỉ nên ở ngưỡng $(3 \to 5) \cdot 10^7$ là an toàn; server mạnh có thể lên $10^8$ nhưng hên xui. Đó là cho C/C++, Python chạy chậm hơn nên ngưỡng phải thấp hơn. Đề cho 2 giây thì nhân 2 ngưỡng lên, cứ thế. Đề không ghi giới hạn thời gian thì thông thường ta tự hiểu là 1 giây.

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

Cách 1Vét cạn mọi cặp · O(T·N²) · 50%Cách 2Chỉ duyệt bội số của a[i] · O(N log N)Kiểm chứngSinh test + so với vét cạn + đo thời gian

Cách 1Vét cạn xét mọi cặp – O(T · N²)

Cách đơn giản nhất là vét cạn xét tất cả mọi cặp số, cặp nào thoả yêu cầu thì đếm. Đơn giản là 2 vòng for lồng nhau: i chạy từ 1 đến < n, với mỗi i thì j chạy từ i + 1 đến n, tức là phần tử a[i] bắt cặp với tất cả các phần tử phía sau nó. Ví dụ mảng a b c d: xét a với b, c, d; xét b với c, d; cuối cùng c với d. Nếu tích 2 phần tử bằng tổng 2 vị trí thì tăng biến đếm.

Làm theo cách này sẽ lấy được 50% điểm. Bạn nào không nghĩ ra cách tối ưu thì cứ chấp nhận lấy 50% này còn hơn là không có. May mắn là đề thi chấm theo thể thức IOI (đúng test nào ăn điểm test đó), chứ nếu chấm ACM (phải đúng full test mới Accepted) thì cách này không dùng được. Và kể cả khi các bạn đã nghĩ ra cách tối ưu mà chưa chắc chắn, lời khuyên của mình là cứ code cách vét cạn ra rồi dùng nó làm công cụ kiểm tra cho cách tối ưu (mình hướng dẫn ở phần cuối).

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 t;
    cin >> t;
    while(t--){
        int n;
        cin >> n;
        vector<long long> a(n + 1);
        for(int i = 1; i <= n; ++i){
            cin >> a[i];
        }
        long long res = 0;
        for(int i = 1; i < n; ++i){
            for(int j = i + 1; j <= n; ++j){
                if(a[i] * a[j] == i + j){
                    res++;
                }
            }
        }
        cout << res << endl;
    }
    return 0;
}

import sys

def main():
    data = sys.stdin.buffer.read().split()
    t = int(data[0]); p = 1
    out = []
    for _ in range(t):
        n = int(data[p]); p += 1
        a = [0] + [int(x) for x in data[p:p + n]]; p += n
        res = 0
        for i in range(1, n):
            for j in range(i + 1, n + 1):
                if a[i] * a[j] == i + j:
                    res += 1
        out.append(res)
    print('\n'.join(map(str, out)))

main()

Ba dòng đầu hàm main (ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);) giúp đẩy nhanh tốc độ nhập xuất khi code C++, bài nào cần nhập xuất nhiều thì nên thêm vào.

Vét cạn dễ nhưng vẫn có thể mất điểm vì 4 chỗ sau

1. Vị trí tính từ 1. Đề không nói rõ nhưng phần giải thích ví dụ cho thấy vị trí tính từ 1. Vị trí tham gia trực tiếp vào điều kiện $a_i \cdot a_j = i + j$, nên nếu theo thói quen cho index chạy từ 0 là sai ngay. Mình cho mảng $n + 1$ phần tử, bỏ qua index 0.
2. Tràn số khi nhân. $a_i \le 2n$, mà tổng $n$ tối đa $2 \cdot 10^5$ nên với $T = 1$ thì $a_i$ có thể tới $4 \cdot 10^5$. Cặp lớn nhất $399\,999 \cdot 400\,000 \approx 1.6 \cdot 10^{11}$ (gần 160 tỷ), vượt xa giới hạn hơn 2 tỷ của int. Nên mảng phải để kiểu long long.
3. Tràn bộ nhớ stack. Mảng long long $2 \cdot 10^5$ phần tử tốn $1.6$ triệu byte ≈ 1.5 MB. Mảng tĩnh khai báo trong main chỉ nên 1 MB đổ lại, nên mình dùng vector (cấp phát động trên heap). Hoặc dùng new long long[200000], hoặc khai báo mảng toàn cục.
4. Biến đếm. Để chắc ăn res cũng nên là long long (số cặp tối đa $\frac{N(N-1)}{2}$ có thể gần 20 tỷ). Chốt lại: cứ cho kiểu 8 byte hết cho chắc.

Đánh giá độ phức tạp:

• Không gian: mảng $N + 1$ phần tử: $O(N)$.
• Thời gian: số lần lặp là $\frac{N(N-1)}{2} = \frac{1}{2}(N^2 - N)$. Bỏ hằng số $\frac{1}{2}$, lấy thành phần lớn nhất ⇒ $O(N^2)$; cộng thêm $O(N)$ đọc dữ liệu vẫn là $O(N^2)$. Có $T$ bộ test ⇒ $O(T \cdot N^2)$.

Không gian$O(N)$

Thời gian$O(T \cdot N^2)$

Với $T = 1$, $N = 2 \cdot 10^5$ thì $N^2 = 4 \cdot 10^{10}$, gấp 400 lần ngưỡng $10^8$, tức là cần cỡ 400 giây (gần 7 phút) ⇒ chắc chắn TLE. Còn subtask 1 với $S \le 10^3$ thì $(10^3)^2 = 10^6$, yên tâm chạy trong 1 giây.

Cách 2Chỉ duyệt các bội số của a[i] – O(N log N)

Đoán độ phức tạp cần đạt. Một kinh nghiệm: thấy số phần tử cỡ $2 \cdot 10^5$ thì nhẩm theo bảng độ phức tạp. $N^2$ không ổn thì hạ xuống $N\sqrt{N} \approx 2 \cdot 10^5 \cdot 450 = 9 \cdot 10^7$, có vẻ vẫn $\le 10^8$ nhưng rất mong manh. Hạ tiếp xuống $N \log N \approx 2 \cdot 10^5 \cdot 18 = 3.6 \cdot 10^6$ thì quá đẹp. Riêng $O(N)$ thì mình nghĩ khó mà đạt được (đọc input thôi đã tốn $O(N)$ rồi, chưa kể xử lý). Vậy ta hướng tới $N\sqrt{N}$ hoặc $N \log N$.

Cải tiến từ vét cạn. Chưa nghĩ ra cách nào tốt hơn thì nhìn lại cách vét cạn và tự hỏi: có thể cải tiến thế nào? Giả sử $N = 1000$, xét $a_2 = 5$, vét cạn phải xét nó với 998 phần tử phía sau. Có cách nào không cần xét đủ 998 phần tử mà vẫn biết phần tử nào thoả không?

Nhìn lại biểu thức: $a_i \cdot a_j = i + j$. Khi xét tới $a_i$ thì ta đã biết cụ thể $a_i$ và $i$. Thay số $a_2 = 5$:

Nhận xét then chốt

$5 \cdot a_j = 2 + j$ ⇒ $(2 + j)$ phải chia hết cho 5, tức $(2 + j)$ là một bội số của 5: 5, 10, 15, 20, … Tổng quát: $i + j$ phải là bội số của $a_i$. Mà $j \le N$ nên $i + j \le N + i$.

Với $N = 1000$: $2 + j \le 1002$, số bội của 5 không vượt quá 1002 là $\lfloor 1002 / 5 \rfloor = 200$ số: 5, 10, …, 1000 ⇒ $j = 3, 8, 13, \ldots, 998$. Vậy thay vì xét 998 giá trị $j$, ta chỉ xét 200 giá trị. Với mỗi $j$ đó kiểm tra $a_i \cdot a_j = i + j$ là xong. Nếu $a_2 = 1000$ thì còn đỡ hơn nữa: chỉ có $\lfloor 1002 / 1000 \rfloor = 1$ trường hợp là $j = 998$.

Các bạn nhập dãy vào khung dưới rồi bấm Tiếp để xem với mỗi $i$ (ô tím) ta chỉ nhảy tới các vị trí $j = \text{sum} - i$ với sum là bội của $a_i$ (dưới ô ghi giá trị sum tương ứng): ô xanh là cặp kì diệu, ô đỏ là không thoả, còn ô mờ là những vị trí được bỏ qua hoàn toàn, không cần xét:

Dãy a (vị trí từ 1)

Ví dụ nhanh:

Độ phức tạp trong trường hợp xấu nhất. Với mỗi $i$, số giá trị phải xét là khoảng $\frac{N + i}{a_i}$. Mẫu số $a_i$ càng nhỏ thì phải xét càng nhiều, nên trường hợp xấu nhất là dãy $1, 2, 3, \ldots, N$ ($a_i = i$). Khi đó tổng số lần xét là:

$$\frac{N+1}{1} + \frac{N+2}{2} + \cdots + \frac{N+N}{N} = \left(\frac{N}{1} + \frac{N}{2} + \cdots + \frac{N}{N}\right) + \underbrace{(1 + 1 + \cdots + 1)}_{N} = N\left(1 + \frac{1}{2} + \cdots + \frac{1}{N}\right) + N$$

Bỏ phần $+N$ (lấy thành phần lớn nhất), còn $N \cdot \left(1 + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{N}\right)$. Tổng $1 + \frac{1}{2} + \cdots + \frac{1}{N}$ là chuỗi điều hoà, có độ lớn $O(\log N)$ (các bạn có thể tìm "Time Complexity of 1 + 1/2 + 1/3 + … + 1/N", hoặc xem bài blog này trên Codeforces). Vậy độ phức tạp là $O(N \log N)$: với $N = 2 \cdot 10^5$ thì cỡ $3.6 \cdot 10^6$, thấp hơn ngưỡng $(3 \to 5) \cdot 10^7$ cả chục lần, yên tâm.

Đến đây mọi thứ đã trình bày hết từ ý tưởng đến tính độ phức tạp. Giờ thì đi cài đặt thôi, source code để các bạn tham khảo:

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

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while(t--){
        int n;
        cin >> n;
        vector<long long> a(n + 1);
        for(int i = 1; i <= n; ++i){
            cin >> a[i];
        }
        long long res = 0;
        for(int i = 1; i <= n; ++i){
            int sz = n + i;
            int sum = a[i];
            while(sum <= sz){
                int j = sum - i;
                if(j > i){
                    if(a[i] * a[j] == i + j){
                        res++;
                    }
                }
                sum += a[i];
            }
        }
        cout << res << endl;
    }
    return 0;
}

import sys

def main():
    data = sys.stdin.buffer.read().split()
    t = int(data[0]); p = 1
    out = []
    for _ in range(t):
        n = int(data[p]); p += 1
        a = [0] + [int(x) for x in data[p:p + n]]; p += n
        res = 0
        for i in range(1, n + 1):
            ai = a[i]
            # sum = i + j chạy qua các bội số của a[i], không vượt quá n + i
            for s in range(ai, n + i + 1, ai):
                j = s - i
                if j > i and ai * a[j] == s:
                    res += 1
        out.append(res)
    print('\n'.join(map(str, out)))

main()

Giải thích code: với mỗi $a_i$, sz = n + i là giá trị lớn nhất có thể của $i + j$ (khi $j = n$). Khởi tạo sum = a[i] là bội số đầu tiên của $a_i$, rồi sum += a[i] để lần lượt đi qua các bội tiếp theo (ví dụ $a_i = 5$ thì sum = 5, 10, 15, …), lặp tới khi sum > sz thì dừng. Mỗi giá trị sum chính là $i + j$, nên $j$ = sum - i, và chỉ xử lý khi j > i (ví dụ sum = 5, i = 3 thì j = 2 < i, bỏ qua). Xác định được $j$ thì kiểm tra a[i] * a[j] == i + j để tăng res.

Bản Python

Bản Python dùng range(ai, n + i + 1, ai) để chạy qua các bội số, đúng y như vòng while của bản C++. Với trường hợp xấu nhất $N = 2 \cdot 10^5$ (dãy $1, 2, \ldots, N$) bản Python chạy khoảng 1 giây trên máy mình, vừa đủ với giới hạn 2 giây của Codeforces.

Khung chạy tay dưới đây chạy đúng từng dòng code C++ ở trên:

C++▶ Chạy tay từng dòng codeVới mỗi i, cho sum chạy qua các bội số của a[i] (không quá n + i), j = sum − i, kiểm tra a[i]·a[j] == i + j.

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

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 t;

9 cin >> t;

10 while(t--){

11 int n;

12 cin >> n;

13 vector<long long> a(n + 1);

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

15 cin >> a[i];

16 }

17 long long res = 0;

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

19 int sz = n + i;

20 int sum = a[i];

21 while(sum <= sz){

22 int j = sum - i;

23 if(j > i){

24 if(a[i] * a[j] == i + j){

25 res++;

26 }

27 }

28 sum += a[i];

29 }

30 }

31 cout << res << endl;

32 }

33 return 0;

34}

ChậmVừaNhanhRất nhanh

Đánh giá độ phức tạp:

• Không gian: $O(N)$ cho mảng.
• Thời gian: $O(N \log N)$ cho mỗi bộ test như đã phân tích, tổng cộng $O(S \log S)$ với $S$ là tổng $n$ (hay viết gọn là $O(T \cdot N \log N)$).

Không gian$O(N)$

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

ThêmTự kiểm chứng khi không có nơi nộp bài

Phần này mình cố gắng viết thêm để mang đến giá trị cho các bạn. Làm sao biết cách 2 không bị Wrong Answer (ra đáp án sai) hay Time Limit Exceeded (quá thời gian)? Ý tưởng:

1. Code vét cạn (cách 1) thì chắc chắn đúng vì nó xét tất cả mọi cặp. Ta sinh ngẫu nhiên các bộ test đúng như đề mô tả, dùng code vét cạn tính đáp án đúng, ghi tất cả vào file data.txt.
2. Dùng code tối ưu đọc từng bộ test và đáp án đúng trong file, tự tính rồi so sánh, đồng thời đo thời gian xử lý. Chạy hết mà toàn OK thì yên tâm; gặp WRONG ANSWER hay TIME LIMIT thì dừng lại, in ra test đó để dò lỗi.

Bước 1 – code sinh dữ liệu (file data.txt sẽ được tạo ra cùng chỗ với file code). Đề cho $1 \le T \le 10^4$, $1 \le N \le 10^5$, các giá trị trong $[1, 2N]$ và không trùng nhau. Ở đây mình chỉ random $N$ tối đa 1000, vì vét cạn $O(T \cdot N^2)$ với $N$ lớn sẽ chạy rất lâu; muốn thử $N$ lớn thì hạ $T$ xuống (nhớ tổng $N$ chỉ tối đa $2 \cdot 10^5$). Sau mỗi bộ test mình ghi thêm 1 dòng là đáp án của vét cạn:

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

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    freopen("data.txt", "w", stdout);
    srand(time(0));
    int t = 1 + rand() % 10000;
    cout << t;
    while(t--){
        int n = 1 + rand() % 1000;
        cout << endl << n << endl;
        vector<bool> check(2 * n + 1, false);
        vector<long long> a(n + 1);
        for(int i = 1; i <= n; ++i){
            do{
                a[i] = 1 + rand() % (2 * n);
            }while(check[a[i]] == true);
            cout << a[i] << " ";
            check[a[i]] = true;
        }
        long long res = 0;
        for(int i = 1; i < n; ++i){
            for(int j = i + 1; j <= n; ++j){
                if(a[i] * a[j] == i + j){
                    res++;
                }
            }
        }
        cout << endl << res;
    }
    return 0;
}

• freopen("data.txt", "w", stdout); mở file data.txt ở chế độ ghi (w = write), gắn với stdout: lúc này cout/printf không xuất ra màn hình nữa mà ghi vào file.
• Mảng check đánh dấu các giá trị đã sinh ra, nếu trùng thì random lại tới khi được giá trị chưa từng xuất hiện (để đảm bảo các số phân biệt).

Bước 2 – code kiểm tra: chính là code cách 2, chỉ thêm việc đọc đáp án đúng answer sau mỗi bộ test và đo thời gian:

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

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    freopen("data.txt", "r", stdin);
    int t;
    cin >> t;
    while(t--){
        int start = clock();
        int n;
        cin >> n;
        vector<long long> a(n + 1);
        for(int i = 1; i <= n; ++i){
            cin >> a[i];
        }
        long long answer;
        cin >> answer;
        long long res = 0;
        for(int i = 1; i <= n; ++i){
            int sz = n + i;
            int sum = a[i];
            while(sum <= sz){
                int j = sum - i;
                if(j > i){
                    if(a[i] * a[j] == i + j){
                        res++;
                    }
                }
                sum += a[i];
            }
        }
        int TotalTime = clock() - start;
        if(res == answer && TotalTime <= 1000){
            cout << "OK\n";
        }
        else{
            if(res != answer){
                cout << "WRONG ANSWER\n";
            }
            else{
                cout << "TIME LIMIT\n";
            }
            cout << "n = " << n << endl;
            cout << "array = ";
            for(int i = 1; i <= n; ++i){
                cout << a[i] << " ";
            }
            cout << endl << "answer = " << answer << endl;
            cout << "output = " << res << endl;
            cout << "Total Time = " << TotalTime;
            break;
        }
    }
    return 0;
}

• freopen("data.txt", "r", stdin); mở file ở chế độ đọc (r = read), gắn với stdin: cin/scanf sẽ đọc từ file thay vì bàn phím.
• Đọc xong mảng thì đọc tiếp answer (đáp án đúng có sẵn trong file) để sau cùng so với res.
• int start = clock(); lấy mốc thời gian lúc bắt đầu, clock() - start là thời gian đã chạy. So với 1000 (ms) để báo TLE.

Lưu ý nhỏ về clock()

clock() trả về số "tick", đổi ra giây thì chia cho CLOCKS_PER_SEC: double TotalTime = (double)(clock() - start) / CLOCKS_PER_SEC;. Trên Windows CLOCKS_PER_SEC = 1000 nên clock() - start đúng là mili giây như code ở trên; còn trên Linux/macOS CLOCKS_PER_SEC = 1 000 000 nên muốn ra mili giây phải tính (clock() - start) * 1000 / CLOCKS_PER_SEC. Dùng công thức chia cho CLOCKS_PER_SEC là chạy đúng ở mọi nơi.

Ghi chú của mình: code C++ và Python của cả 2 cách đã được kiểm tra với test của đề và 300 file test ngẫu nhiên (mỗi file 20 bộ, $n \le 12$) cùng một file 50 bộ với $n \le 300$, so với nhau và với vét cạn – khớp hết. Đo thời gian với $N = 2 \cdot 10^5$: dãy xấu nhất $1, 2, \ldots, N$ thì cách 2 bản C++ chạy khoảng 0.03 giây, bản Python khoảng 1 giây; dãy ngẫu nhiên thì C++ 0.06 giây, Python 0.65 giây; $10^4$ bộ test nhỏ C++ 0.03 giây. Cách 1 (C++) với dãy $N = 2 \cdot 10^5$ mất khoảng 32 giây, đúng như phân tích là chỉ ăn được subtask 1.

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 😇