Số lượng tối thiểu

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

Đề bài

Khu phố nhà Mai đã bị phong toả do mới phát sinh một số ca nhiễm Covid-19. Có $N$ người thuộc diện phải cách ly y tế. Để theo dõi mức độ phòng chống dịch của địa phương, cán bộ y tế đã thực hiện điều tra toàn bộ khu phố và cho kết quả là chỉ có đúng $a$ người trong số $N$ người này biết cách thực hiện tốt việc cách ly, những người không biết thì chắc chắn là sẽ không cách ly tốt. Do sơ suất nên cán bộ y tế chỉ ghi được danh sách $b$ người không thực hiện tốt cách ly, danh sách này có thể chưa đầy đủ nhưng cán bộ này đảm bảo rằng những người đã biết cách thực hiện mà không có tên trong danh sách là những người đã thực hiện tốt.

Yêu cầu: xác định số lượng tối thiểu và tối đa người đã thực hiện tốt việc cách ly.

Dữ liệu: gồm ba số nguyên $N$, $a$ và $b$ $(1 \le N \le 10^{18};\ 0 \le a, b \le N)$.

Kết quả: ghi ra hai số nguyên là số lượng tối thiểu và số lượng tối đa người thực hiện tốt việc cách ly.

Ví dụ – input

3 2 1

Ví dụ – output

1 2

Giải thích: có 3 người, 2 người biết cách (gọi là A, B), 1 người không biết (C), danh sách ghi 1 người cách ly không tốt. Nếu danh sách ghi tên C thì A, B đều cách ly tốt → 2 người. Nếu danh sách ghi tên A thì chỉ còn B cách ly tốt → 1 người. Vậy tối thiểu 1, tối đa 2.

Lời mở đầu

Bài ngắn gọn nhưng đọc đề hơi "xoắn". Mình sẽ chuyển câu chữ thành 4 nhóm người để thấy rõ đáp án, sau đó đi từ cách thử mọi khả năng (dễ nghĩ, nhưng chậm khi $N$ tới $10^{18}$) tới công thức $O(1)$ bằng lập luận tham lam. Chú ý $N$ tới $10^{18}$ nên mọi biến phải là long long.

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

Dành cho tất cả mọi ngườiNộp bài trên Codeforces

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.

Nộp bài trên Codeforces

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

Bộ test100 testÝ tưởng4 nhóm ngườiCách 1Thử mọi tCách 2Công thức

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

Bộ test có 100 test, đề không chia subtask; $N$ tăng dần theo thứ tự test, từ $1$ tới cỡ $8 \cdot 10^{17}$ (test 99). Mình chia thành 5 nhóm theo độ lớn của $N$ để xem cách 1 trụ được tới đâu:

Test	N	min(a, b) lớn nhất	Cách 1 C++	Cách 2 C++
1 – 20	$1$ … $99$	$14$	20/20	20/20
21 – 40	$549$ … $736.408$	$86.622$	20/20	20/20
41 – 60	$2,0·10^6$ … $8,8·10^9$	$32.235$	20/20	20/20
61 – 80	$3,1·10^10$ … $5,8·10^13$	$9,4·10^9$	19/20	20/20
81 – 100	$3,3·10^14$ … $7,9·10^17$	$8,2·10^13$	16/20	20/20

Trường hợp đặc biệt: 49 test có đáp án tối thiểu bằng 0 (danh sách đủ dài để "nuốt" hết người biết cách, $b \ge a$), 7 test có tối thiểu = tối đa (ví dụ $a = 0$ hoặc $b = 0$ hoặc $b = N$), và 6 test có $a + b > N$ – lúc này danh sách bắt buộc phải chứa người biết cách nên tối đa nhỏ hơn $a$.

Ý tưởng4 nhóm người

Mỗi người có 2 thuộc tính: biết / không biết cách cách ly, và có / không có tên trong danh sách. Gọi $t$ là số người biết cách mà vẫn có tên trong danh sách. Khi đó:

	Có tên trong danh sách	Không có tên	Tổng
Biết cách	$t$ (cách ly không tốt)	$a - t$ (cách ly tốt)	$a$
Không biết	$b - t$ (không tốt)	$N - a - b + t$ (không tốt)	$N - a$
Tổng	$b$	$N - b$	$N$

Người cách ly tốt chỉ có thể là ô "biết cách, không có tên": đúng $a - t$ người (người không biết thì chắc chắn không tốt, người có tên thì đã bị ghi là không tốt). Bốn ô trong bảng đều phải $\ge 0$:

Miền giá trị của t

$$\max(0,\ a + b - N) \;\le\; t \;\le\; \min(a, b)$$ Số người tốt $= a - t$ nhỏ nhất khi $t$ lớn nhất, lớn nhất khi $t$ nhỏ nhất.

Hiểu theo kiểu tham lam: muốn ít người tốt nhất thì "dồn" danh sách vào những người biết cách càng nhiều càng tốt ($t = \min(a, b)$); muốn nhiều người tốt nhất thì dồn danh sách vào những người không biết trước ($N - a$ chỗ), hết chỗ mới phải ghi lên người biết cách ($t = \max(0, a + b - N)$).

Em nhập $N, a, b$ nhỏ rồi bấm Tiếp để xem danh sách được "rải" lên từng người với mọi giá trị $t$:

N a b

Ví dụ nhanh:

Cách 1Thử mọi giá trị t – O(min(a, b))

Duyệt $t$ từ $0$ đến $\min(a, b)$; giá trị nào làm nhóm "không biết, có tên" vượt quá số người không biết ($b - t > N - a$) thì bỏ qua; còn lại cập nhật min/max của $a - t$.

C++▶ Chạy tay từng dòng codeCách 1: thử mọi số t người biết cách có tên trong danh sách – O(min(a, b)).

Dữ liệu vào (stdin) – sửa thoải mái3 2 1

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. Điều kiện b - t > N - a: danh sách còn $b - t$ người phải là người không biết, mà chỉ có $N - a$ người không biết.
2. Vòng lặp chạy $\min(a, b) + 1$ lần. Với $a, b$ cỡ $10^{12}$ trở lên thì không bao giờ chạy xong trong 1 giây.

Không gian$O(1)$

Thời gian$O(\min(a, b))$

Kết quả chạy thật cách 1: bản C++ đúng 95/100 test – nhanh hơn mình tưởng vì trong đa số test $a$ hoặc $b$ khá nhỏ (dù $N$ rất lớn); chỉ quá thời gian ở test 73, 89, 91, 98, 99 (cả $a$ và $b$ đều từ cỡ $10^{10}$ trở lên). Bản Python đúng 88/100 test (vòng lặp Python chậm hơn nên quá thời gian ở nhiều test hơn: 62, 73, 74, 76, 81, 84, 89, 90, 91, 96, 98, 99).

Cách 2Công thức tham lam – O(1)

Thay hai đầu mút của $t$ vào $a - t$:

Đáp án

Tối thiểu $= a - \min(a, b) = \max(0,\ a - b)$
Tối đa $= a - \max(0,\ a + b - N)$ $= \min(a,\ N - b)$

C++▶ Chạy tay từng dòng codeCách 2: công thức tham lam – O(1).

Dữ liệu vào (stdin) – sửa thoải mái3 2 1

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. 0LL: số 0 kiểu long long – hàm max của C++ đòi 2 tham số cùng kiểu, viết max(0, a - b) sẽ báo lỗi biên dịch.
2. Không có phép cộng $a + b$ nên không lo tràn số (dù $a + b \le 2 \cdot 10^{18}$ vẫn vừa long long).

Không gian$O(1)$

Thời gian$O(1)$

Kết quả chạy thật cách 2: bản C++ và bản Python đều đúng 100/100 test, mỗi test chạy trong tích tắc.

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

Cách	Độ phức tạp	C++	Python
1. Thử mọi t	$O(\min(a, b))$	95/100	88/100
2. Công thức	$O(1)$	100/100	100/100

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). Mẹo "kẻ bảng 2 × 2 rồi đặt ẩn cho một ô" dùng được cho rất nhiều bài đếm kiểu "có bao nhiêu người vừa A vừa B" – các bạn nhớ nhé.

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 😇