Nguồn: CLUE OJ – Chương 14: Cửa sổ trượt + Tham lamĐộ khó: DễTham lamĐếm phân phối
Đề bài
Để chúc mừng sinh nhật bạn Nhuận ngày 29/2, các bạn học sinh lớp 11A dự định tổ chức dã ngoại đến biển Nha Trang và lớp sẽ đi bằng taxi.
Các bạn trong lớp được chia thành $n$ nhóm, mỗi nhóm thứ $i$ gồm $s_i$ bạn $(1 \le s_i \le 4)$ và mỗi chiếc taxi chở tối đa 4 hành khách.
Vậy lớp 11A cần thuê ít nhất bao nhiêu chiếc taxi để chở các nhóm đi, với điều kiện là các bạn trong nhóm phải ngồi chung taxi (một taxi có thể chở một nhóm trở lên).
Dữ liệu nhập:
Dòng đầu chứa số nguyên $n$ $(1 \le n \le 10^5)$ – số lượng các nhóm học sinh.
Dòng thứ 2 chứa dãy số nguyên $s_1, s_2, \ldots, s_n$ $(1 \le s_i \le 4)$, cách nhau bởi dấu cách, với $s_i$ là số trẻ em trong nhóm thứ $i$.
Dữ liệu xuất: in 1 số nguyên duy nhất – số lượng tối thiểu taxi cần thiết để chở tất cả trẻ em đến nơi.
Giới hạn thời gian: 1 giây. Giới hạn bộ nhớ: 128 MB.
Ví dụ 1 – input
5
1 2 4 3 3
Ví dụ 1 – output
4
Ví dụ 2 – input
8
2 3 4 4 2 1 3 1
Ví dụ 2 – output
5
Giải thích ví dụ 1: các bạn có thể sắp xếp như sau: nhóm thứ 3 gồm 4 học sinh; nhóm thứ 4 gồm 3 học sinh; nhóm thứ 5 gồm 3 học sinh; nhóm thứ nhất và nhóm thứ 2 gồm 3 học sinh (1 và 2 học sinh). Vậy dữ liệu ra là 4.
Lời mở đầu
Đây là bài Taxi kinh điển (Codeforces 158B), một trong những bài tham lam đầu tiên mà bạn nào học thuật toán cũng gặp. Vì mỗi nhóm chỉ có 1 – 4 bạn nên thay vì quan tâm thứ tự các nhóm, ta chỉ cần đếm có bao nhiêu nhóm mỗi loại rồi ghép xe cho khéo. Mình sẽ giải bằng cách "mô phỏng xếp xe" trước, rồi rút gọn thành vài phép tính $O(n)$.
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.
Bạ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.
Gọi $c_1, c_2, c_3, c_4$ là số nhóm có 1, 2, 3, 4 bạn. Ta ghép xe theo thứ tự từ nhóm đông tới nhóm ít:
Nhóm 4 bạn: kín xe, không ghép được với ai → $c_4$ xe.
Nhóm 3 bạn: mỗi nhóm một xe (2 nhóm 3 bạn không ngồi chung được), xe còn đúng 1 chỗ → chở kèm 1 nhóm 1 bạn nếu còn. Thêm $c_3$ xe, $c_1$ giảm đi $\min(c_1, c_3)$.
Nhóm 2 bạn: cứ 2 nhóm ghép 1 xe → $\lfloor c_2 / 2 \rfloor$ xe. Nếu lẻ 1 nhóm thì nó đi 1 xe và chở kèm tối đa 2 bạn lẻ.
Nhóm 1 bạn còn lại: 4 bạn một xe → $\lceil c_1 / 4 \rceil$ xe.
Vì sao tham lam này tối ưu? Nhóm 4 và nhóm 3 thì chắc chắn mỗi nhóm cần riêng một xe (hai nhóm 3 bạn, hay 3 + 2, đều quá 4). Chỗ trống duy nhất cạnh nhóm 3 bạn chỉ vừa một nhóm 1 bạn, nên dùng nhóm 1 lấp vào là không phí. Sau đó chỉ còn nhóm 2 và nhóm 1: xếp hai nhóm 2 vào một xe là kín chỗ; phần lẻ thì nhóm 1 lấp nốt. Không có chỗ ngồi nào bị bỏ phí một cách "tránh được".
Em nhập số bạn của các nhóm rồi bấm Tiếp để xem từng loại nhóm được xếp lên xe:
Ví dụ nhanh:
Cách 1Mô phỏng xếp xe – O(n · k)
Cách tự nhiên nhất: sắp xếp các nhóm giảm dần, rồi lần lượt cho mỗi nhóm lên xe đầu tiên còn đủ chỗ; không có xe nào đủ chỗ thì gọi xe mới. Thứ tự giảm dần đảm bảo các nhóm lớn được xếp trước, nhóm nhỏ đi lấp chỗ trống – đúng như ý tưởng ở trên.
C++▶ Chạy tay từng dòng codeCách 1: sắp xếp giảm dần, mỗi nhóm lên xe đầu tiên còn đủ chỗ.
Dữ liệu mẫu:
con[t] là số chỗ trống của xe thứ $t$; vòng while tìm xe đầu tiên có con[t] >= s[i].
Không sắp xếp giảm dần là sai: ví dụ 1 1 3 3 xếp theo thứ tự đề thì hai bạn lẻ ngồi chung một xe, hai nhóm 3 bạn phải đi 2 xe riêng → 3 xe, trong khi đáp án là 2. Chạy thật bản không sắp xếp: 26/100 test đúng.
Mỗi nhóm có thể phải dò qua rất nhiều xe đã đầy (nhất là các xe chở nhóm 4 bạn) → tệ nhất $O(n^2)$.
Không gian$O(n)$
Thời gian$O(n \log n + n \cdot k)$, $k$ là số xe
Kết quả chạy thật: C++ đúng 80/100 test (test 1–80, chậm nhất 0.033 giây); test 81–100 bị quá thời gian. Python đúng 60/100 test (test 1–60, chậm nhất 0.058 giây); test 61–100 bị quá thời gian.
Cách 2Đếm rồi tính – O(n)
Không cần biết nhóm nào ở xe nào, chỉ cần đếm $c_1..c_4$ rồi làm 4 bước của ý tưởng.
C++▶ Chạy tay từng dòng codeCách 2: đếm số nhóm mỗi loại rồi ghép xe bằng công thức.
Dữ liệu mẫu:
max(0, c[1] - c[3]): nếu số bạn lẻ ít hơn số nhóm 3 thì bạn lẻ hết sạch, không âm.
(c[1] + 3) / 4 là cách viết làm tròn lên $\lceil c_1 / 4 \rceil$ chỉ bằng số nguyên.
Không gian$O(1)$
Thời gian$O(n)$
Kết quả chạy thật: C++ đúng 100/100 test, test chậm nhất chỉ 0.010 giây. Python đúng 100/100 test, test chậm nhất chỉ 0.048 giây.
Ghi chú của mình: cách 2 (C++) đúng 100/100 test, chậm nhất 0.010 giây; bản Python cũng đúng hết, chậm nhất 0.048 giây. Bài này rất hay để luyện thói quen "đếm thay vì duyệt": giá trị nhỏ (1 – 4) thì đếm số lần xuất hiện là đủ.
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 😇
Nguồn: CLUE OJ – Chương 11: Mảng 2 chiều & Map/SetĐộ khó: Trung bìnhTổng 8 ô kềmap đếm
Đề bài
Đề tuyển sinh lớp 10 trường Phổ thông Năng khiếu năm 2012 – 2013.
Bản đồ hành tinh Alpha được chia thành lưới ô vuông có kích thước gồm $m$ dòng và $n$ cột. Các dòng đánh số từ trên xuống dưới, các cột được đánh số từ trái qua phải và đều bắt đầu từ 1. Hai ô gọi là kề nhau nếu có chung cạnh hoặc chung đỉnh. Như vậy, mỗi ô kề với tối đa 8 ô.
Ô ở dòng $i$, cột $j$ có khả năng sản xuất $a_{i,j}$ đơn vị lương thực trong mỗi tháng với $0 \le a_{i,j} \le 10^6$.
Một khu dân cư được xây dựng trong một ô bất kỳ trên bản đồ sẽ được cung cấp lương thực sản xuất ra từ tất cả các ô kề với khu dân cư này. Bạn có danh sách $k$ khu dân cư dự kiến sẽ xây dựng, trong đó khu dân cư thứ $i$ có nhu cầu tiêu thụ $c_i$ đơn vị lương thực mỗi tháng $(1 \le i \le k)$. Để tối ưu hóa quy hoạch, khu dân cư thứ $i$ có thể được xây dựng tại ô mà tổng lương thực sản xuất của các ô kề đúng bằng $c_i$.
Yêu cầu: Với mỗi khu dân cư, hãy cho biết tồn tại hay không trên bản đồ một vị trí để xây dựng đảm bảo yêu cầu nêu trên.
Dữ liệu: vào từ tập tin văn bản CITY.INP
Dòng đầu tiên chứa 3 số nguyên dương $m$, $n$ và $k$ với $3 \le m, n \le 500$; $1 \le k \le 2000$.
Dòng thứ $i$ trong số $m$ dòng tiếp theo chứa $n$ số tự nhiên lần lượt là số lương thực sản xuất được của các ô trên dòng $i$ của bản đồ.
Dòng cuối cùng gồm $k$ số nguyên dương $c_1, c_2, \dots, c_k$ với $c_i$ là nhu cầu tiêu thụ lương thực của khu dân cư thứ $i$.
Kết quả: ghi ra tập tin văn bản CITY.OUT $k$ số tự nhiên 0 hoặc 1. Số thứ $i$ bằng 1 nếu có thể tìm được vị trí để xây dựng khu dân cư thứ $i$, trong trường hợp ngược lại số thứ $i$ bằng 0. Các số trên cùng một dòng cách nhau bởi đúng một ký tự khoảng trắng.
Giải thích ví dụ 1: khu dân cư 1 có thể xây được tại ô $(1, 1)$ (các ô kề có tổng $9 + 1 + 9 = 19$), khu dân cư 3 có thể xây được tại ô $(1, 2)$ (tổng $1 + 7 + 1 + 9 + 9 = 27$), còn hai khu dân cư 2 và 4 không có phương án xây.
Ghi chú của đề trên CLUE OJ: đề không nói rõ nhưng ta hiểu mỗi ô chỉ xây được 1 khu dân cư. Giả sử ví dụ trên là $k = 5$, có thêm 1 khu dân cư muốn xây với nhu cầu lại là 19, thì đáp án phải in ra 0, bởi vì chỉ có duy nhất 1 vị trí phù hợp có tổng lân cận bằng 19 và vị trí đó đã ưu tiên cho khu dân cư 1 (xét duyệt theo thứ tự từ trái qua phải). Tức là nếu có 5 khu dân cư cần xây là 19, 100, 27, 50, 19 thì đáp án là 1 0 1 0 0 (ví dụ 2).
Lưu ý: dữ liệu đọc ghi với file với tên file như trong đề bài (CITY.INP, CITY.OUT).
Ví dụ 1 – input
3 4 4
1 9 7 1
1 9 9 5
2 0 0 3
19 100 27 50
Ví dụ 1 – output
1 0 1 0
Ví dụ 2 – input
3 4 5
1 9 7 1
1 9 9 5
2 0 0 3
19 100 27 50 19
Ví dụ 2 – output
1 0 1 0 0
Lời mở đầu
Bài này nằm ở cả 2 chương Mảng 2 chiều và Map/Set: phần mảng 2 chiều là tính tổng 8 ô xung quanh một ô, phần map là "đếm xem mỗi tổng xuất hiện bao nhiêu lần" để trả lời nhanh $k$ câu hỏi. Ngoài ra bộ test còn giấu một cái bẫy rất hiểm ở 5 test cuối mà mình sẽ chỉ ra bên dưới – nhiều bạn code đúng thuật toán mà vẫn mất điểm vì nó.
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.
Bộ test có 100 test. Đề không chia subtask nhưng nhìn dữ liệu thì thấy rõ 3 nhóm:
Test
Số test
$m \times n$ lớn nhất
$k$ lớn nhất
$a_{i,j}$ lớn nhất
Số $c_i$ dài hơn 9 chữ số
Số kết quả 1
1 – 10
10
5 × 5
20
128933
0
0 – 6
11 – 95
85
500 × 500
2000
132768
0
951 – 1053
96 – 100
5
500 × 500
2000
132768
381 – 415 số (dài tới 50 chữ số)
787 – 839
Test 1 – 10: lưới rất nhỏ (tối đa $5 \times 5$), $k \le 20$.
Test 11 – 95: đều là lưới $500 \times 500$ với $k = 2000$ – lớn nhất theo đề. Giá trị $a_{i,j}$ thực tế chỉ tới khoảng $1{,}3 \cdot 10^5$, nên tổng 8 ô kề không vượt quá $8 \cdot 10^6$; khoảng một nửa số khu dân cư xây được.
Test 96 – 100: giống nhóm 2 nhưng có khoảng 400 số $c_i$ dài từ 10 đến 50 chữ số! Đề chỉ nói $c_i$ là "số nguyên dương", không giới hạn trên. Số 50 chữ số thì long long (tối đa khoảng $9{,}2 \cdot 10^{18}$, 19 chữ số) không chứa nổi.
Kết quả chạy thật của các cách giải bên dưới trên từng nhóm test (giới hạn 1 giây):
Nhóm
Test
Đặc điểm
Cách 1
Cách 2
Cách 3
Cách 3 đọc long long
Nhóm 1
1 – 10
lưới nhỏ, $k \le 20$
✔
✔
✔
✔
Nhóm 2
11 – 95
$500 \times 500$, $k = 2000$
✘ đúng 0/85 còn lại TLE
✔
✔
✔
Nhóm 3
96 – 100
như nhóm 2 + có $c_i$ hàng chục chữ số
✘ đúng 0/5 còn lại TLE
✔
✔
✘ đúng 0/5 còn lại WA
Ý tưởngMỗi ô có một "con số" cố định
Gọi $S_{i,j}$ là tổng lương thực của các ô kề với ô $(i, j)$. Con số này chỉ phụ thuộc vào bản đồ, không phụ thuộc khu dân cư. Khu dân cư thứ $t$ xây được ở ô $(i, j)$ khi và chỉ khi ô đó còn trống và $S_{i,j} = c_t$.
Vì mỗi ô chỉ xây được 1 khu và các ô có cùng $S$ thì "như nhau", ta chỉ cần biết còn bao nhiêu ô trống có tổng bằng $c_t$: còn thì in 1 và bớt đi 1 ô, hết thì in 0. Xét các khu dân cư theo đúng thứ tự cho trong đề (ai đến trước được ưu tiên trước).
Mẹo tính tổng 8 ô kề
Bao quanh bản đồ một viền ô bằng 0 (đánh số từ 1, mảng toàn cục có sẵn hàng 0, cột 0, hàng $m+1$, cột $n+1$ bằng 0). Khi đó ô ở góc hay ở mép đều tính chung một công thức: cộng cả khối $3 \times 3$ rồi trừ đi chính ô giữa – không cần if kiểm tra ra ngoài.
Em sửa bản đồ và danh sách $c$ rồi bấm Tiếp để xem từng bước: tính $S$ cho từng ô, đếm vào map, rồi lần lượt trả lời các khu dân cư:
Ví dụ nhanh:
Cách 1Mỗi khu dân cư, quét lại toàn bộ bản đồ
Cách tự nhiên nhất: với mỗi khu dân cư, duyệt mọi ô; ô nào còn trống thì tính tổng 8 ô kề bằng hàm tong8, bằng $c$ thì đánh dấu đã xây và dừng. Số $c$ mình đọc bằng xâu (lý do ở phần bẫy bên dưới), xâu dài hơn 9 chữ số thì gán $c = -1$ để chắc chắn không ô nào khớp.
C++▶ Chạy tay từng dòng codeCách 1: mỗi khu dân cư quét lại bản đồ, gọi tong8 cho từng ô.
Dữ liệu mẫu:
Đọc bản đồ mình gộp mỗi dòng 1 bước; lời gọi hàm tong8 gộp vào bước của dòng if.
Điều kiện !ok trong 2 vòng lặp giúp dừng ngay khi đã tìm được ô.
Mảng a khai báo toàn cục cỡ $505 \times 505$ nên hàng 0, cột 0, hàng $m+1$, cột $n+1$ đều bằng 0 – chính là viền 0.
Khu dân cư không xây được sẽ phải quét hết $m \cdot n = 250\,000$ ô, mỗi ô 9 phép cộng; nhân với $k = 2000$ là khoảng $4{,}5 \cdot 10^9$ phép tính – quá chậm.
Không gian$O(mn)$
Thời gian$O(k \cdot mn \cdot 9)$
Kết quả chạy thật: đúng 10/100 test (sai 90 test: TLE), test đúng chậm nhất 0.00 giây. Chỉ qua được 10 test nhỏ. Python: bản Python đúng 10/100 test (các test lớn quá thời gian), test đúng chậm nhất 0.03 giây.
Cách 2Tính trước S một lần
Tổng 8 ô kề của một ô không đổi, vậy tính sẵn vào mảng S một lần duy nhất. Mỗi khu dân cư vẫn quét bản đồ nhưng mỗi ô chỉ còn 1 phép so sánh.
C++▶ Chạy tay từng dòng codeCách 2: tính trước S[i][j] một lần, mỗi khu dân cư chỉ so sánh.
Dữ liệu mẫu:
Mỗi ô của mảng S mình gộp vòng lặp 3×3 thành 1 bước.
Dòng S[i][j] = -a[i][j] rồi cộng cả khối $3 \times 3$ chính là "cộng 9 ô, trừ ô giữa".
Không gian$O(mn)$
Thời gian$O(mn + k \cdot mn)$
Kết quả chạy thật: đúng 100/100 test, test đúng chậm nhất 0.54 giây. Bất ngờ chưa: cách này vẫn qua hết! Khoảng một nửa số khu dân cư không xây được nên phải quét trọn $250\,000$ ô, tổng cộng cỡ $1000 \cdot 250\,000 = 2{,}5 \cdot 10^8$ phép so sánh – rất nhẹ nên chạy kịp, nhưng chỉ còn cách giới hạn 1 giây khoảng một nửa. Nếu $k$ lớn hơn (chẳng hạn $10^5$) thì cách này chắc chắn quá thời gian, nên mình vẫn muốn các bạn nắm cách 3.
Cách 3Đếm bằng map – trả lời mỗi khu dân cư trong O(log)
Thay vì quét bản đồ cho từng khu dân cư, ta gom các ô theo giá trị $S$: cnt[s] = số ô còn trống có tổng 8 ô kề bằng $s$. Khu dân cư cần $c$: nếu cnt[c] > 0 thì in 1 và giảm cnt[c] đi 1, ngược lại in 0. Vì $S$ có thể lên tới $8 \cdot 10^6$ và chỉ có $250\,000$ giá trị nên dùng map rất tiện (dùng mảng đếm cỡ $8 \cdot 10^6$ cũng được nếu tin chắc vào giới hạn $a_{i,j}$).
C++▶ Chạy tay từng dòng codeCách 3: đếm số ô theo tổng 8 ô kề bằng map, mỗi khu dân cư trả lời trong O(log).
Dữ liệu mẫu:
Tính tổng 8 ô kề của mỗi ô mình gộp thành 1 bước ở dòng cnt[s]++.
Dùng cnt.find(c) thay vì cnt[c] để không vô tình chèn thêm khoá mới vào map khi $c$ không tồn tại.
Nếu xâu $c$ dài hơn 9 chữ số thì $c \ge 10^9 > 8 \cdot 10^6$, chắc chắn in 0 mà không cần đổi sang số.
Không gian$O(mn)$
Thời gian$O(mn \log(mn) + k \log(mn))$
Kết quả chạy thật: đúng 100/100 test, test đúng chậm nhất 0.31 giây. Full điểm. Python: bản Python đúng 100/100 test, test đúng chậm nhất 0.42 giây.
BẫyĐọc c bằng long long thì sao?
Hầu hết các bạn sẽ viết tự nhiên như sau:
long long c;
cin >> c; // c có 50 chữ số thì sao?
auto it = cnt.find(c);
...
Thuật toán y hệt cách 3, nhưng chạy thật trên bộ test thì: đúng 95/100 test (sai 5 test: WA), test đúng chậm nhất 0.30 giây. – sai đúng 5 test cuối 96 – 100, là các test có số $c_i$ khổng lồ.
Lý do: khi gặp một số 50 chữ số, cin >> c với long long bị tràn, C++ gán $c$ = giá trị lớn nhất của long long và bật cờ lỗi (failbit) cho cin. Từ lúc đó mọi lệnh cin phía sau đều bị bỏ qua và $c$ luôn bằng 0, nên toàn bộ các khu dân cư còn lại đều sai. Python thì không gặp chuyện này vì int của Python không giới hạn độ dài.
Bài học
Khi đề không ghi giới hạn trên của một số, hãy đọc nó bằng xâu rồi tự kiểm tra độ dài trước khi đổi sang số.
Ghi chú của mình: cách 3 (map) đạt 100/100 test của bộ test chính thức, cách 3 đọc long long chỉ đạt 95/100. Thời gian đo bằng CPU time, giới hạn 1 giây. Bài đọc/ghi file CITY.INP/CITY.OUT: đoạn if(fopen(...)) giúp code vừa chạy được với file, vừa chạy được với bàn phím khi tự thử.
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 😇
