Dãy Số 8
Đề bài
Yêu cầu: Tìm giá trị lớn nhất của biểu thức $a_i + a_j - a_k$ $(1 \le i < j < k \le n)$.
Dữ liệu:
- Dòng đầu tiên chứa số nguyên $n$ $(2 < n \le 10^6)$.
- Dòng thứ 2 là các số nguyên $a_1, a_2, \ldots, a_n$ $(|a_i| \le 10^9)$.
Kết quả: Một dòng duy nhất ghi giá trị lớn nhất của biểu thức.
Subtask:
- 30% số test đầu tiên có $n \le 400$.
- 30% số test tiếp theo có $n \le 10^4$.
- 20% số test tiếp theo có $n \le 10^5$.
- 20% số test còn lại có $n \le 10^6$.
7
8 2 4 -5 9 1 -320Giải thích ví dụ: chọn $i = 1$, $j = 5$, $k = 7$: $a_1 + a_5 - a_7 = 8 + 9 - (-3) = 20$. Không có bộ ba nào cho giá trị lớn hơ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 😇.
Link này chỉ học viên đã tham gia tổ chức mới vào được. Học viên nên ưu tiên nộp ở đây vì sẽ được chấm nhanh hơn.
Nộp bài trên CLUE OJBạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì dùng link này nhé. Chưa có tài khoản thì tạo tài khoản rồi đăng nhập nộp bài thử hen.
Nộp bài trên CodeforcesMình nói luôn bài này là bài "Dãy số 8". Nếu bạn nào vẫn chưa làm được thì trước tiên hãy thử làm bài "Dãy số 1" này: tìm giá trị lớn nhất của $a_j - a_i$ với $i < j$. Bài 1 có thể xem là bài con của bài hiện tại: nếu bạn làm được bài 1 thì sẽ có cơ sở để làm bài hiện tại, vì dạng của nó cũng tương đồng chỉ là làm rối lên một tí ^^. Nếu bài 1 bạn vẫn không làm được thì có thể xem qua bài giải của mình cho bài 1 để làm cơ sở cho bài hiện tại.
Từ đây trở xuống là mình bắt đầu phân tích giải bài hiện tại nha các bạn. Hãy đảm bảo là bạn đã cố gắng hết sức nhưng vẫn không được, hay đã tự làm được rồi, thì mới xem tiếp bài giải dưới đây của mình nhé.
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 bộ ba – O(N³)
Một cách làm cơ bản nhất dễ dàng nhìn ra đó là vét cạn xét hết tất cả các bộ 3 $(i, j, k)$ thoả mãn $i < j < k$ rồi tính $a[i] + a[j] - a[k]$, liên tục so sánh để sau cùng tìm ra kết quả lớn nhất trong tất cả các bộ 3 hợp lệ thì đó là đáp án.
Source code để các bạn tham khảo tư tưởng xử lý ở trên:
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
if(n < 3){
cout << 0;
}
else{
vector<long long> a(n);
for(int i = 0; i < n; ++i){
cin >> a[i];
}
long long Max = LLONG_MIN;
for(int i = 0; i < n; ++i){
for(int j = i + 1; j < n; ++j){
for(int k = j + 1; k < n; ++k){
Max = max(Max, a[i] + a[j] - a[k]);
}
}
}
cout << Max;
}
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0])
if n < 3:
print(0)
return
a = [int(x) for x in data[1:n + 1]]
Max = None
for i in range(n):
for j in range(i + 1, n):
for k in range(j + 1, n):
v = a[i] + a[j] - a[k]
if Max is None or v > Max:
Max = v
print(Max)
main()Giải thích một số chỗ trong code ở trên:
- 2 dòng đầu tiên của hàm main (
ios::sync_with_stdio(0); cin.tie(0);) 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é). Kinh nghiệm là trong các bài cần nhập xuất nhiều, như bài này input có thể lên đến 1 triệu số, 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 ngôn ngữ C thì chẳng cần mấy dòng đó, tuy nhiên thường khi code lập trình thi đấu 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é. - Để chắc ăn nhất mình chọn kiểu
long long(số nguyên 8 byte, lưu được đến hơn 9 tỷ tỷ) để yên tâm không sợ bị tràn số. Nếu theo thói quen dùng kiểuint(4 byte, chỉ đến hơn 2 tỷ) thì $a_i + a_j$ có thể lên tới $2 \cdot 10^9$, trừ thêm $a_k$ âm nữa là lên $3 \cdot 10^9$, vượt quá 2 tỷ là bị tràn và chương trình sai nha các bạn. - Vì mảng cần lưu trữ tối đa có thể lên đến 1 triệu số nên mình không dùng mảng tĩnh mà dùng kiểu
vector. Các bạn cứ nhớ một kinh nghiệm: mảng tĩnh khai báo trong hàm chỉ nên lưu tối đa ở mức $3 \cdot 10^5$ phần tử thôi, nếu vượt quá ngưỡng này nên dùng mảng động để tránh bị tràn bộ nhớ nhé. - Biến
Maxkhởi tạo ban đầu làLLONG_MIN, tức là giá trị nhỏ nhất của kiểulong long, để đảm bảo mọi giá trị lần đầu tiên so sánh với nó sẽ luôn lớn hơn nó mà cập nhật lạiMax. - Câu lệnh
Max = max(Max, a[i] + a[j] - a[k]);là cách viết gọn củaif(a[i] + a[j] - a[k] > Max){ Max = a[i] + a[j] - a[k]; }. Hàmmax(a, b)trả về giá trị lớn nhất trong 2 giá trị truyền vào, đây là hàm có sẵn trong C++. Tương tự ta cũng có hàmmin, về sau có gặp thì các bạn cũng hiểu hen.
Đánh giá độ phức tạp của cách làm này:
$O(N)$ của bước đọc mảng + $O(N^3)$ của thao tác xử lý. Theo quy tắc cộng Big-O sẽ lấy theo thành phần lớn nhất nên tổng quát kết luận sẽ là $O(N^3)$.
Trong trường hợp xấu nhất $N$ có thể lên đến $10^6$, như thế thì $N^3 = (10^6)^3 = 10^{18}$, vượt quá ngưỡng giới hạn 1 giây (khoảng $10^8$ phép tính) cả $10^{10}$ lần, tức là nếu trường hợp xấu nhất xảy ra thì phải chạy cả 10 tỷ giây ⇔ 317 năm mới ra kết quả nha các bạn :)) Vậy thì rõ là cách này không được rồi, chỉ ăn được subtask đầu $n \le 400$.
Ý tưởngQuy về bài "Dãy số 1"
Bài này cách giải quyết trọn vẹn nhất chỉ cần độ phức tạp thời gian là $O(N)$ thôi nha các bạn, và nó dùng phương pháp Quy Hoạch Động (Dynamic Programming) – thuộc thể loại quy hoạch động cơ bản. Mình sẽ cố gắng tiếp cận phân tích theo kiểu tư duy thông thường để những bạn nào chưa biết về quy hoạch động cũng sẽ lờ mờ hiểu được, còn bạn nào đã biết rồi thì đọc vào là hiểu ngay thôi.
Hồi đầu mình có nói bài "Dãy số 1" là bài con của bài "Dãy số 8" này. Lý do? Bài 1 chúng ta chỉ làm việc trên 2 số là $a[j] - a[i]$ để tìm ra hiệu lớn nhất. Còn bài này làm trên 3 số: $a[i] + a[j] - a[k]$. Các bạn nhìn xem nhé, nếu quy về:
thì có phải nó giống như bài 1 không? $(a[i] + a[j])$ ở bài này tương đương $a[j]$ của bài 1 (số bị trừ), và $a[k]$ của bài này tương đương $a[i]$ của bài 1 (số trừ). Rõ ràng bản chất nó cũng quy về dạng tìm cặp 2 số giống bài 1 thôi.
Khi mảng có thêm một phần tử
Đề yêu cầu $i < j < k$, tức là 3 vị trí đều phân biệt, nghĩa là mảng phải có tối thiểu 3 phần tử. Giả sử mảng có 3 phần tử a b c thì chỉ có 1 bộ 3 duy nhất là a b c và ta tính a + b - c.
Nếu mảng có thêm phần tử thứ 4, tức là a b c d, thì ta có các bộ 3 sau:
Ta sẽ thấy có thêm 3 bộ 3 mới là a b d, a c d, b c d. Điểm chung là phần tử d luôn đứng ở cuối cùng, theo lẽ dĩ nhiên là vậy. Nghĩa là biểu thức giờ đây sẽ luôn trừ cho d, còn trước đó sẽ là 2 phần tử cộng nhau.
Vậy mấu chốt: khi mảng có thêm 1 phần tử mới đứng ở cuối thì phần tử đó sẽ là phần tử bị trừ đi, tức nó chính là $a[k]$. Còn các phần tử trước đó sẽ lấy 2 phần tử cộng với nhau. Để biểu thức lớn nhất thì theo quy tắc toán học đơn giản, 2 phần tử cộng lại nên là 2 phần tử lớn nhất trong các phần tử đứng trước, vì 2 thằng lớn nhất cộng lại sẽ là tổng lớn nhất có thể. Việc trừ cho $a[k]$ là bắt buộc, nhưng ta đảm bảo biểu thức lớn nhất nhờ $a[i] + a[j]$ là 2 phần tử lớn nhất cộng nhau.
Vậy quy tắc là: quy ước chỉ số tính từ 1, ta bắt đầu xét từ $k = 3$ trở đi; trong các phần tử đứng trước ($1, 2, \ldots, k - 1$) lấy 2 phần tử lớn nhất cộng lại rồi trừ cho $a[k]$, so sánh với Max, lớn hơn thì cập nhật. Cứ thế lặp lại tới $k = N$ thì Max là kết quả. Chỉ cần duyệt qua 1 lần ⇒ độ phức tạp $O(N)$.
4 bước quy hoạch động
Còn bạn nào đã biết về quy hoạch động rồi thì mình trình bày 4 bước giải bài này, cũng y như những gì nói ở trên nhưng tóm gọn lại:
Bước 2 – Bài toán cơ sở: $F[1] = F[2] = 0$ (chưa đủ 3 phần tử thì đâu thể nào tính được biểu thức, không dùng tới).
Bước 3 – Đáp án: giá trị lớn nhất của các $F[i]$ với $i$ từ 3 đến $N$.
Bước 4 – Công thức truy hồi: $F[i] = \text{max1}(a[1..i-1])$ $+ \text{max2}(a[1..i-1]) - a[i]$, với max1 là giá trị lớn nhất, max2 là giá trị lớn nhì.
Em nhập dãy số rồi bấm Tiếp để xem với mỗi $k$, 2 số lớn nhất phía trước (tô xanh) cộng lại trừ đi $a[k]$ (tô đỏ):
Cách 2Quy hoạch động với Max1, Max2 – O(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;
if(n < 3){
cout << 0;
}
else{
vector<long long> a(n + 1);
for(int i = 1; i <= n; ++i){
cin >> a[i];
}
long long Max1 = max(a[1], a[2]);
long long Max2 = min(a[1], a[2]);
long long Max = Max1 + Max2 - a[3];
for(int i = 4; i <= n; ++i){
if(a[i - 1] > Max1){
Max2 = Max1;
Max1 = a[i - 1];
}
else if(a[i - 1] > Max2){
Max2 = a[i - 1];
}
Max = max(Max, Max1 + Max2 - a[i]);
}
cout << Max;
}
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0])
if n < 3:
print(0)
return
a = [0] + [int(x) for x in data[1:n + 1]] # chỉ số từ 1
Max1 = max(a[1], a[2])
Max2 = min(a[1], a[2])
Max = Max1 + Max2 - a[3]
for i in range(4, n + 1):
x = a[i - 1]
if x > Max1:
Max2 = Max1
Max1 = x
elif x > Max2:
Max2 = x
Max = max(Max, Max1 + Max2 - a[i])
print(Max)
main()Giải thích một số chỗ trong code ở trên:
- Tuy trong 4 bước quy hoạch động mình có gọi $F[i]$, nghĩa là cần thêm bộ nhớ phụ là mảng $F$, nhưng thực tế việc dùng mảng $F$ là không cần thiết nha các bạn. Sau cùng ta chỉ cần Max của các $F[i]$, nên không nhất thiết lưu trữ từng $F[i]$ rồi duyệt lại tìm Max, mà có thể vừa tính vừa so sánh cập nhật
Maxluôn. - Biến
Max1lưu giá trị lớn nhất vàMax2lưu giá trị lớn nhì trong tất cả các giá trị trước vị trí $i$. Lưu ý cả 2 biến có thể mang giá trị giống nhau nếu giá trị lớn nhất xuất hiện nhiều hơn 1 lần. Ban đầuMax1 = max(a[1], a[2])là số lớn hơn trong 2 số đầu mảng,Max2 = min(a[1], a[2])là số nhỏ hơn. Biến đáp ánMaxkhởi tạo bằngMax1 + Max2 - a[3]. - Vòng lặp duyệt từ $i = 4$ đến $N$. Với mỗi $a[i]$ mới thì trước hết cập nhật
Max1,Max2với giá trị $a[i - 1]$. Bởi ví dụ khi $i = 4$ thì $a[i - 1]$ là $a[3]$: ban đầu ta chỉ xétMax1,Max2với 2 phần tử đầu là $a[1], a[2]$ thì giờ phải xét tiếp với $a[3]$. - Cách cập nhật: nếu $a[i - 1]$ lớn hơn
Max1thì chắc chắnMax1phải cập nhật lại bằng $a[i - 1]$ để khẳng định vị thế lớn nhất của mình. Nhưng trước khi cập nhậtMax1thì gán giá trịMax1hiện tại qua choMax2, để đảm bảoMax2là giá trị lớn nhất theo sauMax1, tứcMax2 <= Max1và không có giá trị nào xen giữa tụi nó. Còn nếu $a[i - 1]$ không lớn hơnMax1nhưng lớn hơnMax2thì đơn giản cập nhậtMax2 = a[i - 1]. - Cập nhật xong
Max1,Max2thì tínhMax1 + Max2 - a[i](chính là $F[i]$) và so sánh cập nhật lạiMax. Kết thúc vòng lặp thìMaxlà giá trị biểu thức lớn nhất.
Đánh giá độ phức tạp của cách làm này:
$O(N)$ của bước đọc mảng + $O(N)$ của thao tác xử lý, cả thảy là $O(2N)$. Theo quy tắc Big-O khi nhân với hằng số ta có thể bỏ qua nên tổng quát lại là $O(N)$ các bạn nha.
Với độ phức tạp $O(N)$ thì yên tâm không sợ bị TLE rồi, vì nó là độ phức tạp tốt nhất trong những bài tập có dùng đến mảng $N$ phần tử: chắc chắn cơ bản nhất là phải đọc mảng vào chương trình rồi mới có dữ liệu đi xử lý, mà việc đọc $N$ phần tử đã tốn $O(N)$ rồi. Bài này $N$ tối đa $10^6$, ít hơn cả $10^8$ (ngưỡng khoảng 1 giây) tới 100 lần, nên xét lý thuyết cách này chỉ cần khoảng 0.01 giây là ra kết quả.
Cách 3Không cần mảng – bộ nhớ O(1)
Đến đây thì đã được rồi, nhưng mình trình bày luôn cho các bạn một cách tối ưu hơn nữa: không cần bộ nhớ cho mảng $a$, tức là độ phức tạp không gian chỉ còn $O(1)$ với vài biến đơn lẻ. Độ phức tạp thời gian vẫn là $O(N)$ nhưng bản chất chỉ cần 1 vòng lặp duy nhất kết hợp cả quá trình đọc dữ liệu và xử lý. Chi tiết các bạn xem code dưới đây của mình nhé:
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
if(n < 3){
cout << 0;
}
else{
long long a, b, c;
cin >> a >> b >> c;
long long Max1 = max(a, b);
long long Max2 = min(a, b);
long long Max = Max1 + Max2 - c;
n -= 3;
while(n--){
if(c > Max1){
Max2 = Max1;
Max1 = c;
}
else if(c > Max2){
Max2 = c;
}
cin >> c;
Max = max(Max, Max1 + Max2 - c);
}
cout << Max;
}
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0])
if n < 3:
print(0)
return
it = map(int, data[1:n + 1]) # đọc lần lượt từng số, không tạo mảng số nguyên
a, b, c = next(it), next(it), next(it)
Max1 = max(a, b)
Max2 = min(a, b)
Max = Max1 + Max2 - c
for nxt in it:
if c > Max1:
Max2 = Max1
Max1 = c
elif c > Max2:
Max2 = c
c = nxt
if Max1 + Max2 - c > Max:
Max = Max1 + Max2 - c
print(Max)
main()Tư tưởng xử lý y như mình đã phân tích với cách làm trước đó, chỉ là tối ưu lại không cần dùng mảng cũng như gộp chung vòng lặp đọc dữ liệu + xử lý. Ở đây biến c đóng vai trò $a[i - 1]$ khi cập nhật Max1, Max2, sau đó cin >> c đọc số mới thì c lại đóng vai trò $a[i]$ để trừ đi. Các bạn hiểu được cách làm trước đó rồi thì cách này mình tin sẽ không có gì khó hiểu cả.
Đến đây các bạn thấy việc luyện tư duy giải thuật quan trọng chứ? Từ cách làm ban đầu cần dùng mảng và độ phức tạp $O(N^3)$, trường hợp xấu nhất phải đến 317 năm mới chạy ra kết quả, thì với cách làm sau này không cần dùng mảng và cũng trường hợp xấu nhất đó nhưng chỉ khoảng 0.01 giây là ra kết quả thôi, chớp mắt cái là xong. Trong khi đối chiếu lại các bạn sẽ thấy code không dài thêm bao nhiêu so với cách ban đầu cả. Thế mới thấy luyện tốt kiến thức giải thuật sẽ hay thế nào đúng không 😊
Nhận xét
Đăng nhận xét