Làm đẹp

Nguồn: CLUE OJ – Chương 14: Cửa sổ trượt + Tham lam Độ khó: Dễ Sắp xếp Cửa sổ trượt

Đề bài

Tối biểu diễn văn nghệ chào mừng 60 năm thành lập trường, nhóm bạn thân Mai, Cúc, Lan, Huệ sẽ đi đến tiệm trang điểm để làm đẹp. Trên menu lựa chọn của tiệm có $n$ kiểu trang điểm khác nhau, được đánh thứ tự từ kiểu $1$ đến kiểu $n$, mỗi kiểu trang điểm sẽ có độ ấn tượng lần lượt là $a_1, a_2, \dots, a_n$, độ ấn tượng của mỗi kiểu là duy nhất, không có hai kiểu nào có cùng độ ấn tượng với nhau. Đương nhiên là mỗi bạn đều muốn mình là người ấn tượng nhất trong buổi lễ, nhưng là nhóm bạn thân nên không thể để một người ấn tượng hơn người khác trong nhóm quá nhiều. Các bạn quyết định sẽ chọn mỗi người một kiểu trang điểm sao cho với cách chọn đó thì độ ấn tượng của từng người trong nhóm chênh lệch nhau là nhỏ nhất, và đương nhiên khi có nhiều sự lựa chọn thì sẽ chọn cách có độ ấn tượng càng cao càng tốt.

Yêu cầu: em hãy xác định độ chênh lệch ấn tượng lớn nhất giữa 4 kiểu mà các bạn lựa chọn và cho biết đó là 4 kiểu trang điểm nào.

Dữ liệu vào:

• Dòng đầu ghi số nguyên dương $n$ $(n \le 10^6)$.
• Dòng tiếp theo ghi $n$ số nguyên dương $a_1, a_2, \dots, a_n$ $(a_i \le 10^9)$ khác nhau đôi một.

Dữ liệu ra:

• Dòng đầu ghi độ chênh lệch ấn tượng lớn nhất giữa 4 kiểu trang điểm thoả mãn yêu cầu của các bạn.
• Dòng tiếp theo ghi 4 số nguyên theo thứ tự trong menu của 4 kiểu được chọn, ghi theo thứ tự tăng dần, mỗi số cách nhau một khoảng trắng.

Ràng buộc: 30% số test có $n \le 50$; 70% số test còn lại không ràng buộc gì thêm.

Ví dụ – input

6
3 4 7 5 10 8

Ví dụ – output

4
2 3 4 6

Giải thích: chọn kiểu trang điểm thứ 2, 3, 4, 6 có độ ấn tượng lần lượt là 4, 7, 5, 8, có độ chênh lệch lớn nhất giữa 2 kiểu là $8 - 4 = 4$. Để ý: chọn kiểu 1, 2, 3, 4 (độ ấn tượng 3, 4, 7, 5) cũng có chênh lệch $7 - 3 = 4$, nhưng nhóm 4, 5, 7, 8 ấn tượng hơn nên được chọn.

Lời mở đầu

"Độ chênh lệch lớn nhất giữa 4 kiểu" chính là $\max - \min$ của 4 số được chọn. Bài yêu cầu chọn 4 số có $\max - \min$ nhỏ nhất – một bài tham lam kinh điển: sắp xếp rồi chỉ xét 4 số liên tiếp. Cái bẫy thật sự của bài nằm ở câu "khi có nhiều sự lựa chọn thì chọn cách có độ ấn tượng càng cao càng tốt" – bộ test có tới 90/100 test có nhiều cách chọn cùng độ chênh lệch nhỏ nhất, chọn sai cách là mất gần hết điểm.

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 testÝ tưởng4 số liên tiếpCách 1Vét cạnCách 2Sắp xếp + cửa sổ

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

Bộ test có 100 test. Đề chỉ chia 2 mức (30% có $n \le 50$, 70% không giới hạn) và bộ test khớp đúng: 30 test đầu $n \le 50$, 70 test sau $n$ tăng dần $1000 \to 10^4 \to 10^5 \to 10^6$. Từ test 31 trở đi, độ ấn tượng trải gần hết khoảng $1 \dots 10^9$ nhưng với $n$ lớn thì gần như chắc chắn có 4 số liên tiếp nhau, nên chênh lệch nhỏ nhất thường chỉ là 3.

Test	n	Độ ấn tượng	Chênh lệch nhỏ nhất	Số test có nhiều cách chọn tốt nhất	Cách 1	Cách 2
1 – 30	5 – 50	1 – 60	3 – 11	20/30	30/30	30/30
31 – 40	1000	1 – 999706964	3 – 3	10/10	0/10	10/10
41 – 60	10000	1 – 999987313	3 – 3	20/20	0/20	20/20
61 – 80	100000	1 – 999999700	3 – 3	20/20	0/20	20/20
81 – 100	1000000	1 – 999999855	3 – 3	20/20	0/20	20/20

Điều đáng chú ý nhất: có tới 90/100 test có nhiều nhóm cùng đạt chênh lệch nhỏ nhất (test 90 có tới 79101 nhóm như vậy), nên quy tắc "chọn nhóm ấn tượng hơn" được kiểm tra rất kỹ.

Ý tưởngSắp xếp + cửa sổ 4 phần tử liên tiếp

Sắp xếp các độ ấn tượng tăng dần thành dãy $b_1 < b_2 < \dots < b_n$ (nhớ giữ lại số thứ tự gốc trong menu). Nhận xét then chốt:

Nhóm tốt nhất luôn là 4 số liên tiếp sau khi sắp xếp

Giả sử chọn 4 số có nhỏ nhất là $b_i$, lớn nhất là $b_l$ với $l > i + 3$. Thì 4 số liên tiếp $b_i, b_{i+1}, b_{i+2}, b_{i+3}$ có chênh lệch $b_{i+3} - b_i < b_l - b_i$ (các số khác nhau đôi một) – tốt hơn hẳn. Vậy chỉ cần xét $n - 3$ "cửa sổ" $[b_i, b_{i+3}]$ với chênh lệch $b_{i+3} - b_i$.

Khi nhiều cửa sổ có cùng chênh lệch nhỏ nhất, cửa sổ nằm sau thì có cả 4 số lớn hơn (vì dãy đã tăng dần) → ấn tượng hơn. Vậy khi duyệt từ trái sang phải, gặp chênh lệch bằng kết quả tốt nhất thì vẫn cập nhật (dùng dấu <= thay vì <).

Em sửa dãy độ ấn tượng rồi bấm Tiếp để xem cửa sổ 4 phần tử trượt trên dãy đã sắp xếp:

Độ ấn tượng a₁ … aₙ

Ví dụ nhanh:

Cách 1Vét cạn mọi bộ 4 – O(n⁴)

Với $n \le 50$ ta thử hết $\binom{n}{4}$ bộ 4 chỉ số $i < j < k < l$ (với $n = 50$ là $230\,300$ bộ). Mỗi bộ tính $\max - \min$; bộ tốt hơn nếu chênh lệch nhỏ hơn, hoặc bằng nhau mà số nhỏ nhất lớn hơn. Vì $i < j < k < l$ nên 4 chỉ số đã sẵn thứ tự tăng dần để in.

C++▶ Chạy tay từng dòng codeCách 1: thử mọi bộ 4 chỉ số i < j < k < l – O(n⁴).

Dữ liệu vào (stdin) – sửa thoải mái6 3 4 7 5 10 8

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

Với các vòng j, k, l mình chỉ dừng ở các dòng tính toán bên trong để số bước không quá dài.

1. Tại sao khi chênh lệch bằng nhau lại so số nhỏ nhất? Theo nhận xét ở phần ý tưởng, mọi nhóm tối ưu đều là 4 số liên tiếp trong dãy đã sắp xếp, nên nhóm có số nhỏ nhất lớn hơn thì cả 4 số đều lớn hơn.
2. max({a, b, c, d}) – hàm max/min của C++ nhận cả một danh sách trong ngoặc nhọn.
3. Bản Python dùng itertools.combinations sinh các bộ 4 theo thứ tự tăng dần, so sánh cặp (chênh lệch, -min).

Không gian$O(n)$

Thời gian$O(n^4)$

Kết quả chạy thật cách 1: bản C++ đúng 30/100 test – đủ 30 test có $n \le 50$, từ test 31 ($n = 1000$, cỡ $4 \cdot 10^{10}$ bộ) trở đi đều quá thời gian. Bản Python đúng 30/100 test.

Cách 2Sắp xếp + cửa sổ trượt – O(n log n)

Lưu mỗi kiểu thành cặp (độ ấn tượng, số thứ tự), sắp xếp theo độ ấn tượng, rồi trượt cửa sổ 4 phần tử.

C++▶ Chạy tay từng dòng codeCách 2: sắp xếp rồi trượt cửa sổ 4 phần tử, bằng nhau thì lấy cửa sổ sau – O(n log n).

Dữ liệu vào (stdin) – sửa thoải mái6 3 4 7 5 10 8

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. pair được sắp theo phần tử first trước nên sort sắp đúng theo độ ấn tượng, phần tử second (số thứ tự gốc) đi theo.
2. Dòng if(diff <= best) là chỗ quan trọng nhất: dấu <= giúp cửa sổ sau cùng trong số các cửa sổ tốt nhất được giữ lại. Mình thử đổi thành < (lấy cửa sổ đầu tiên) thì chỉ còn đúng 10/100 test.
3. 4 số thứ tự của cửa sổ chưa chắc đã tăng dần (ví dụ cửa sổ $4, 5, 7, 8$ có số thứ tự $2, 4, 3, 6$) nên phải sort(id, id + 4) trước khi in.
4. $n$ tới $10^6$ số nên nhớ ios::sync_with_stdio(0); cin.tie(0); để đọc nhanh.

Không gian$O(n)$

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

Kết quả chạy thật cách 2: bản C++ đúng 100/100 test, chậm nhất 0,22 giây. Bản Python đúng 80/100 test – riêng 20 test $n = 10^6$ (test 81 – 100) bị quá thời gian vì chỉ riêng đọc và sắp xếp $10^6$ số bằng Python đã mất hơn 1 giây.

Tổng kếtSo sánh 2 cách

Cách	Độ phức tạp	C++	Python	Mức đạt
1. Vét cạn bộ 4	$O(n^4)$	30/100	30/100	$n \le 50$ (30%)
2. Sắp xếp + cửa sổ	$O(n \log n)$	100/100	80/100	Toàn bộ (C++)

Ghi chú của mình: tất cả code trong bài đều được chấm thật trên toàn bộ 100 test chính thức (giới hạn 1 giây, đo bằng thời gian CPU). Hai điều cần nhớ: (1) bài "chọn $k$ số có max − min nhỏ nhất" thì sắp xếp rồi xét $k$ số liên tiếp; (2) đọc kỹ tiêu chí phụ khi bằng nhau – ở bài này nó quyết định tới 90% số điểm.

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 😇