Kiểm tra
Đề 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).
6 3
5 6 7 2 5 8
1 2 34Lờ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.
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 OJBạ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 CodeforcesLộ trình lời giải, bấm vào từng phần để nhảy tới:
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 |
- 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 = 1012 nghĩa là chọn $B_0$ và $B_2$.
- Duyệt
masktừ $1$ đến $2^M - 1$, tính tổng các $B_k$ có bit $k$ bật, cho vàoset<long long> tong(set tự bỏ các tổng trùng nhau). - 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$:
Cách 1Chỉ so với B1 – 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.
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.
mask >> k & 1lấy bit thứ $k$ củamask: dịch phải $k$ bit rồi lấy bit cuối.1 << mlà $2^m$;maskchạy từ 1 để bỏ tập rỗng (tổng 0 của tập rỗng không được tính).- Gặp một tổng bằng $A_i$ thì
breakngay – mỗi $A_i$ chỉ được đếm 1 lần dù có nhiều tập con cho cùng tổng.
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.
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".tong.count(a[i])trả về 1 nếu có, 0 nếu không.- 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$).
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) |
set thay vì dò tuần tự. Tổng tập con phải dùng long long.