Max Triple

Nguồn: Bài tập trên nhóm lập trình Độ khó: Dễ Mảng Tìm max Tư duy

Đề bài

MAX TRIPLE

Cho mảng $A[\,]$ gồm $N$ số nguyên.

Nhiệm vụ của bạn là tìm tổng lớn nhất của bộ ba số trong mảng. Chú ý nếu sử dụng kỹ thuật sắp xếp, submit lời giải của bạn sẽ bị fail.

Ví dụ $A[\,] = \{1, 2, 3, 4, 5\}$, ta nhận được tổng lớn nhất của bộ ba số là $3 + 4 + 5 = 12$.

Input:

• Dòng đầu tiên đưa vào $T$ là số lượng bộ test.
• Những dòng tiếp theo, mỗi dòng đưa vào một test. Mỗi test là gồm hai dòng: dòng đầu tiên đưa vào $N$ là số lượng phần tử của mảng $A[\,]$; dòng tiếp theo đưa vào các phần tử $A[i]$ của mảng $A[\,]$.
• $T$, $N$, $A[i]$ thoả mãn ràng buộc: $1 \le T \le 100$; $1 \le N \le 10^6$; $-10^8 \le A[i] \le 10^8$.

Output:

• Đưa ra kết quả mỗi test theo từng dòng.

Ví dụ – input

2
7
1 2 3 0 -1 8 10
7
9 8 20 3 4 -1 0

Ví dụ – output

21
37

Lời mở đầu

Nay mình đi comment dạo trên một nhóm lập trình thấy bài này thú vị nè, có bạn đăng lên nhờ mọi người giúp. Bài nhìn thì dễ, nhưng cái hay nằm ở ràng buộc không được sắp xếp. Đây cũng từng là 1 câu hỏi phỏng vấn tuyển dụng của FPT đó anh em 😉. Phần hướng giải mình đã để ở comment bài viết, giờ mình viết lại chi tiết hơn, có hình minh hoạ và chạy tay để anh em dễ theo dõi.

Bạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì link bài đây nhé:

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ụ: test 1 là mảng 1 2 3 0 -1 8 10, ba số lớn nhất là $10, 8, 3$ nên tổng lớn nhất của bộ ba là $10 + 8 + 3 = 21$. Test 2 là mảng 9 8 20 3 4 -1 0, ba số lớn nhất là $20, 9, 8$ ⇒ $20 + 9 + 8 = 37$. Rõ ràng muốn tổng 3 số lớn nhất thì ta chọn 3 số lớn nhất của mảng (nếu có giá trị trùng nhau thì vẫn được chọn cả hai, vì là hai phần tử khác nhau). Đề ngầm hiểu mỗi mảng có ít nhất 3 phần tử.

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

Cách 13 lần duyệt tìm max · chưa tối ưuCách 21 vòng lặp, bộ 3 biến Max · O(1) bộ nhớ

Cách 1Duyệt 3 lần, mỗi lần lấy ra 1 số lớn nhất – O(3·N)

Không được sắp xếp thì cách nghĩ đầu tiên của nhiều anh em là: tìm số lớn nhất, đánh dấu lại; rồi tìm số lớn nhất trong các số chưa đánh dấu (chính là số lớn nhì); rồi làm thêm lần nữa để ra số lớn thứ ba. Có những anh em comment dùng đến 3 vòng lặp như vậy. Cách này vẫn ra kết quả đúng, độ phức tạp vẫn là $O(N)$ cho mỗi test, nhưng như thế chưa tối ưu:

• Phải duyệt mảng tới 3 lần.
• Phải lưu toàn bộ mảng (và cả mảng đánh dấu) ⇒ tốn bộ nhớ $O(N)$.

Source code để các bạn tham khảo nếu làm theo hướng này (mình viết thêm để anh em so sánh):

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

int a[1000005];
bool chon[1000005];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin >> t;
    while(t--) {
        int n;
        cin >> n;
        for(int i = 0; i < n; i++) {
            cin >> a[i];
            chon[i] = false;
        }
        int tong = 0;
        for(int lan = 1; lan <= 3; lan++) {
            int vt = -1;
            for(int i = 0; i < n; i++)
                if(!chon[i] && (vt == -1 || a[i] > a[vt]))
                    vt = i;
            chon[vt] = true;
            tong += a[vt];
        }
        cout << tong << "\n";
    }
    return 0;
}

import sys

def main():
    data = sys.stdin.buffer.read().split()
    p = 0
    t = int(data[p]); p += 1
    kq = []
    for _ in range(t):
        n = int(data[p]); p += 1
        a = list(map(int, data[p:p + n])); p += n
        chon = [False] * n
        tong = 0
        for lan in range(3):
            vt = -1
            for i in range(n):
                if not chon[i] and (vt == -1 or a[i] > a[vt]):
                    vt = i
            chon[vt] = True
            tong += a[vt]
        kq.append(str(tong))
    print('\n'.join(kq))

main()

Không gian$O(N)$

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

Cách 2Chỉ 1 vòng lặp với bộ 3 biến Max1, Max2, Max3 – O(N)

Cách tối ưu nhất là ta hoàn toàn có thể chỉ cần 1 vòng lặp duy nhất xét qua toàn bộ các phần tử của mảng là tìm ra được 3 số lớn nhất. Tư tưởng giải quyết như sau:

Ta tạo ra bộ 3 biến max1, max2, max3 tương ứng là 3 giá trị lớn nhất, nhì, ba. 3 biến này ban đầu sẽ khởi tạo giá trị là $-10^8 - 1$ để đảm bảo mọi giá trị trong mảng lần đầu tiên so sánh với nó sẽ luôn lớn hơn nó, để từ đó cập nhật lại giá trị mới vào các biến này (các phần tử trong mảng theo như đề bài cho có miền giá trị từ $-10^8$ đến $10^8$).

Thì giờ đây chỉ cần 1 vòng lặp duyệt qua từng phần tử $x$ của mảng và ta luôn cập nhật đồng thời bộ 3 biến Max. Để làm được điều đó thì như sau:

• Nếu $x \gt$ max1 (lớn hơn cả số lớn nhất): max1 phải trao lại giá trị hiện tại của nó cho max2. Nhưng nếu max2 muốn nhận giá trị từ max1 thì trước đó max2 cũng phải trao lại giá trị hiện tại của nó cho max3 rồi mới nhận được giá trị mới từ max1. Khi nào trao lại giá trị xong xuôi hết thì max1 mới nhận giá trị $x$.
• Ngược lại, nếu $x \gt$ max2: lúc này max2 phải trao lại giá trị hiện tại cho max3 rồi max2 mới được nhận $x$.
• Ngược lại, nếu $x \gt$ max3: max3 là thằng cuối trong bộ 3 rồi nên nó không cần trao giá trị lại cho thằng nào khác, chính nó nhận luôn $x$.

Thứ tự "trao giá trị" rất quan trọng

Phải trao từ dưới lên: max3 = max2; rồi max2 = max1; rồi mới max1 = x;. Nếu làm ngược (gán max1 = x trước) thì giá trị cũ của max1 bị ghi đè mất, không còn gì để trao cho max2 nữa. Ta luôn phải cập nhật đồng thời như thế để duy trì được bộ 3 biến này luôn là 3 giá trị lớn nhất trong các số đã xét.

Cứ như thế ta chỉ cần duyệt hết 1 lần vòng lặp và luôn kiểm tra cập nhật liên tục 3 biến max1, max2, max3 rồi sau cùng ta đã có được kết quả là max1 + max2 + max3.

Không cần cả mảng

Dễ dàng nhận ra một chỗ tối ưu hơn nữa khi ta chẳng cần dùng mảng để lưu trữ danh sách các số đầu vào. Bởi vì với tư tưởng này mỗi giá trị đầu vào ta chỉ xét qua 1 lần duy nhất nên ta đâu cần lưu trữ vào mảng làm gì, ta tạo 1 biến $x$ đọc giá trị từ input vào và xử lý so sánh thôi. Như thế này thì độ phức tạp không gian chỉ cần $O(1)$ chứ không cần $O(N)$ nếu phải dùng mảng lưu trữ.

Minh hoạ

Em nhập mảng rồi bấm Tiếp để xem bộ 3 biến Max "chuyền" giá trị cho nhau như thế nào (ô vàng là số $x$ đang xét):

Mảng A

Ví dụ nhanh:

Mình cũng code thử theo hướng này cho anh em tham khảo để nhìn thấy rõ hơn những gì mình đã phân tích:

#include <iostream>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while(t--) {
        int n;
        cin >> n;
        int max1, max2, max3;
        max1 = max2 = max3 = -100000001;
        while(n--) {
            int x;
            cin >> x;
            if(x > max1) {
                max3 = max2;
                max2 = max1;
                max1 = x;
            }
            else if(x > max2) {
                max3 = max2;
                max2 = x;
            }
            else if(x > max3) {
                max3 = x;
            }
        }
        cout << max1 + max2 + max3 << "\n";
    }
    return 0;
}

import sys

def main():
    data = sys.stdin.buffer.read().split()
    p = 0
    t = int(data[p]); p += 1
    kq = []
    for _ in range(t):
        n = int(data[p]); p += 1
        max1 = max2 = max3 = -100000001
        for k in range(p, p + n):
            x = int(data[k])
            if x > max1:
                max3 = max2
                max2 = max1
                max1 = x
            elif x > max2:
                max3 = max2
                max2 = x
            elif x > max3:
                max3 = x
        p += n
        kq.append(str(max1 + max2 + max3))
    print('\n'.join(kq))

main()

C++▶ Chạy tay từng dòng codeCách 2: 1 vòng lặp, cập nhật đồng thời bộ 3 biến max1, max2, max3.

Dữ liệu vào (stdin) – sửa thoải mái2 7 1 2 3 0 -1 8 10 7 9 8 20 3 4 -1 0

Dữ liệu mẫu:

1#include <iostream>

2using namespace std;

3

4int main() {

5 ios_base::sync_with_stdio(false);

6 cin.tie(0);

7 cout.tie(0);

8 int t;

9 cin >> t;

10 while(t--) {

11 int n;

12 cin >> n;

13 int max1, max2, max3;

14 max1 = max2 = max3 = -100000001;

15 while(n--) {

16 int x;

17 cin >> x;

18 if(x > max1) {

19 max3 = max2;

20 max2 = max1;

21 max1 = x;

22 }

23 else if(x > max2) {

24 max3 = max2;

25 max2 = x;

26 }

27 else if(x > max3) {

28 max3 = x;

29 }

30 }

31 cout << max1 + max2 + max3 << "\n";

32 }

33 return 0;

34}

ChậmVừaNhanhRất nhanh

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

• Không gian: chỉ dùng vài biến, không cần mảng ⇒ $O(1)$.
• Thời gian: $O(N)$ với từng bộ test và ta có $T$ bộ test ⇒ độ phức tạp tổng quát cả bài sẽ là $O(T \cdot N)$.

Không gian$O(1)$

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

10^8 số – ranh giới khá mong manh

Một số anh em cho rằng với giới hạn tối đa 100 bộ test và mỗi bộ test tối đa $10^6$ phần tử thì làm theo cách ở trên độ phức tạp $O(T \cdot N)$ là sẽ không AC được vì lúc này tối đa lên đến $10^2 \cdot 10^6 = 10^8$ số phải xét. Điều này là có cơ sở, bởi với phần lớn các hệ thống chấm bài tự động, nếu muốn an toàn thì ngưỡng tối đa chỉ nên ở mức $(3$ đến $5) \cdot 10^7$ phép tính nếu đề bài cho giới hạn 1 giây; vượt ngưỡng này thì khả năng TLE cao lắm. Tuy nhiên với những máy server chấm mạnh thì $10^8$ vẫn sẽ AC được.
Trong trường hợp bài này, $O(T \cdot N)$ là tối ưu nhất rồi, bởi vì chắc chắn nội bước đọc dữ liệu là đã phải xét qua đủ $T$ trường hợp và mỗi trường hợp đọc qua $N$ số là điều bắt buộc. Vậy nên một số anh em nói bài này muốn AC phải dùng thuật toán $O(T \cdot \sqrt{N})$ hay $O(T \cdot \log N)$ thì không thể được nha, vì bước đọc dữ liệu vào vốn nó đã là $O(T \cdot N)$ rồi.

Tăng tốc nhập xuất

Khi chạm ngưỡng $10^8$, anh em muốn AC thì các cú pháp nhập xuất nên dùng của C: scanf, printf thay vì cin, cout; kể cả bước xuống dòng cũng nên dùng "\n" thay vì endl cho chắc ăn. Hoặc anh em để 3 dòng đầu hàm main như trong code trên của mình (ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);) – có thể hiểu cơ bản là nó giúp tốc độ đọc ghi của C++ nhanh như bên C – rồi từ đó yên tâm dùng cin, cout.

Một hướng khác từ bình luận

Có bạn bình luận: không cho sort thì dùng heap (hàng đợi ưu tiên) giữ 3 phần tử; heap chỉ có 3 phần tử nên mỗi thao tác cũng xem như $O(1)$. Cách này cũng đúng, nhưng bộ 3 biến Max ở trên chính là một "heap 3 phần tử" viết tay, gọn và nhanh hơn.

Ghi chú của mình: code C++ và Python của cả 2 cách đã được kiểm tra với 500 bộ dữ liệu ngẫu nhiên (mỗi bộ 1 đến 5 test, có số trùng, số âm, cả giá trị biên $\pm 10^8$), so với code vét cạn thử mọi bộ ba – khớp hết. Với 1 test $N = 10^6$: cách 2 (C++) chạy khoảng 0.08 giây, cách 1 khoảng 0.13 giây. Với trường hợp xấu nhất $T = 100$, $N = 10^6$ (file input gần 1 GB), cách 2 (C++) trên máy mình mất khoảng 7 giây, gần như toàn bộ là thời gian đọc dữ liệu, đúng như phân tích ở trên: phần xử lý không thể nhanh hơn bước đọc dữ liệu. Bản Python chỉ phù hợp để tham khảo vì đọc $10^8$ số bằng Python chắc chắn quá thời gian.

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 😇