Bán Bitcoin
Đề bài
Bitcoin là một loại tiền mã hóa, được phát minh bởi Satoshi Nakamoto dưới dạng phần mềm mã nguồn mở từ năm 2009. Bitcoin có thể được trao đổi trực tiếp bằng thiết bị kết nối Internet mà không cần thông qua một tổ chức tài chính trung gian nào.
Sắn tìm hiểu và rất thích BITCOIN, cậu dự đoán giá của bitcoin trong $N$ ngày tiếp theo là $d_1, d_2, \ldots, d_n$ (đơn vị USD). Cậu ta nhờ bố giúp đỡ để có thể thu lời từ việc mua bán bitcoin. Bố cậu ta có thể cho cậu ta mượn 1 đồng bitcoin với hai điều kiện:
- Một là phải trả phí: mượn một ngày trả phí $K$ đô la. Khi trả lại phải trả đúng 1 bitcoin và tiền lời.
- Hai là cho mượn bất cứ ngày nào nhưng chỉ được bán đi và mua lại một lần duy nhất để kiếm lời.
Sắn đã có kế hoạch cho riêng mình để thu lời. Cậu ấy có thể bán ra đồng bitcoin vào một ngày bất kỳ nào đó nếu muốn và mua lại vào một ngày nào đó sau ngày bán, hoặc là không mua bán lần nào nếu không thu được tiền lời. Đố bạn Sắn sẽ thu được nhiều nhất bao nhiêu tiền nếu có kế hoạch bán tối ưu.
Dữ liệu nhập
- Dòng 1 là hai số nguyên $N$ và $K$ ($1 \le N \le 10^6$; $0 \le K \le 10^5$).
- Dòng 2 là giá bitcoin trong $N$ ngày tiếp theo $d_1, d_2, \ldots, d_n$ ($0 \le d_i \le 10^8$).
Kết quả: in ra một số nguyên duy nhất là số tiền lời tối đa mà Sắn thu được.
Subtask
- 50% số test đầu tiên có $N \le 10^3$.
- 50% số test còn lại có $N \le 10^6$.
3 1
10 8 53Trong ví dụ trên:
- Sắn bán ra ở ngày 1 thu được 10 USD.
- Sắn mua lại bitcoin ở ngày thứ 3 mất 5 USD.
- Vị chi tiền lời thu được: 10 − 5 − 2 = 3 USD (2 USD là tiền lãi phải trả cho bố sau 2 ngày mượn).
Lời mở đầu
Bài này mình được một bạn học viên hỏi nên sẵn tiện mình viết bài giải chi tiết để nhiều bạn được tham khảo luôn. Hy vọng mang đến được giá trị cho các bạn 😇.
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:
Rút gọn đề bài
Cái đề thì dài dòng lắm nhưng tóm gọn lại đề bài có thể phát biểu đơn giản thế này thôi, bạn nào phải nhìn ra được cái đề rút gọn lại thế này thì mới làm được bài này nha: cho dãy $N$ phần tử các giá trị $a_1, a_2, a_3, \ldots, a_n$. Gọi index $i$, $j$ là chỉ số từng phần tử trong mảng thỏa mãn $i < j$. Tìm giá trị lớn nhất của:
Đơn giản là vậy thôi. Tại sao có thể phát biểu đề bài đơn giản như vậy? Vì các bạn xem nhé, các giá trị mảng a là giá dự đoán bitcoin trong các ngày tiếp theo. Và theo ràng buộc đề đưa ra là chỉ bán được 1 lần duy nhất và sau khi bán thì mua được 1 lần duy nhất rồi thôi. Chính vì vậy ta xem giá trị a[i] chính là giá thời điểm bán đi và giá trị a[j] chính là giá thời điểm mua lại.
Chắc chắn $i$ phải $< j$, vì nếu trường hợp bằng nhau tức là bán đi và mua lại ngay trong ngày thì coi như tiền lãi vẫn là 0, thì ta đã có ràng buộc là có thể không bán và không mua thì tiền lãi vẫn là 0. Nên nếu việc ta ràng buộc $i \le j$ thì vẫn đúng thôi, nhưng cứ thế sẽ bị xét trùng rất nhiều phần tử không cần thiết. Ta chỉ cần ràng buộc $i < j$ rồi thì tìm giá trị của 2 cặp $i$, $j$ bất kỳ thỏa mãn a[i] - a[j] - (j - i) * K là lớn nhất, sau đó so sánh nó với 0 và chọn theo thằng lớn hơn.
Tại sao lại phải trừ cho (j - i) * K? Vì a[i] là giá thời điểm bán, a[j] là giá thời điểm mua lại, 2 thằng này trừ nhau thì ra tiền lời; thì còn phải trừ cho tiền lãi khoản vay là $K$ dollar/ngày, vì thế khoảng cách giữa 2 ngày chính là $j - i$ và nhân cho $K$ sẽ ra tổng số tiền phải trả. Tiền lời có được từ việc mua bán phải trả lãi cho khoản vay (tức là trừ đi) và phần còn lại chính là tiền lời thực sự giữ lại được.
50%Cách 1: vét cạn mọi cặp (i, j)
Thì 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 nhưng cảm giác chưa được 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 làm 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 thì mới ra kết quả đúng, nhưng thường cách làm vét cạn là rất dễ làm), thì nhờ vào việc luôn đảm bảo cho ra kết quả đúng đó, có cái là nó bị chạy lâu thôi, thì ta lợi dụng nó để kiểm tra tính chính xác cho cách làm tối ưu mà tiếp theo sau đó chúng ta sẽ cố gắng làm ra. Mình có hướng dẫn trong 1 bài viết cách làm công cụ kiểm tra tính chính xác nhờ cách làm vét cạn, bạn nào chưa xem thì nên xem qua tại đây nhé: Hạn chế lỗi Wrong Answer bằng vét cạn.
Cũng như khi các bạn làm theo kiểu 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 đề để các bạn tối ưu lại để đưa ra những thuật toán tốt hơn. Còn nếu sau cùng các bạn vẫn không nghĩ ra được cách làm tối ưu hơn thì cách làm 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 tức là đúng test case nào là có điểm test case đó; còn nếu chấm theo thể thức ACM phải đúng hết mới là AC thì thua rồi hihi).
Vậy nên với những gì mình đã phân tích ở trên thì ta sẽ thấy cách làm vét cạn đó là xét tất cả các cặp $(i, j)$ có thể có trong $N$ phần tử và tính giá trị a[i] - a[j] - (j - i) * K và so sánh với Max ban đầu khởi tạo là 0. Nếu nó lớn hơn thì cập nhật lại Max. Sau cùng in ra Max là số tiền lời nhiều nhất giữ lại được. Việc xét tất cả các cặp $(i, j)$ nó rất đơn giản, chính là kiểu 2 vòng lặp for lồng nhau của thuật toán sắp xếp cơ bản mà mới bắt đầu học lập trình các bạn được dạy đó.
Source code để các bạn tham khảo nếu làm theo hướng này:
Xem code cách 1 (vét cạn)
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
long long n, k;
cin >> n >> k;
vector<long long> a(n);
for(int i = 0; i < n; ++i){
cin >> a[i];
}
long long Max = 0;
for(long long i = 0; i < n; ++i){
for(long long j = i + 1; j < n; ++j){
Max = max(Max, a[i] - a[j] - (j - i) * k);
}
}
cout << Max;
return 0;
}n, k = map(int, input().split())
a = list(map(int, input().split()))
Max = 0
for i in range(n):
for j in range(i + 1, n):
Max = max(Max, a[i] - a[j] - (j - i) * k)
print(Max)Giải thích một số chỗ trong code ở trên:
ios::sync_with_stdio(0); cin.tie(0);2 dòng đầu tiên của hàm main sẽ giúp đẩy nhanh tốc độ nhập xuất dữ liệu nếu các bạn đang code theo ngôn ngữ C++ (để hiểu vì sao thì các bạn cứ gõ mấy từ này lên Google là sẽ ra rất nhiều bài viết giải thích nhé), nên 1 kinh nghiệm trong các bài mà cần nhập xuất nhiều, như trường hợp bài này ta thấy $N$ tối đa là $10^6$ số cần nhập nên đây là số lượng lớn thì ta nên để thêm 2 dòng này vào đầu để chương trình chạy nhanh hơn. Tất nhiên nếu các bạn code theo cú pháp của C thì chẳng cần mấy dòng đó làm gì, tuy nhiên thường khi code các bài lập trình thi đấu thế này ta dùng C++ vì cú pháp ngắn gọn cũng như nhiều hỗ trợ của nó, vậy nên bạn nào code C++ thì nhớ thêm 2 dòng này vào đầu hàm main nhé.- Các bạn để ý sẽ thấy mình khai báo kiểu
long longcho mảngavà các biếnn,k,Max. Tốt nhất nên là như vậy. Vì các bạn chú ý theo giới hạn dữ liệu đề đưa ra $K$ có thể tối đa lên đến $10^5$. Thì các bạn chú ý chỗ trong vòng lặp mình tính(j - i) * k. Tối đa chỗ này có thể $i$ là chỉ số index phần tử đầu tiên, $j$ là chỉ số index phần tử cuối cùng, như thế $j - i$ coi như là $10^6$ luôn nhé, rồi lại nhân tiếp cho $K$ có thể tối đa là $10^5$ thì lúc này kết quả sẽ là $10^{11}$, tức là 100 tỷ, vượt xa kiểuint. Cả biếni,jcũng nên khai báolong longcho chắc. - Câu lệnh
Max = max(Max, a[i] - a[j] - (j - i) * k);là cách viết gọn của:if(a[i] - a[j] - (j - i) * k > Max) { Max = a[i] - a[j] - (j - i) * k; }. Hàmmax(a, b)sẽ trả về giá trị lớn nhất trong 2 giá trịa,btruyền vào, đây là hàm được hỗ trợ sẵn trong thư viện giải thuật (algorithm) của C++. Do ở đây mình đang dùng thư việnbits/stdc++.h, một mình nó là bao chứa hết các thư viện khác nên mình không cần ghi thư viện giải thuật, nhưng nếu bạn nào không dùng thư việnbits/stdc++.hnày thì phải có thư viện giải thuật thì nó mới cho dùng hàm này nha. Tương tự với hàmmaxthì ta cũng có hàmminvới ý nghĩa trả về giá trị nhỏ nhất trong 2 tham số truyền vào, nếu các bạn về sau có gặp thì cũng hiểu hen.
Đánh giá độ phức tạp của cách làm này:
- Độ phức tạp không gian (Space Complexity): $O(N)$ với $N$ là số lượng phần tử của mảng.
- Độ phức tạp thời gian (Time Complexity): $O(N)$ của bước đọc dữ liệu từ input + chính xác số cặp $(i, j)$ được xét có thể tính bằng công thức $\frac{N(N-1)}{2}$. Tuy nhiên ta có thể kết luận độ phức tạp thời gian về mặt lý thuyết là $O(N^2)$. Bởi vì $\frac{N(N-1)}{2}$ nếu ta nhân trực tiếp vào phá ngoặc ra thì sẽ là $\frac{N^2}{2} - \frac{N}{2}$. Trừ cho $\frac{N}{2}$ tương đương là cộng cho $-\frac{N}{2}$. Thì theo quy tắc cộng Big O sẽ lấy đại diện theo thành phần lớn nhất nên chỗ này chắc chắn $\frac{N^2}{2}$ lớn hơn rồi nên ta chỉ lấy theo $\frac{N^2}{2}$. Tương tự khi cộng thêm $N$ của bước đọc dữ liệu thì cũng bỏ qua vì $\frac{N^2}{2}$ lớn hơn $N$. Mà $\frac{N^2}{2}$ nghĩa là $0.5 \times N^2$, thì theo quy tắc nhân Big O khi nhân với hằng số ta có thể bỏ qua, vì thế về mặt tổng quát ta kết luận là $O(N^2)$.
Vì sao vét cạn chậm?
Ta có thể làm theo cách tốt hơn thế nào? Thì mình nói luôn nha là bài này tối ưu nhất sẽ là $O(N)$, tức là bước xử lý chỉ cần 1 vòng lặp duy nhất duyệt qua $N$ phần tử thôi chứ không cần phải 2 vòng lặp lồng nhau như ở trên. Làm sao để được như vậy các bạn có thể xem tiếp.
Ta sẽ thấy rằng cách làm vét cạn ở trên có cái dở là nó luôn phải xét đi xét lại những vị trí mà trước đó nó đã xét. Mình sẽ ví dụ với $N = 5$ thì ta sẽ có các cặp sau:
| i | Các vị trí j được xét | Các cặp |
|---|---|---|
| 0 | 1, 2, 3, 4 | {0, 1}, {0, 2}, {0, 3}, {0, 4} |
| 1 | 2, 3, 4 | {1, 2}, {1, 3}, {1, 4} |
| 2 | 3, 4 | {2, 3}, {2, 4} |
| 3 | 4 | {3, 4} |
Các bạn sẽ thấy vị trí $j = 4$ bị xét lặp lại đủ 4 lần, $j = 3$ bị xét lặp lại 3 lần, $j = 2$ bị xét lặp lại 2 lần... Và đó chính là chỗ chưa được tối ưu của cách làm này. Nếu mỗi vị trí $j$ ta chỉ xét qua đúng 1 lần thôi chứ không bị xét lặp lại nhiều lần như thế này thì sẽ tối ưu hơn, các bạn đồng ý chứ?
Vậy làm sao để mỗi vị trí $j$ chỉ xét 1 lần duy nhất? Trước tiên ta phải hiểu được vì sao cách làm ở trên lại cứ phải xét lặp lại nhiều lần vị trí $j$? Nói chính xác là khi xét qua vị trí $i$ tăng lên tiếp theo thì cứ phải xét lại các vị trí $j$ đứng sau nó, từ đó vị trí $j$ liên tục bị xét lặp lại qua các lần $i$ mới. Nó làm vậy để đảm bảo từ vị trí $i$ mới đó sẽ xét qua tất cả các cặp có thể để a[i] - a[j] - (j - i) * k là lớn nhất có thể.
ACCách 2: tham lam, duyệt từ cuối về đầu – O(N)
Để làm được điều đó cần đến phương pháp tham lam (greedy) để giải quyết. Kể cả bạn nào có không biết về phương pháp tham lam này thì thực ra đôi khi các bạn đang giải quyết vấn đề theo chính tư tưởng của tham lam mà các bạn không biết. Cho bạn nào không biết thì mình có thể nói nhanh như thế này: tham lam ở đây nghĩa là ta sẽ cố gắng chọn ra cách giải quyết tốt nhất trong tất cả các cách ở hiện tại rồi đi theo cách giải quyết tốt nhất đó; nếu lại đứng trước nhiều lựa chọn cách giải quyết khác nhau nữa thì ta lại cố gắng chọn theo cách giải quyết tốt nhất trong số đó; tóm lại cứ tốt nhất mà triển, vì thế tên gọi nó là tham lam. Quy luật nó là như vậy thôi chứ còn lại không có công thức từng bước cụ thể giải quyết như mấy thuật toán khác. Thì tại sao bài này lại có thể nhìn ra tư tưởng của nó là tham lam? Đọc đề bài là thấy rõ mùi rồi hehe, muốn xử lý theo quy luật gì gì đó để sau cùng đáp án phải là nhỏ nhất/lớn nhất các kiểu, đọc kiểu này phát thấy mùi tham lam ngay. Thì thực ra tham lam chỉ là dạng tư tưởng thôi, còn lại để hiện thực được nó thì có thể cần đến những kỹ thuật bổ trợ khác nữa. Mình lấy ví dụ ngay trong chính bài tập này, các bạn cứ tiếp tục xem nhé.
Tư tưởng tham lam đơn giản là:
đúng không các bạn? Và giá trị thu được sau phép trừ đó là kết quả. Tức là chúng ta có: Số bị trừ − Số trừ = Hiệu, với số bị trừ là a[i] và số trừ là (a[j] + (j - i) * k). Vậy để Hiệu là lớn nhất thì có phải số trừ càng nhỏ thì hiệu sẽ càng lớn không? Cái này là quy tắc toán học đơn giản thôi mà: càng ít bị trừ thì phần còn lại sẽ càng nhiều, giống như kiểu 1 cái bánh mà càng phải chia ra cho nhiều người ăn thì phần ăn mỗi người càng bị nhỏ đi.
Vậy thì nếu ta xét các giá trị từ cuối về đầu, cứ mỗi lần xét lên vị trí mới, sau khi tính Max xong ta luôn cập nhật vị trí $j$ sao cho tại đó số trừ là nhỏ nhất có thể khi tính từ cuối cùng đến đó, và luôn cố gắng luôn cập nhật được như vậy. Như thế khi xét a[i] bất kỳ trừ cho (a[j] + (j - i) * k) thì kết quả sẽ là lớn nhất có thể, ta liên tục cập nhật lại Max và cứ thế xem như chỉ xét hết một lượt các giá trị a[i] của mảng là xong.
Ví dụ với $N = 10$ chẳng hạn, index từ cuối về đầu tức là từ 9 về 0. Ban đầu $j = 9$, $i$ từ 8. Xét a[i] - (a[j] + (j - i) * k) so sánh cập nhật lại Max. Rồi thì trước khi xét qua $i = 7$ thì ta kiểm tra vị trí $j$ hiện tại là 9 với vị trí $i = 8$ vừa xét, xem có thể phải cập nhật lại $j = 8$ không? Thì các bạn có thể thấy thế này: nếu a[9] hiện tại là 50 chẳng hạn đi ha, mà a[8] có giá trị nhỏ hơn 50, tức là a[8] <= a[9], thì có phải chắc chắn không cần suy nghĩ ngay mà cập nhật lại vị trí $j = 8$ không? Tại vì giá trị index đi lên càng nhỏ hơn, như thế giá trị $(j - i)$ càng nhỏ hơn: ví dụ cùng $i$ là 7 nhưng nếu $j = 9$ thì $(9 - 7) \times k$, so với $j = 8$ thì $(8 - 7) \times k$, chắc chắn với $j = 8$ kết quả sẽ ra nhỏ hơn; mà a[8] lại càng nhỏ hơn a[9], nghĩa là a[j] + (j - i) * k càng nhỏ hơn. Vì nhỏ hơn + nhỏ hơn sẽ càng nhỏ hơn. Và chắc chắn ta phải cập nhật lại $j$ để tiếp tục khi xét qua $i$ mới thì a[i] sẽ trừ cho số nhỏ nhất khúc sau nó để đảm bảo giá trị thu được là lớn nhất.
Vậy ta có thể thấy nếu giá trị a[i] vừa xét xong mà a[i] <= a[j] hiện tại thì ngay lập tức cập nhật $j = i$ trước khi xét qua $i$ mới. Còn trường hợp nếu a[i] > a[j] thì sao? Lúc này các bạn đừng vội nghĩ rằng không cần cập nhật $j$ nhé, nó tùy trường hợp đấy. Ví dụ nếu a[i] > a[j] nhưng khoảng cách giữa chúng (tức là $j - i$) nhân cho $k$ đủ bù đắp lại chênh lệch đó thì có thể ta vẫn sẽ cập nhật lại $j$. Ví dụ nếu $j$ hiện tại là index 8 và tại đó a[j] = 10. Nhưng nếu khi xét $i = 5$ tuy a[5] là 11 lớn hơn a[j] là 10 (lớn hơn 1), nhưng khoảng cách giữa chúng lúc này là $8 - 5 = 3$. Vậy các bạn nghĩ thử: nếu tiếp tục khi xét a[4] cần trừ cho (a[5] + (5 - 4) * k), tức là $(11 + k)$, so với a[4] cần trừ cho (a[8] + (8 - 4) * k), tức là $(10 + 4k)$. Thì so sánh giữa $(11 + k)$ với $(10 + 4k)$ thì thằng nào sẽ bé hơn? Lúc này còn tùy: ví dụ nếu $k = 0$ thì $(10 + 4k)$ sẽ nhỏ hơn, vì lúc này $10 < 11$. Nhưng nếu $k$ từ 1 trở lên, ví dụ $k = 1$ thì $(11 + k)$ sẽ nhỏ hơn vì $12 < 14$, hay $k = 2$ thì $13 < 18$.
Đó, vậy tổng quát nhất ta có thể cập nhật theo nguyên tắc: giả định cho rằng tiếp tục xét lên vị trí $i$ mới là $i - 1$, như thế so sánh giữa a[i] + (i - (i - 1)) * k, nếu nhỏ hơn a[j] + (j - (i - 1)) * k thì sẽ cập nhật $j = i$ hiện tại. Tức là sẽ cập nhật $j = i$ khi:
⇔ a[i] + k < a[j] + (j − i + 1) * k
⇔ a[i] + k < a[j] + (j − i) * k + k (cả 2 vế đều + k nên ta có thể bỏ đi)
⇔ a[i] < a[j] + (j − i) * k
⇔ a[i] − a[j] − (j − i) * k < 0
j = n - 1, Max = 0. Bắt đầu chạy vòng lặp xét $i$ từ $n - 2$ trở về 0, với mỗi giá trị a[i] tính x = a[i] - a[j] - (j - i) * k; nếu thấy x lớn hơn Max thì cập nhật lại Max bằng x. Sau đó kiểm tra nếu x < 0 thì cập nhật lại j = i. Rồi cứ thế xét qua $i$ tiếp theo. Sau khi chạy hết vòng lặp thì giá trị Max là kết quả số tiền lời lớn nhất có được.Chạy thử với ví dụ của đề (a = {10, 8, 5}, $K = 1$):
| i | a[i] | j hiện tại | x = a[i] − a[j] − (j − i)·K | Max | Cập nhật j |
|---|---|---|---|---|---|
| 1 | 8 | 2 (a[j] = 5) | 8 − 5 − (2 − 1)×1 = 2 | 2 | giữ j |
| 0 | 10 | 2 (a[j] = 5) | 10 − 5 − (2 − 0)×1 = 3 | 3 | giữ j |
Và một ví dụ dài hơn để thấy rõ lúc nào $j$ được cập nhật (a = {9, 12, 4, 7, 6, 8}, $K = 1$):
| i | a[i] | j hiện tại | x = a[i] − a[j] − (j − i)·K | Max | Cập nhật j |
|---|---|---|---|---|---|
| 4 | 6 | 5 (a[j] = 8) | 6 − 8 − (5 − 4)×1 = -3 | 0 | x < 0 ⇒ j = 4 |
| 3 | 7 | 4 (a[j] = 6) | 7 − 6 − (4 − 3)×1 = 0 | 0 | giữ j |
| 2 | 4 | 4 (a[j] = 6) | 4 − 6 − (4 − 2)×1 = -4 | 0 | x < 0 ⇒ j = 2 |
| 1 | 12 | 2 (a[j] = 4) | 12 − 4 − (2 − 1)×1 = 7 | 7 | giữ j |
| 0 | 9 | 2 (a[j] = 4) | 9 − 4 − (2 − 0)×1 = 3 | 7 | giữ j |
Kết quả 7: bán ở ngày có giá 12 (index 1), mua lại ở ngày có giá 4 (index 2), mượn 1 ngày nên trả lãi 1: $12 - 4 - 1 = 7$. Đúng bằng kết quả của cách vét cạn.
Em nhập giá các ngày và phí $k$ rồi bấm Tiếp để xem từng bước tham lam từ cuối về đầu. Với mỗi ngày bán $i$, hình vẽ "số trừ" a[j] + (j - i) * k của mọi ngày mua $j > i$: cột màu xanh đậm chính là ngày $j$ mà thuật toán đang giữ, và nó luôn là cột thấp nhất:
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);
long long n, k;
cin >> n >> k;
vector<long long> a(n);
for(int i = 0; i < n; ++i){
cin >> a[i];
}
long long j = n - 1;
long long Max = 0;
for(long long i = n - 2; i >= 0; --i){
long long x = a[i] - a[j] - (j - i) * k;
Max = max(Max, x);
if(x < 0){
j = i;
}
}
cout << Max;
return 0;
}n, k = map(int, input().split())
a = list(map(int, input().split()))
j = n - 1
Max = 0
for i in range(n - 2, -1, -1):
x = a[i] - a[j] - (j - i) * k
Max = max(Max, x)
if x < 0:
j = i
print(Max)Đánh giá độ phức tạp của cách làm này:
- Độ phức tạp không gian (Space Complexity): $O(N)$ với $N$ là số lượng phần tử của mảng.
- Độ phức tạp thời gian (Time Complexity): $O(N)$ của bước đọc dữ liệu từ input + $O(N)$ của bước xử lý. Tổng cộng sẽ là $O(2 \times N)$, thì theo quy tắc nhân Big O, nhân với hằng số ta có thể bỏ qua, vì thế có thể kết luận là $O(N)$.
Vậy với độ phức tạp ở trên, nếu tính chính xác luôn thì $2 \times N$ trong trường hợp xấu nhất $N$ là $10^6$ thì tổng cộng số lần lặp sẽ hết $2 \times 10^6$, tức là 2 triệu lần lặp. Trong khi đó cách làm trước đó số lần lặp là khoảng 500 tỷ lần lặp. Tính ra ít hơn gấp cả 250,000 lần. Trong khi đó các bạn đối chiếu code tính ra số lượng dòng code cũng ngang nhau thôi; không phải cách tối ưu hơn là phải code cực hơn, chỉ là cực hơn trong việc tính toán phân tích thôi, còn lại thì hiệu suất tốt hơn cả 250,000 lần, các bạn thấy kinh khủng chưa ^^ Và chắc chắn với 2 triệu thì yên tâm không thể bị TLE được nhé các bạn.
ACCách 3: duyệt từ đầu về cuối
Thực ra nếu muốn tối ưu hơn nữa cũng vẫn được luôn nha các bạn. Cụ thể như code ở trên chúng ta cần đến 2 vòng lặp, mỗi vòng lặp duyệt hết $N$ lần: vòng lặp đầu tiên là bước đọc dữ liệu và vòng lặp thứ 2 là bước xử lý, và phải cần đến mảng lưu trữ $N$ phần tử. Sẽ tối ưu nhất là khi chỉ cần 1 vòng lặp duy nhất, tức là kết hợp cả bước đọc dữ liệu và xử lý bên trong đó luôn. Và nếu đã như thế nghĩa là không cần phải dùng mảng lưu trữ $N$ phần tử, ta đọc dữ liệu vào thông qua vài biến đại diện rồi xử lý luôn. Đây là mức độ tối ưu nhất.
Thì cách làm ở trên là ta đi từ cuối về đầu; nếu giờ ta muốn xét từ đầu về cuối, thì với code ở trên, ta chỉ sửa lại khởi tạo j = 0, và trong vòng lặp khởi tạo i = 1; i < n; ++i. Rồi bên trong vòng lặp ở dòng đầu tiên tính x thì ta sẽ đổi chỗ index i, j cho nhau: chỗ nào là a[i] thì thay là a[j], chỗ nào là a[j] thì thay bằng a[i], j - i thì thay là i - j. Chỉ vậy thôi là được. Các bạn hãy thử suy nghĩ xem vì sao lại như vậy nhé, phần này mình dành cho các bạn suy ngẫm ^^
Source code để các bạn tham khảo nếu làm theo hướng này:
Xem code cách 3 (từ đầu về cuối)
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
long long n, k;
cin >> n >> k;
vector<long long> a(n);
for(int i = 0; i < n; ++i){
cin >> a[i];
}
long long j = 0;
long long Max = 0;
for(long long i = 1; i < n; ++i){
long long x = a[j] - a[i] - (i - j) * k;
Max = max(Max, x);
if(x < 0){
j = i;
}
}
cout << Max;
return 0;
}n, k = map(int, input().split())
a = list(map(int, input().split()))
j = 0
Max = 0
for i in range(1, n):
x = a[j] - a[i] - (i - j) * k
Max = max(Max, x)
if x < 0:
j = i
print(Max)ACCách 4: 1 vòng lặp duy nhất, không cần mảng
Vậy dựa theo code này thì giờ ta hãy gom 2 vòng lặp lại làm 1 vòng lặp duy nhất nào, và không sử dụng mảng luôn nhé. Như thế ta có thể tạo ra 2 biến đại diện là a, b, với a hiểu là thằng đứng trước, tương đương trong đoạn code trên chính là a[j], còn b là thằng đứng sau, tương đương trong đoạn code trên chính là a[i]; ta sẽ thay thế tụi nó lại là xong. Các bạn xem code dưới đây thay thế lại đây nhé:
Xem code cách 4 (1 vòng lặp)
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
long long n, k;
cin >> n >> k;
long long a, b;
long long Max = 0;
cin >> a;
long long j = 0;
for(long long i = 1; i < n; ++i){
cin >> b;
long long x = a - b - (i - j) * k;
Max = max(Max, x);
if(x < 0){
j = i;
a = b;
}
}
cout << Max;
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n, k = int(data[0]), int(data[1])
a = int(data[2]) # giá của "thằng đứng trước" (tương đương a[j])
j = 0
Max = 0
for i in range(1, n):
b = int(data[2 + i]) # giá của "thằng đứng sau" (tương đương a[i])
x = a - b - (i - j) * k
if x > Max:
Max = x
if x < 0:
j = i
a = b
print(Max)
main()Bản Python của cách này là mình viết thêm cho bạn nào code Python, cùng ý tưởng y như C++, chỉ khác là đọc toàn bộ input một lần cho nhanh.
Các bạn sẽ thấy đầu tiên ta cin >> a; để đọc dữ liệu số đầu tiên vào biến a trước. Rồi vòng lặp chạy $N - 1$ lần đọc còn lại để đọc vào biến b. Nếu thấy x < 0 thì cập nhật lại vị trí j = i thì cũng đồng thời cập nhật a = b. Vì trước đó do ta dùng mảng nên ta chỉ cần cập nhật lại index j thì khi gọi a[j] là lấy được ngay giá trị tại index đó; còn giờ đây ta cập nhật index j để nó đi tính khoảng cách ngày từ đó nhân với k, rồi thì phải cập nhật a = b là giá trị tương đương tại vị trí index j đó, do ta đã không còn mảng lưu trữ nữa.
Và đoạn code trên các bạn thấy không? Chỉ cần dùng 1 vòng lặp duy nhất lặp qua $N$ phần tử, kết hợp quá trình đọc dữ liệu và xử lý ngay lập tức luôn, và không cần dùng thêm bộ nhớ lưu trữ mảng, tức là độ phức tạp không gian là $O(1)$; còn độ phức tạp thời gian về mặt lý thuyết thì vẫn là $O(N)$ thôi, tức là cũng như cách trước đó, nhưng về mặt thực tế là nó tốt hơn hẳn nha các bạn, cụ thể là $O(N)$ thay vì trước đó là $O(2 \times N)$.
Nên nghĩa là cách trước đó trong trường hợp xấu nhất lặp 2 triệu lần thì cách này chỉ lặp 1 triệu lần, nhanh gấp 2 lần cách trước đó nữa, đồng nghĩa là nhanh gấp khoảng 500,000 lần cách vét cạn đầu tiên. Các bạn thấy tối ưu vi diệu chứ ^^
- 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