Bộ Số Tam Giác (BOSOTG) (HSG12 Đà Nẵng 2018-2019 – Bài 1)
Đề bài
BOSOTG – Bộ số tam giác (Bài 1 – Đề thi HSG lớp 12 TP Đà Nẵng năm học 2018-2019)
Cho dãy số $A$ gồm $n$ phần tử nguyên dương $A_1, A_2, \ldots, A_n$. Mỗi phần tử có giá trị không vượt quá $10^9$ và $1 \lt n \le 5000$. Một bộ ba số được gọi là bộ số tam giác, nếu ba số này tạo thành ba cạnh của một tam giác nào đó.
Yêu cầu: Hãy đếm xem trong dãy $A$ có bao nhiêu bộ số tam giác $(A_i, A_j, A_k)$ với $i, j, k$ đôi một khác nhau.
Dữ liệu vào:
- Dòng đầu là số $n$;
- Dòng tiếp theo là các phần tử của dãy $A$, mỗi phần tử cách nhau một dấu cách.
Dữ liệu ra: Ghi ra số lượng bộ số tam giác.
Ràng buộc:
- Có 30% số test ứng với 30% số điểm của bài có $n \le 100$.
- Có 30% số test ứng với 30% số điểm của bài có $100 \lt n \le 1000$.
- Có 40% số test ứng với 40% số điểm của bài có $1000 \lt n \le 5000$.
Giới hạn thời gian: 1 giây. Giới hạn bộ nhớ: 512 MB. Dữ liệu vào/ra chuẩn (standard input / standard output).
5
4 3 1 5 73Lời mở đầu
Đây là bài 1 trong đề thi HSG lớp 12 TP Đà Nẵng năm học 2018-2019. Bài này rất hay để thấy được sức mạnh của giải thuật: mình sẽ đi từ cách vét cạn cần tới hơn 20 tỷ lần lặp, rồi rút xuống còn khoảng 162 triệu, cuối cùng chỉ còn khoảng 12,5 triệu lần lặp. Hy vọng mang đến được giá trị cho các bạn 😇.
Mình giải thích đề bài một chút cho bạn nào chưa hiểu. Cái này là kiến thức toán học cơ bản, nhưng mình nghĩ ít ra trong đề cũng nên có giải thích. Như đề nói, bộ số tam giác nghĩa là 3 số đó tạo thành 3 cạnh của một tam giác. Mình nói thêm: quy tắc để 3 cạnh tạo thành tam giác hợp lệ là tổng của 2 cạnh bất kỳ phải lớn hơn cạnh còn lại.
Ví dụ 3 cạnh $1, 2, 3$ là không hợp lệ vì $1 + 2$ không lớn hơn $3$: hai cạnh $1$ và $2$ nối lại chỉ vừa đúng bằng cạnh $3$ nên "nằm bẹp" xuống luôn, không dựng lên thành tam giác được:
Với ví dụ của đề, dãy $4, 3, 1, 5, 7$ có $5$ phần tử nên có tất cả $\binom{5}{3} = 10$ bộ ba vị trí khác nhau. Mình liệt kê hết ra để các bạn thấy vì sao đáp án là $3$:
| Bộ ba | Kiểm tra (2 cạnh nhỏ cộng lại so với cạnh lớn nhất) | Kết quả |
|---|---|---|
| (4, 3, 1) | 1 + 3 = 4, không > 4 | ✘ |
| (4, 3, 5) | 3 + 4 = 7 > 5 | ✔ |
| (4, 3, 7) | 3 + 4 = 7, không > 7 | ✘ |
| (4, 1, 5) | 1 + 4 = 5, không > 5 | ✘ |
| (4, 1, 7) | 1 + 4 = 5, không > 7 | ✘ |
| (4, 5, 7) | 4 + 5 = 9 > 7 | ✔ |
| (3, 1, 5) | 1 + 3 = 4, không > 5 | ✘ |
| (3, 1, 7) | 1 + 3 = 4, không > 7 | ✘ |
| (3, 5, 7) | 3 + 5 = 8 > 7 | ✔ |
| (1, 5, 7) | 1 + 5 = 6, không > 7 | ✘ |
Lưu ý là đề đếm theo vị trí đôi một khác nhau, nên nếu dãy có các giá trị trùng nhau (ví dụ $5, 5, 5, 5$) thì mỗi bộ ba vị trí vẫn được đếm riêng (dãy $5, 5, 5, 5$ có đáp án là $4$).
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 OJLộ trình lời giải, bấm vào từng phần để nhảy tới:
Cách 1Vét cạn tất cả các bộ 3 – O(N³)
Mình luôn khuyên các bạn là với mọi bài tập, nếu các bạn chưa nghĩ ra cách làm tối ưu, hoặc nghĩ ra rồi nhưng cảm giác chưa chắc chắn về độ chính xác, thì trước tiên hãy giải quyết bài đó theo cách vét cạn đi. Vì cách làm vét cạn sẽ luôn đảm bảo cho ra kết quả đúng (tất nhiên là bạn phải cài đặt đúng, nhưng thường cách vét cạn rất dễ cài), nó chỉ bị cái chạy lâu thôi. Nhờ vậy:
- Ta lợi dụng nó để kiểm tra tính chính xác cho cách làm tối ưu mà ta sẽ cố gắng làm ra sau đó (sinh test ngẫu nhiên nhỏ, chạy cả 2 code rồi so kết quả).
- Khi làm vét cạn rồi thì các bạn sẽ nhìn ra những cái chưa tốt của nó, từ đó làm tiền đề để tối ưu lại thành thuật toán tốt hơn.
- Nếu sau cùng vẫn không nghĩ ra cách tối ưu thì cách vét cạn sẽ giúp các bạn vét được bao nhiêu điểm thì vét (nếu thi chấm theo thể thức IOI, đúng test nào có điểm test đó; còn chấm theo thể thức ACM phải đúng hết mới AC thì thua rồi hihi).
Vậy cách vét cạn bài này là sao? Đó là ta xét tất cả các bộ 3 phần tử tại các vị trí phân biệt, với mỗi bộ ta kiểm tra xem nó có thỏa là tam giác không. Nếu thỏa thì tăng biến đếm lên, sau cùng biến đếm chính là kết quả.
Việc xét tất cả các bộ 3 rất đơn giản. Ví dụ có 5 phần tử ở các vị trí từ 1 tới 5 thì các bộ 3 vị trí phân biệt là: $\{1, 2, 3\}$, $\{1, 2, 4\}$, $\{1, 2, 5\}$, $\{1, 3, 4\}$, $\{1, 3, 5\}$, $\{1, 4, 5\}$, $\{2, 3, 4\}$, $\{2, 3, 5\}$, $\{2, 4, 5\}$, $\{3, 4, 5\}$. Để không bị đếm trùng, ta luôn chọn $i \lt j \lt k$, nên chỉ cần 3 vòng lặp lồng nhau: $j$ chạy từ $i + 1$, $k$ chạy từ $j + 1$ là giải quyết gọn.
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);
int n;
cin >> n;
int a[n];
for(int i = 0; i < n; ++i){
cin >> a[i];
}
long long res = 0;
for(int i = 0; i < n; ++i){
for(int j = i + 1; j < n; ++j){
for(int k = j + 1; k < n; ++k){
if(a[i] + a[j] > a[k]
&& a[i] + a[k] > a[j]
&& a[j] + a[k] > a[i]){
res++;
}
}
}
}
cout << res;
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0])
a = [int(x) for x in data[1:1 + n]]
res = 0
for i in range(n):
for j in range(i + 1, n):
for k in range(j + 1, n):
if (a[i] + a[j] > a[k]
and a[i] + a[k] > a[j]
and a[j] + a[k] > a[i]):
res += 1
print(res)
main()Các bạn bấm Tiếp để xem 3 con trỏ $i, j, k$ đi qua từng bộ 3, bộ nào thỏa điều kiện tam giác sẽ được tô xanh:
Giải thích 1 số chỗ trong cách làm ở trên:
- 2 dòng đầu hàm main (
ios::sync_with_stdio(0); cin.tie(0);) giúp đẩy nhanh tốc độ nhập xuất dữ liệu nếu các bạn code C++ (để hiểu vì sao thì cứ gõ mấy từ này lên Google là ra rất nhiều bài viết giải thích nhé). Bài này $n$ tối đa $5000$, tức là số phần tử cần nhập có thể lên tới $5000$, nên kinh nghiệm là cứ để 2 dòng này vào cho chạy nhanh hơn. Tất nhiên nếu code theo cú pháp C (scanf/printf) thì chẳng cần mấy dòng đó, nhưng thường khi code lập trình thi đấu ta dùng C++ vì cú pháp ngắn gọn và nhiều hỗ trợ, nên bạn nào code C++ thì nhớ thêm 2 dòng này vào đầu hàm main nhé. - Biến đáp án
resnên dùng kiểulong long(số nguyên 8 byte) để tránh bị tràn số. Với $n = 5000$ và mọi bộ 3 đều là tam giác thì đáp án là $\binom{5000}{3} = 20\,820\,835\,000$ – vượt xa giới hạn khoảng $2{,}1$ tỷ của kiểuint. - Đúng ra vòng lặp
for ichỉ cần chạy tới $i \lt n - 2$ vàfor jchỉ cần tới $j \lt n - 1$, vì bộ 3 cuối cùng là 3 phần tử cuối danh sách (giá trị $i$ cuối cùng là $n - 3$, $j$ cuối cùng là $n - 2$). Tuy nhiên quan điểm của mình là cứ để $i \lt n$, $j \lt n$ luôn, vì nó chỉ xét thêm 1, 2 lần giá trị $i, j$ rồi $k$ sẽ không thỏa ngay; như vậy tốt hơn là với tất cả các giá trị $i, j$ cứ phải làm thêm phép trừ khi so sánh điều kiện vòng lặp.
Đánh giá độ phức tạp của cách làm này:
- Không gian: $O(N)$ cho mảng $a$.
- Thời gian: bước đọc dữ liệu lặp $N$ lần. Bước xử lý xét tất cả các bộ 3: tính chính xác thì tổng số lần lặp của 3 vòng lặp lồng nhau (cũng là tổng số bộ 3 cần xét) là $\dfrac{N(N-1)(N-2)}{6}$. Về mặt tổng quát, mỗi vòng lặp $i, j, k$ trong trường hợp xấu nhất đều chạy cỡ $N$ lần, 3 vòng lồng nhau nên độ phức tạp là $O(N^3)$. Cộng với $O(N)$ của bước đọc dữ liệu thì theo quy tắc cộng Big O ta lấy thành phần lớn nhất, kết luận $O(N^3)$.
Cách 2Sắp xếp tăng dần + tìm kiếm nhị phân – O(N²·logN)
Ta cần tìm ra cách làm với độ phức tạp thời gian tốt hơn. Ở cách trên ta phải xét qua toàn bộ các bộ 3 là do dữ liệu của ta đang lộn xộn, chưa có quy tắc. Vậy nếu chuẩn hóa cho dữ liệu có trật tự thì có thể tốt hơn. Thử với ví dụ của đề: $4, 3, 1, 5, 7$. Nếu ta sắp xếp tăng dần thành $1, 3, 4, 5, 7$ thì liệu có xét nhanh hơn không? Các bạn cùng xem nhé.
Khi dãy đã tăng dần, ta dùng 2 vòng lặp for i, j lồng nhau để xét tất cả các cặp và tính tổng từng cặp. Nhưng tiếp theo không cần vòng lặp for k như cách trước nữa, mà ta tìm từ vị trí $j + 1$ trở đi đến cuối xem có bao nhiêu phần tử có giá trị nhỏ hơn tổng $a[i] + a[j]$. Có bao nhiêu phần tử như vậy thì bấy nhiêu phần tử đó sẽ kết hợp được với cặp $a[i], a[j]$ để tạo thành bộ số tam giác.
Thử với dãy đã sắp xếp $1, 3, 4, 5, 7$:
- Cặp $\{1, 3\}$ tổng là $4$: sau phần tử $3$ chẳng có thằng nào nhỏ hơn $4$ ⇒ không có bộ nào.
- Cặp $\{1, 4\}$ tổng là $5$: sau phần tử $4$ chẳng có thằng nào nhỏ hơn $5$ ⇒ không có bộ nào.
- Cặp $\{1, 5\}$ tổng là $6$: sau phần tử $5$ chẳng có thằng nào nhỏ hơn $6$ ⇒ không có bộ nào.
- Cặp $\{1, 7\}$ tổng là $8$: sau phần tử $7$ không còn phần tử nào để xét.
- Cặp $\{3, 4\}$ tổng là $7$: sau phần tử $4$ có duy nhất $5$ nhỏ hơn $7$ ⇒ tìm được bộ $\{3, 4, 5\}$.
- Cặp $\{3, 5\}$ tổng là $8$: sau phần tử $5$ có duy nhất $7$ nhỏ hơn $8$ ⇒ thêm bộ $\{3, 5, 7\}$, có 2 bộ.
- Cặp $\{3, 7\}$ tổng là $10$: sau phần tử $7$ không còn phần tử nào.
- Cặp $\{4, 5\}$ tổng là $9$: sau phần tử $5$ có duy nhất $7$ nhỏ hơn $9$ ⇒ thêm bộ $\{4, 5, 7\}$, có 3 bộ.
- Các cặp $\{4, 7\}$, $\{5, 7\}$: phía sau không còn phần tử nào.
Vậy sau cùng ta tìm được $3$ bộ – đúng đáp án.
- $a + c \gt b$ là đương nhiên: $c$ vốn đã $\ge b$, còn được cộng thêm $a \gt 0$ nữa thì càng lớn hơn $b$.
- $b + c \gt a$ cũng đương nhiên: $c$ vốn đã $\ge a$, cộng thêm $b$ nữa thì càng lớn hơn $a$.
Và đến đây đừng nói với mình là các bạn còn nghĩ đến việc đi tìm tuần tự từ vị trí $j + 1$ trở đi, đếm xem có bao nhiêu thằng nhỏ hơn $a[i] + a[j]$, gặp thằng nào $\ge$ thì dừng (vì xét tiếp toàn những thằng lớn hơn nữa thôi) nhé. Nghĩ vậy thì cũng tối ưu thêm được chút xíu so với cách 1 vì vòng for k có thể kết thúc sớm, nhưng không tối ưu thêm bao nhiêu cả – xét ra vẫn là tìm kiếm tuần tự.
Tối ưu hơn là ta tìm kiếm nhị phân, vì danh sách đã có thứ tự rồi các bạn nha. Cụ thể sau khi tính tổng $a[i] + a[j]$, ta tìm từ vị trí $j + 1$ trở đi xem vị trí đầu tiên có giá trị $\ge a[i] + a[j]$, gọi là $k$. Tại đó là sự kết thúc, nên các phần tử nằm giữa $j$ và $k$ (từ $j + 1$ đến $k - 1$) chính là các phần tử nhỏ hơn tổng $a[i] + a[j]$, và số lượng tính ngay được bằng cách lấy 2 vị trí trừ nhau:
Ví dụ $j = 2$, $k = 5$ thì các vị trí $3, 4$ thỏa, có $5 - 2 - 1 = 2$ phần tử. Nếu không tìm được thằng nào (ngay $a[j + 1]$ đã $\ge$ tổng) thì $k = j + 1$, trừ ra $0$. Còn nếu mọi phần tử phía sau đều nhỏ hơn tổng thì $k = n$.
Đến đây sẽ rất gọn nếu bạn nào biết hàm lower_bound trong thư viện giải thuật của C++: hàm trả về vị trí đầu tiên có phần tử $\ge x$ (với $x$ là giá trị cần tìm), nếu không có thì trả về vị trí cuối đoạn tìm. Bạn nào chưa biết cách dùng hàm này thì nên Google tìm hiểu thêm nhé. Bên Python thì tương ứng là hàm bisect_left trong thư viện bisect.
Minh hoạ: với mỗi cặp (i, j), tìm k bằng lower_bound
Các bạn nhập dãy rồi bấm Tiếp. Hai ô vàng là cặp $a[i], a[j]$; các ô xanh là những phần tử phía sau nhỏ hơn tổng (mỗi ô xanh là 1 bộ số tam giác); ô đỏ là vị trí $k$ mà lower_bound trả về:
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);
int n;
cin >> n;
int a[n];
for(int i = 0; i < n; ++i){
cin >> a[i];
}
sort(a, a + n);
long long res = 0;
for(int i = 0; i < n; ++i){
for(int j = i + 1; j < n; ++j){
int k = lower_bound(a + j + 1, a + n, a[i] + a[j]) - a;
res += k - j - 1;
}
}
cout << res;
return 0;
}import sys
from bisect import bisect_left
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0])
a = sorted(int(x) for x in data[1:1 + n])
res = 0
for i in range(n):
for j in range(i + 1, n):
# vị trí đầu tiên trong đoạn [j + 1, n) có giá trị >= a[i] + a[j]
k = bisect_left(a, a[i] + a[j], j + 1, n)
res += k - j - 1
print(res)
main()Giải thích 1 số chỗ trong cách làm ở trên:
sort(a, a + n);là sắp xếp tăng dần mảng $a$ từ vị trí đầu tiên (tham số đầuachính là địa chỉ ô $a[0]$, vì tên mảng luôn "trỏ" vào ô đầu tiên) và sắp $n$ phần tử (tham số thứ 2 làa + n). Đây là hàm trong thư viện giải thuậtalgorithm. Do mình include<bits/stdc++.h>là đã bao hết các thư viện khác rồi, còn bạn nào không dùng thư viện này thì nhớ khai báo#include <algorithm>mới dùng được hàmsortnha.lower_bound(a + j + 1, a + n, a[i] + a[j])nghĩa là bắt đầu tìm từ vị trí $j + 1$ đến hết mảng (phần tử thứ $n$), giá trị cần tìm là $a[i] + a[j]$. Hàm trả về địa chỉ của phần tử tìm thấy; muốn lấy ra chỉ số (index) thì trừ cho địa chỉ đầu mảnga– ra khoảng cách từ đầu mảng tới đó, chính là index. Hàm này cũng nằm trong thư việnalgorithm.- Tổng $a[i] + a[j]$ lớn nhất là $2 \cdot 10^9$, vẫn nằm vừa trong kiểu
int(tối đa $2\,147\,483\,647$) nên không bị tràn – nhưng chỉ dư có chút xíu thôi, đề mà cho $a_i$ tới $1{,}1 \cdot 10^9$ là phải chuyển sanglong longrồi nha.
Đánh giá độ phức tạp của cách làm này:
- Không gian: $O(N)$.
- Thời gian: bước đọc dữ liệu là $O(N)$. Bước sắp xếp dùng hàm
sortcó sẵn là $O(N \log N)$. Rồi 2 vòng lặp lồng nhau xét hết các cặp, tính chính xác là $\dfrac{N(N-1)}{2}$ lần, nhưng tổng quát thì vòng $j$ trường hợp lớn nhất cũng chạy cỡ $N$ lần nên xem là $O(N^2)$. Bên trong làlower_boundtìm kiếm nhị phân $O(\log N)$ – phạm vi tìm thật ra nhỏ dần, nhưng ta cứ tính gọn là $N$. Vậy bước này là $O(N^2 \log N)$. Tổng: $O(N) + O(N \log N) + O(N^2 \log N)$, lấy thành phần lớn nhất ⇒ $O(N^2 \log N)$.
#pragma GCC optimize("Ofast")Ofast còn O1, O2, O3… các bạn tìm hiểu hết đi nhé hehe.Cách 3Sắp xếp giảm dần + hai con trỏ – O(N²)
Từ đầu tới giờ ta đã đi từ $O(N^3)$ lên $O(N^2 \log N)$ nhưng vẫn chưa thực sự hiệu quả: nếu không nhờ #pragma GCC optimize thì đã bị TLE. Code mà phải nhờ vào gcc optimize mới AC được thì đó không phải code tối ưu, và cũng hên xui may rủi lắm các bạn ơi. Nên ta không nên chấp nhận như vậy mà phải cố tìm ra cách tốt hơn nữa.
Mình nói luôn: bài này giải được với độ phức tạp $O(N^2)$, và đây là độ phức tạp tối ưu nhất cho bài này – ít nhất theo quan điểm cá nhân mình thì không có cách nào tốt hơn $O(N^2)$ được. Để làm được thì ta dùng kỹ thuật Two Pointers (hai con trỏ). Yên tâm là không phải kiểu con trỏ, bộ nhớ trong C/C++ đâu nha, đó chỉ là tên gọi thôi: đại ý là 2 biến lưu vị trí (index) cùng di chuyển phối hợp với nhau.
Từ đây ta thấy, ví dụ có 10 số đã sắp giảm dần: $10, 9, 8, 7, 6, 5, 4, 3, 2, 1$ (vị trí mình tạm tính từ 1 cho dễ hình dung). Khi xét $a[1] = 10$ làm cạnh lớn nhất, chỉ cần đếm trong 9 số còn lại có bao nhiêu cặp có tổng lớn hơn $10$ – mỗi cặp như vậy ghép với $10$ thành 1 bộ số tam giác.
Đếm các cặp này ta không cần xét hết mọi cặp với chi phí $O(N^2)$. Đặt left = i + 1 = 2, right = n = 10:
- $a[2] + a[10] = 9 + 1 = 10$ không lớn hơn $10$. Danh sách đang giảm dần, muốn tổng lớn hơn thì phải giảm right (tiến lên phía trước là các phần tử lớn hơn):
right = 9. - $a[2] + a[9] = 9 + 2 = 11 \gt 10$: tìm được cặp đầu tiên. Nếu giữ nguyên
left = 2thì mọi vị trírighttừ $9$ lùi về $3$ đều cho tổng $\gt 10$, vì right càng giảm thì phần tử càng lớn, tổng càng tăng. Vậy tính ngay được right − left = 9 − 2 = 7 cặp ghép với $10$ thành tam giác. - Tăng
leftlên $3$. $a[3] + a[9] = 8 + 2 = 10$ không thỏa ⇒ giảmright = 8. $a[3] + a[8] = 8 + 3 = 11 \gt 10$ ⇒ thêm 8 − 3 = 5 cặp, rồi lại tăngleft… - Cứ thế lặp lại khi nào
left < right. Khileft >= rightthì dừng: đã đếm xong số cặp ghép được với $a[i]$. Sau đói++sang phần tử tiếp theo, khởi tạo lạileft = i + 1,right = nvà làm lại quy trình trên.
l = i + 1, r = n - 1; trong khi l < r:
- Nếu $a[l] + a[r] \le a[i]$: tổng chưa đủ lớn ⇒
r--(lấy phần tử lớn hơn). - Ngược lại: $a[l]$ ghép được với mọi $a[l+1], \ldots, a[r]$ ⇒
res += r - l, rồil++.
while chạy không quá $n$ lần.Minh hoạ hai con trỏ
Các bạn nhập dãy rồi bấm Tiếp. Ô vàng là $a[i]$ (cạnh lớn nhất), hai con trỏ $l, r$ được đánh dấu bên dưới. Khi $a[l] + a[r] \gt a[i]$, ô tím là $a[l]$ và các ô xanh là những bạn ghép được với $a[l]$:
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);
int n;
cin >> n;
int a[n];
for(int i = 0; i < n; ++i){
cin >> a[i];
}
sort(a, a + n, greater<int>());
long long res = 0;
for(int i = 0; i < n; ++i){
int l = i + 1;
int r = n - 1;
while(l < r){
if(a[l] + a[r] <= a[i]){
r--;
}
else{
res += r - l;
l++;
}
}
}
cout << res;
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0])
a = sorted((int(x) for x in data[1:1 + n]), reverse=True)
res = 0
for i in range(n):
l = i + 1
r = n - 1
ai = a[i]
while l < r:
if a[l] + a[r] <= ai:
r -= 1
else:
res += r - l
l += 1
print(res)
main()Giải thích 1 số chỗ trong cách làm ở trên:
- Ở ví dụ phía trên mình tính vị trí từ 1 cho các bạn dễ hình dung, nhưng trong lập trình index tính từ 0, nên
rightban đầu là vị trí cuối cùng $n - 1$. Còn lại mọi thứ không có gì thay đổi, đúng như những gì mình đã phân tích. - Hàm
sortmình giải thích ở cách 2 rồi, ở đây có thêm tham số thứ 3 làgreater<int>()để quy định sắp xếp giảm dần; không có nó thì mặc định là tăng dần nha các bạn. Bên Python thì dùngsorted(..., reverse=True).
Đánh giá độ phức tạp của cách làm này:
- Không gian: $O(N)$.
- Thời gian: đọc dữ liệu $O(N)$, sắp xếp giảm dần $O(N \log N)$. Bước 2 vòng lặp lồng nhau tính ra chỉ lặp khoảng $\dfrac{N(N-1)}{2}$ lần: vòng
whilevới $i$ đầu tiên chạy gần $N$ lần, các lần sau là $N - 1, N - 2, \ldots, 2, 1$ (giống kiểu 2 vòng lặp lồng nhau của thuật toán sắp xếp cơ bản mà các bạn học hồi nhập môn đó). Tính theo trường hợp lớn nhất thì bước này là $O(N^2)$. Tổng: $O(N) + O(N \log N) + O(N^2)$ ⇒ $O(N^2)$.
Với $N = 5000$, số lần lặp khoảng $5000 + 5000 \cdot 13 + \dfrac{5000 \cdot 4999}{2} = 12\,567\,500$ (12 triệu 567 ngàn 500) lần – ít hơn ngưỡng 1 giây từ 3 đến 10 lần, không sợ TLE. Mình nộp code trên chạy hết 109 ms; thêm gcc optimize như mẹo ở cách 2 thì còn 78 ms.
sort có sẵn của C++, độ phức tạp luôn được đảm bảo $O(N \log N)$ vì nó là sự kết hợp nhiều thuật toán sắp xếp tối ưu bên trong (bạn nào chưa biết có thể Google tìm hiểu thêm). Nếu không thì phải tự cài Quick Sort, Merge Sort, Heap Sort… – vừa mất công, lỡ cài sai, hoặc xui gặp trường hợp xấu nhất của Quick Sort thì cũng thành $O(N^2)$. Còn nếu cài các thuật toán cơ bản như Interchange Sort, Selection Sort, Bubble Sort ($O(N^2)$) thì về lý thuyết độ phức tạp cách 2 và cách 3 vẫn không đổi (vì bước xử lý chính đã $\ge N^2$ rồi), nhưng thực tế dùng hàm sort sẽ chạy nhanh hơn, điều này là không thể bàn cãi.Đến đây các bạn đã thấy cái hay của giải thuật rồi chứ? Từ cách làm chạy hết $20\,820\,840\,000$ lần lặp rút xuống còn $162\,537\,500$ lần, cuối cùng chỉ còn $12\,567\,500$ lần. Cách 2 nhanh hơn cách 1 khoảng 128 lần, cách 3 nhanh hơn cách 2 khoảng 13 lần. Quá tuyệt vời đúng không các bạn ^^
- Không biết học gì trước, học gì sau, học lan man nên kiến thức bị hổng.
- Bí bài không ai gỡ, ngồi cả buổi vẫn không ra rồi bỏ cuộc.
- Code chạy được nhưng không đủ điểm, không biết sai ở đâu, chậm ở đâu.
- Không có đề thi thử và người chấm, nên không biết mình đang ở mức nào.
- Dễ nản giữa chừng khi không có ai theo sát.
- Lộ trình 111 buổi video sắp sẵn từ dòng code đầu tiên đến đề HSG thật của các tỉnh.
- Thầy trực tiếp gỡ bí, chữa bài cho từng em qua nhóm Zalo riêng.
- Hệ thống chấm bài tự động 24/7 và thi thử HSG hằng tuần để biết chính xác mình đang ở đâu.
- Đóng học phí một lần, thầy kèm lâu dài: từ thi chuyên Tin đến HSG quốc gia và cả khi lên đại học.
Nhận xét
Đăng nhận xét