Sắp xếp các tổng

Nguồn: CLUE OJ – Chương 15: Hàng đợi ưu tiên Độ khó: Khá Hàng đợi ưu tiên Sắp xếp

Đề bài

Cho ba dãy số nguyên $A = (A_1, A_2, \ldots, A_X)$, $B = (B_1, B_2, \ldots, B_Y)$, $C = (C_1, C_2, \ldots, C_Z)$.

Thiết lập dãy số mới gồm $X \cdot Y \cdot Z$ phần tử là các tổng $A_i + B_j + C_t$ $(1 \le i \le X;\ 1 \le j \le Y;\ 1 \le t \le Z)$. Hãy xác định $K$ phần tử lớn nhất của dãy mới này.

Dữ liệu (nhập từ bàn phím/thiết bị vào chuẩn):

• Dòng 1: bốn số nguyên $X, Y, Z, K$ $(1 \le X, Y, Z \le 1000;\ 1 \le K \le \min(3000, X \cdot Y \cdot Z))$.
• Dòng 2: $X$ số nguyên $A_1, A_2, \ldots, A_X$ $(1 \le A_i \le 10^{10}\ \forall i)$.
• Dòng 3: $Y$ số nguyên $B_1, B_2, \ldots, B_Y$ $(1 \le B_j \le 10^{10}\ \forall j)$.
• Dòng 4: $Z$ số nguyên $C_1, C_2, \ldots, C_Z$ $(1 \le C_t \le 10^{10}\ \forall t)$. (Trong ảnh đề ghi nhầm là "Dòng 2".)

Kết quả (ghi ra màn hình/thiết bị ra chuẩn): dòng 1 gồm $K$ số nguyên theo thứ tự không tăng là $K$ phần tử lớn nhất của dãy nhận được.

Ràng buộc:

• $50\%$ số test đầu tiên có $1 \le X, Y, Z \le 100$;
• $50\%$ số test còn lại không có giới hạn gì thêm.

Ví dụ 1 – input

2 2 2 8
4 6
1 5
3 8

Ví dụ 1 – output

19 17 15 14 13 12 10 8

Ví dụ 2 – input

3 3 3 5
1 10 100
2 20 200
1 10 100

Ví dụ 2 – output

400 310 310 301 301

Giải thích ví dụ 1: $A = (4, 6)$, $B = (1, 5)$, $C = (3, 8)$ cho $8$ tổng: $6 + 5 + 8 = 19$, $4 + 5 + 8 = 17$, $6 + 1 + 8 = 15$, $6 + 5 + 3 = 14$, $4 + 1 + 8 = 13$, $4 + 5 + 3 = 12$, $6 + 1 + 3 = 10$, $4 + 1 + 3 = 8$. Ví dụ 2 cho thấy các tổng bằng nhau vẫn được in đủ ($310$ xuất hiện 2 lần).

Lời mở đầu

Có tới $10^9$ tổng nhưng ta chỉ cần $3000$ tổng lớn nhất. Bài này là ví dụ rất hay để thấy sức mạnh của hàng đợi ưu tiên: thay vì sinh hết rồi sắp xếp, ta chỉ "mở rộng" dần từ tổng lớn nhất, đúng kiểu thuật toán Dijkstra. Mình đi qua 3 cách – vét hết, ghép hai lần và hàng đợi ưu tiên – kèm kết quả chạy thật trên bộ test của CLUE.

Dành cho học viên · Ưu tiênNộp bài trên hệ thống CLUE OJ

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 OJ

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

Bộ test100 testCách 1vét hếtCách 2ghép 2 lầnÝ tưởngmở rộng dầnCách 3priority_queue

Bộ testBộ test chính thức có gì?

Test	X = Y = Z	K	Số tổng X·Y·Z	Giá trị lớn nhất
1 – 20	2 … 6	5 … 125	8 … 150	200
21 – 50	100	235 … 2.940	1.000.000	≈ $1,00 \cdot 10^{10}$
51 – 70	500	153 … 2.868	125.000.000	≈ $1,00 \cdot 10^{10}$
71 – 100	1.000	121 … 2.946	1.000.000.000	≈ $1,00 \cdot 10^{10}$

• Bộ test có 100 test và đúng như đề nói: test 1–50 có $X, Y, Z \le 100$ (test 1–20 rất nhỏ, test 21–50 đều là $100$), test 51–100 lớn: $500$ (test 51–70) và $1000$ (test 71–100).
• Từ test 21 các số lên tới gần $10^{10}$, tổng ba số gần $3 \cdot 10^{10}$ – vượt kiểu int, bắt buộc dùng long long.
• $K$ lớn nhất trong bộ test là 2.946 (đề cho tới $3000$).

Các subtask khớp với bộ test như sau (ô ghi số test đúng của bản C++ – chạy thật):

Subtask	Điều kiện	Các test	Cách 1 vét hết	Cách 2 ghép 2 lần	Cách 3 hàng đợi ưu tiên
1 (50%)	$X, Y, Z \le 100$	1 – 50	50/50	50/50	50/50
2 (50%)	$X, Y, Z \le 1000$	51 – 100	0/50	50/50	50/50

Cách 1Vét hết mọi tổng rồi sắp xếp

Cách tự nhiên nhất: ba vòng lặp sinh đủ $X \cdot Y \cdot Z$ tổng, sắp xếp giảm dần, in $K$ số đầu.

C++▶ Chạy tay từng dòng codeCách 1: sinh đủ X·Y·Z tổng, sắp xếp giảm dần, in K số đầu.

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

Không gian$O(XYZ)$

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

Kết quả chạy thật: bản C++ đúng 50/100 test (sai ở các test 51–100), lâu nhất 0.107s; bản Python đúng 50/100 test (sai/quá thời gian ở các test 51–100), lâu nhất 0.548s. Với $X = Y = Z = 100$ có $10^6$ tổng – nhẹ nhàng. Nhưng $500^3 = 1{,}25 \cdot 10^8$ tổng cần $1$ GB bộ nhớ, còn $1000^3 = 10^9$ tổng cần tới $8$ GB – vượt xa giới hạn 256 MB, chương trình bị dừng ngay (mình chạy với giới hạn bộ nhớ nên các test này báo lỗi chạy).

Cách 2Ghép hai lần, mỗi lần chỉ giữ K tổng

Nhận xét: nếu $A_i + B_j$ không nằm trong $K$ tổng $A + B$ lớn nhất thì đã có ít nhất $K$ tổng $A_{i'} + B_{j'}$ lớn hơn hoặc bằng nó; cộng cùng một $C_t$ vào thì được $K$ tổng ba số lớn hơn hoặc bằng $A_i + B_j + C_t$. Vậy $A_i + B_j + C_t$ không bao giờ cần tới, và ta chỉ cần giữ $K$ tổng $A + B$ lớn nhất.

1. Sinh $X \cdot Y \le 10^6$ tổng $A_i + B_j$, sắp xếp, giữ $K$ tổng lớn nhất.
2. Ghép $K$ tổng đó với $Z$ số của $C$: $K \cdot Z \le 3 \cdot 10^6$ tổng, sắp xếp, in $K$ tổng lớn nhất.

C++▶ Chạy tay từng dòng codeCách 2: giữ K tổng A + B lớn nhất rồi mới ghép với C.

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

Không gian$O(XY + KZ)$

Thời gian$O(XY \log(XY) + KZ \log(KZ))$

Kết quả chạy thật: bản C++ đúng 100/100 test, lâu nhất 0.362s; bản Python đúng 87/100 test (sai/quá thời gian ở các test 73–75, 79, 85, 87–89, 91, 93, 95–96, 99), lâu nhất 0.972s. Bản C++ đã full điểm, nhưng vẫn phải sinh và sắp xếp vài triệu số.

Ý tưởngHàng đợi ưu tiên: mở rộng dần từ tổng lớn nhất

Sắp xếp $A, B, C$ giảm dần. Khi đó tổng lớn nhất chắc chắn là $A_0 + B_0 + C_0$ (đánh số từ 0). Nếu tổng $(i, j, t)$ vừa được lấy ra là tổng lớn thứ $k$, thì tổng lớn thứ $k + 1$ chỉ có thể là một "hàng xóm" của những tổng đã lấy: $(i + 1, j, t)$, $(i, j + 1, t)$ hoặc $(i, j, t + 1)$. Lý do: với mọi bộ $(i, j, t)$ khác $(0, 0, 0)$, luôn có một bộ "đứng trước" nó (giảm 1 ở một chỉ số) có tổng lớn hơn hoặc bằng, nên bộ đó phải được lấy ra trước.

Thuật toán

• Cho bộ $(0, 0, 0)$ vào một hàng đợi ưu tiên (luôn lấy ra được tổng lớn nhất).
• Lặp $K$ lần: lấy bộ có tổng lớn nhất ra, in tổng, rồi cho 3 hàng xóm của nó vào hàng đợi.
• Một bộ có thể là hàng xóm của nhiều bộ (ví dụ $(1, 1, 0)$ là hàng xóm của cả $(0, 1, 0)$ và $(1, 0, 0)$), nên dùng một set đánh dấu bộ đã cho vào hàng đợi để không bị đếm trùng.

Mỗi lần lấy ra chỉ thêm tối đa 3 bộ nên hàng đợi có không quá $3K + 1$ phần tử – cực nhỏ so với $10^9$.

Em nhập ba dãy (mình sẽ tự sắp xếp giảm dần) và $K$, rồi bấm Tiếp để xem hàng đợi ưu tiên làm việc:

A: B: C: K =

Ví dụ nhanh:

Cách 3Cài đặt bằng priority_queue – O(K log K)

C++▶ Chạy tay từng dòng codeCách 3: hàng đợi ưu tiên lấy tổng lớn nhất, đẩy 3 hàng xóm, set chống trùng – O(K log K).

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. priority_queue<T> với T = tuple<ll, int, int, int>: tuple so sánh theo phần tử đầu trước nên đỉnh hàng đợi là bộ có tổng lớn nhất.
2. seen.insert(...).second trả về true nếu bộ chưa có trong set (vừa được thêm) – gọn hơn viết count rồi insert.
3. Các điều kiện i + 1 < X… đặt trước seen.insert để không chèn bộ ngoài phạm vi mảng.
4. Bản Python dùng heapq (heap nhỏ nhất) nên lưu số âm của tổng để lấy ra tổng lớn nhất trước.

Không gian$O(K)$

Thời gian$O(X \log X + Y \log Y + Z \log Z + K \log K)$

Kết quả chạy thật: bản C++ đúng 100/100 test, lâu nhất 0.005s; bản Python đúng 100/100 test, lâu nhất 0.043s.

Tổng kếtKết quả chạy thật trên bộ test

Cách	Ngôn ngữ	Đúng	Lâu nhất (test đúng)	Ghi chú
1. Vét hết X·Y·Z tổng	C++	50/100	0.107s	Vượt bộ nhớ ở test 51–100
	Python	50/100	0.548s	Quá thời gian / bộ nhớ ở test 51–100
2. Ghép 2 lần, giữ K tổng	C++	100/100	0.362s	Full điểm
	Python	87/100	0.972s	Quá 1 giây ở 13 test lớn
3. Hàng đợi ưu tiên	C++	100/100	0.005s	Full điểm
	Python	100/100	0.043s	Full điểm

Ghi chú của mình: thời gian trong bảng là thời gian CPU đo trên máy của mình, giới hạn 1 giây/test (cách 1 chạy với giới hạn bộ nhớ). Cách 3 nhanh hơn cách 2 khoảng trăm lần vì chỉ làm việc với khoảng $3K$ bộ chỉ số. Mẹo "lấy phần tử tốt nhất ra, đẩy các hàng xóm vào hàng đợi ưu tiên, đánh dấu để không trùng" dùng được cho rất nhiều bài "K phần tử lớn nhất / nhỏ nhất" khác.

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 😇