Kiểm tra

Nguồn: CLUE OJ Độ khó: Trung bình set Duyệt tập con (bitmask)

Đề bài

Kiểm tra

Cho dãy $A$ gồm $N$ số nguyên $A_1, A_2, \ldots, A_N$ và dãy $B$ gồm $M$ số nguyên $B_1, B_2, \ldots, B_M$.

Yêu cầu: Em hãy đếm xem có bao nhiêu số của dãy $A$ có giá trị bằng giá trị của một hoặc tổng của một số phần tử của dãy $B$.

Ví dụ: Cho dãy $A = (5, 6, 7, 2, 5, 8)$ và dãy $B = (1, 2, 3)$. Có 4 số trong dãy $A$ là $5, 6, 2, 5$ bằng giá trị của một phần tử hoặc bằng tổng của một số phần tử của dãy $B$.

Dữ liệu vào: đọc vào từ file văn bản CHECK.INP gồm:

• Dòng 1: ghi 2 số nguyên dương $N$ và $M$ $(N \le 10^5,\ M \le 15)$;
• Dòng 2: ghi $N$ số nguyên $A_1, A_2, \ldots, A_N$ $(|A_i| \le 10^9)$;
• Dòng 3: ghi $M$ số nguyên $B_1, B_2, \ldots, B_M$ $(|B_i| \le 10^9)$.

Các số trên cùng dòng cách nhau ít nhất 1 dấu cách.

Kết quả ra: ghi ra file văn bản CHECK.OUT một số duy nhất là kết quả của bài toán.

Giới hạn:

• Subtask 1: có 50% test tương ứng 2.0 điểm với $M = 1$;
• Subtask 2: có 25% test tương ứng 1.0 điểm với $N \le 10^3$ và $M \le 10$;
• Subtask 3: có 25% test tương ứng 1.0 điểm với $N \le 10^5$ và $M \le 15$.

Lưu ý: trên CLUE OJ bài này đọc/ghi file CHECK.INP / CHECK.OUT. Code bên dưới tự kiểm tra: có file thì đọc file, không có thì đọc bàn phím (để nộp Codeforces vẫn được).

Ví dụ – input

6 3
5 6 7 2 5 8
1 2 3

Ví dụ – output

4

Lời mở đầu

Bài này là bài 3 trong một đề thi học sinh giỏi. Chữ "tổng của một số phần tử" nghĩa là tổng của một tập con khác rỗng bất kỳ của $B$ (không cần liên tiếp). Vì $M \le 15$ nên $B$ chỉ có $2^{15} - 1 = 32767$ tập con khác rỗng – đủ ít để sinh hết. Phần còn lại là tra cứu thật nhanh: với mỗi $A_i$, hỏi "$A_i$ có nằm trong tập các tổng không?" – đúng sở trường của set.

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ộ test40 testÝ tưởngbitmaskCách 1M = 1Cách 2dò tuần tựCách 3set

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

Bộ test có 40 test, chia đúng theo 3 subtask của đề:

Test	N	M	$|A_i|$ lớn nhất	Tổng $|B_i|$ lớn nhất	Có số âm	Đáp án lớn nhất
1–20	5 … 99.991	1	33.767	12.642	14 test	101
21–30	10 … 973	3 … 9	999.999.999	8.999.999.934	7 test	597
31–40	19.965 … 99.969	12 … 15	999.999.949	13.999.999.136	9 test	54.994

Đối chiếu subtask của đề với test thật và số test đúng của từng cách:

Subtask	Đề ghi	Test	Thực tế	Cách 1 (M = 1)	Cách 2 (dò từng tổng)	Cách 3 (set)
1 (50%)	$M = 1$	1–20	đúng	20/20	20/20	20/20
2 (25%)	$N \le 10^3,\ M \le 10$	21–30	đúng: $N \le 973$, $M \le 9$	1/10	10/10	10/10
3 (25%)	$N \le 10^5,\ M \le 15$	31–40	đúng: $N$ tới 99.992, $M$ từ 12 đến 15	0/10	9/10	10/10

Chú ý tràn số và số âm

• Test 29 có các $B_i$ gần $10^9$, tổng của 9 số lên tới gần $9 \cdot 10^9$ – vượt int. Tổng tập con phải là long long.
• Nhiều test có số âm (cả trong $A$ lẫn $B$). Không thể làm "mảng đánh dấu" theo giá trị được, càng nên dùng set.
• $A$ có thể có các số trùng nhau, và mỗi số đều được đếm (trong ví dụ, số 5 được đếm 2 lần).

Ý tưởngMỗi tập con là một dãy bit

Mỗi tập con của $B$ ứng với một số mask từ $1$ đến $2^M - 1$: bit thứ $k$ của mask bằng 1 nghĩa là chọn $B_k$. Ví dụ $M = 3$, mask = 5 = 101₂ nghĩa là chọn $B_0$ và $B_2$.

Thuật toán

1. Duyệt mask từ $1$ đến $2^M - 1$, tính tổng các $B_k$ có bit $k$ bật, cho vào set<long long> tong (set tự bỏ các tổng trùng nhau).
2. Với mỗi $A_i$, nếu tong.count(A[i]) thì tăng biến đếm.

Em nhập 2 dãy rồi bấm Tiếp để xem sinh từng tập con và tra cứu từng $A_i$:

Dãy A: Dãy B:

Ví dụ nhanh:

Cách 1Chỉ so với B₁ – Subtask 1

Khi $M = 1$, "tổng của một số phần tử" chỉ có đúng một giá trị là $B_1$. Đếm số $A_i = B_1$ là xong.

C++▶ Chạy tay từng dòng codeCách 1: khi M = 1 chỉ cần đếm số a[i] bằng b[0].

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

Ví dụ "Test đề" có M = 3 nên cách 1 in ra kết quả sai – chỉ để em thấy giới hạn của cách này.

Không gian$O(N)$

Thời gian$O(N)$

Kết quả chạy thật: bản C++ đúng 21/40 test (sai kết quả ở test 21–29, 31–40), test đúng lâu nhất 0.01s; bản Python đúng 21/40 test (sai kết quả ở test 21–29, 31–40), test đúng lâu nhất 0.05s. Ăn trọn subtask 1 (50% điểm); test 30 "ăn may" vì đáp án bằng 0.

Cách 2Sinh mọi tổng, dò lần lượt – Subtask 1, 2

Sinh tất cả $2^M - 1$ tổng vào một vector, rồi với mỗi $A_i$ dò lần lượt cả vector xem có tổng nào bằng $A_i$ không.

C++▶ Chạy tay từng dòng codeCách 2: sinh 2^M − 1 tổng vào vector, mỗi a[i] dò lần lượt cả vector.

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. mask >> k & 1 lấy bit thứ $k$ của mask: dịch phải $k$ bit rồi lấy bit cuối.
2. 1 << m là $2^m$; mask chạy từ 1 để bỏ tập rỗng (tổng 0 của tập rỗng không được tính).
3. Gặp một tổng bằng $A_i$ thì break ngay – mỗi $A_i$ chỉ được đếm 1 lần dù có nhiều tập con cho cùng tổng.

Không gian$O(N + 2^M)$

Thời gian$O(M \cdot 2^M + N \cdot 2^M)$

Kết quả chạy thật: bản C++ đúng 39/40 test (quá thời gian ở test 39), test đúng lâu nhất 0.96s; bản Python đúng 30/40 test (quá thời gian ở test 31–40), test đúng lâu nhất 0.05s. Kết quả này tốt hơn mình nghĩ: trường hợp xấu nhất $N = 10^5$, $M = 15$ phải so sánh tới $10^5 \cdot 32767 \approx 3.3 \cdot 10^9$ lần, nhưng nhờ break sớm khi tìm thấy và phép so sánh rất nhẹ (máy tự tối ưu vòng lặp) nên chỉ gục ở test 39 – test mà các $A_i$ đều âm, hầu hết không tìm thấy nên phải dò hết cả vector. Test 36 cũng chạy tới 0.9–1.1 giây, chấm lại vài lần là có lúc trượt. Nói cách khác: cách này "ăn may" được gần hết subtask 3, nhưng không đảm bảo.

Cách 3Cho các tổng vào set – Full điểm

Chỉ cần đổi vector thành set: thay vì dò $2^M$ phần tử, ta tìm trong cây cân bằng mất $O(\log 2^M) = O(M)$ bước.

C++▶ Chạy tay từng dòng codeCách 3: cho mọi tổng tập con vào set, mỗi a[i] chỉ cần tong.count(a[i]).

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. tong.insert(s): tổng nào trùng thì set chỉ giữ một bản – không ảnh hưởng kết quả vì ta chỉ hỏi "có hay không".
2. tong.count(a[i]) trả về 1 nếu có, 0 nếu không.
3. Bản Python sinh tổng theo kiểu "quy hoạch": duyệt từng $x$ trong $B$, mỗi tổng cũ $s$ sinh thêm tổng mới $s + x$, cộng thêm tập chỉ gồm $x$. Cách này chỉ tạo tập con khác rỗng, nên vẫn đúng khi có tập con khác rỗng tổng bằng 0 (ví dụ $B$ có cả $3$ và $-3$).

Không gian$O(N + 2^M)$

Thời gian$O(M \cdot 2^M + N \cdot M)$

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

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

Cách	Ngôn ngữ	Đúng	Test đúng lâu nhất	Ghi chú
1. Chỉ so với $B_1$	C++	21/40	0.01s	Đúng subtask 1, test 30 đúng nhờ đáp án = 0
	Python	21/40	0.05s	Giống bản C++
2. Dò từng tổng $O(N \cdot 2^M)$	C++	39/40	0.96s	Quá thời gian test 39
	Python	30/40	0.05s	Quá thời gian test 31–40
3. set các tổng	C++	40/40	0.02s	Full điểm
	Python	40/40	0.05s	Full điểm (set)

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). Chỉ cần nhớ 2 điều: sinh tập con bằng bitmask (vì $M \le 15$) và tra cứu bằng set thay vì dò tuần tự. Tổng tập con phải dùng long long.

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 😇