Phần thưởng cuối năm (Đề tự luyện HSG Tin 12 – Bài 3)
Đề bài
Phần thưởng cuối năm. Nhà sách có $N$ món quà, món thứ $i$ giá $a_i$ đồng. Thầy Sơn cần chọn đúng $K$ món khác nhau sao cho tổng giá nằm trong đoạn $[L, R]$. Đếm số cách chọn (hai cách khác nhau nếu khác nhau ít nhất một món, kể cả khi các món cùng giá).
Dữ liệu vào: dòng đầu $N, K, L, R$ ($1 \le K \le N \le 40$, $0 \le L \le R \le 4 \cdot 10^{10}$); dòng hai $a_1, \ldots, a_N$ ($1 \le a_i \le 10^9$).
Kết quả: số cách chọn.
- Subtask 1 (30%): $N \le 20$.
- Subtask 2 (30%): $a_i \le 1000$.
- Subtask 3 (40%): không có ràng buộc gì thêm.
6 3 220000 260000
70000 85000 113000 28000 90000 950006Các cách hợp lệ (số thứ tự món): $\{1, 2, 5\}$: $245000$; $\{1, 2, 6\}$: $250000$; $\{1, 5, 6\}$: $255000$; $\{2, 3, 4\}$: $226000$; $\{3, 4, 5\}$: $231000$; $\{3, 4, 6\}$: $236000$.
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é. Bộ test có chia subtask và có cả những test "bẫy", nên code đúng ý tưởng nhưng sai chi tiết nhỏ cũng sẽ bị trừ điểm đó.
Nộp bài Phần thưởng cuối nămLời mở đầu
Nhìn giới hạn $N \le 40$ là thấy "mùi" của bài: nhỏ quá để nghĩ tới thuật toán đa thức, nhưng $2^{40} \approx 1{,}1 \cdot 10^{12}$ tập con thì cũng không thể vét hết. Con số $40$ gợi ý một kỹ thuật kinh điển: chia đôi tập (meet in the middle) – mỗi nửa chỉ có $2^{20} \approx 10^6$ tập con, vét thoải mái.
Nhận xét. Chia $N$ món thành nửa đầu và nửa sau. Một cách chọn $K$ món = (một tập $c_1$ món ở nửa đầu, tổng $s$) ghép với (một tập $c_2 = K - c_1$ món ở nửa sau, tổng $t$), và điều kiện trở thành $L - s \le t \le R - s$. Vậy nếu với mỗi số món $c$, ta có sẵn danh sách tổng của nửa sau đã sắp xếp, thì với mỗi $s$ chỉ cần chặt nhị phân để đếm số $t$ nằm trong đoạn $[L - s, R - s]$.
Hình 1. Ví dụ của đề chia thành hai nửa $3$ món. Ghép "$c_1$ món nửa đầu" với "$3 - c_1$ món nửa sau" và đếm bằng một đoạn giá trị.
Cách 1Vét mọi tập con – O(2N·N) · 30%
Mỗi tập con ứng với một số mask từ $0$ tới $2^N - 1$: bit $i$ bật nghĩa là chọn món $i$. Với $N \le 20$ có khoảng một triệu mask. Bỏ qua mask không có đúng $K$ bit $1$ (__builtin_popcount), cộng tổng giá các món được chọn rồi kiểm tra $L \le s \le R$.
long long.(Bản Python tính tổng của mọi mask bằng mẹo "bỏ bit thấp nhất": tổng của mask = tổng của mask bỏ bit thấp nhất + giá món ứng với bit đó – mỗi mask chỉ tốn $O(1)$.)
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, k;
long long L, R;
cin >> n >> k >> L >> R;
vector<long long> a(n);
for (auto& x : a) cin >> x;
long long ans = 0;
for (int mask = 0; mask < (1 << n); mask++) { // moi tap con cua N mon
if (__builtin_popcount(mask) != k) continue; // phai chon dung k mon
long long s = 0;
for (int i = 0; i < n; i++)
if (mask >> i & 1) s += a[i];
if (L <= s && s <= R) ans++;
}
cout << ans << "\n";
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0]); k = int(data[1]); L = int(data[2]); R = int(data[3])
a = [int(x) for x in data[4:4 + n]]
# sums[mask] = tong gia cac mon trong mask, cnt[mask] = so mon
sums = [0] * (1 << n)
cnt = [0] * (1 << n)
ans = 0
for mask in range(1, 1 << n):
low = mask & (-mask) # bit thap nhat
i = low.bit_length() - 1
sums[mask] = sums[mask ^ low] + a[i]
cnt[mask] = cnt[mask ^ low] + 1
if cnt[mask] == k and L <= sums[mask] <= R:
ans += 1
print(ans)
main()Cách 2Giá nhỏ: cái túi đếm số cách – O(N·K·S) · 60%
Khi $a_i \le 1000$, tổng giá của mọi món không quá $S = 40 \cdot 1000 = 40000$. Gọi $f[c][s]$ là số cách chọn $c$ món (trong các món đã xét) có tổng giá đúng bằng $s$. Ban đầu $f[0][0] = 1$. Xét lần lượt từng món giá $x$: mỗi cách chọn $c - 1$ món tổng $s - x$ thêm món này thành một cách chọn $c$ món tổng $s$:
$$f[c][s] \mathrel{+}= f[c - 1][s - x].$$Duyệt $c$ và $s$ giảm dần để mỗi món chỉ được dùng một lần (giống cái túi 0/1). Đáp án là $\sum_{L \le s \le R} f[K][s]$.
long long cho mảng đếm và cho đáp án.Code gộp luôn Cách 1 khi $N \le 20$:
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, k;
long long L, R;
cin >> n >> k >> L >> R;
vector<long long> a(n);
for (auto& x : a) cin >> x;
long long ans = 0;
if (n <= 20) { // Cach 1: vet moi tap con
for (int mask = 0; mask < (1 << n); mask++) {
if (__builtin_popcount(mask) != k) continue;
long long s = 0;
for (int i = 0; i < n; i++) if (mask >> i & 1) s += a[i];
if (L <= s && s <= R) ans++;
}
} else { // a[i] <= 1000: cai tui dem so cach
int S = 0;
for (auto x : a) S += x;
// f[c][s] = so cach chon c mon co tong gia dung bang s
vector<vector<long long>> f(k + 1, vector<long long>(S + 1, 0));
f[0][0] = 1;
int top = 0; // tong gia cac mon da xet
for (int i = 0; i < n; i++) {
top += a[i];
for (int c = min(i + 1, k); c >= 1; c--) // duyet nguoc: moi mon chon toi da 1 lan
for (int s = top; s >= a[i]; s--)
f[c][s] += f[c - 1][s - a[i]];
}
for (int s = 0; s <= S; s++)
if (L <= s && s <= R) ans += f[k][s];
}
cout << ans << "\n";
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0]); k = int(data[1]); L = int(data[2]); R = int(data[3])
a = [int(x) for x in data[4:4 + n]]
ans = 0
if n <= 20: # Cach 1: vet moi tap con
sums = [0] * (1 << n); cnt = [0] * (1 << n)
for mask in range(1, 1 << n):
low = mask & (-mask); i = low.bit_length() - 1
sums[mask] = sums[mask ^ low] + a[i]
cnt[mask] = cnt[mask ^ low] + 1
if cnt[mask] == k and L <= sums[mask] <= R:
ans += 1
else: # a[i] <= 1000: cai tui dem so cach
S = sum(a)
# f[c][s] = so cach chon c mon co tong gia dung bang s
f = [[0] * (S + 1) for _ in range(k + 1)]
f[0][0] = 1
top = 0 # tong gia cac mon da xet
for i in range(n):
x = a[i]
top += x
for c in range(min(i + 1, k), 0, -1): # duyet nguoc: moi mon chon toi da 1 lan
fc = f[c]; fp = f[c - 1]
for s in range(top, x - 1, -1):
v = fp[s - x]
if v:
fc[s] += v
for s in range(S + 1):
if L <= s <= R:
ans += f[k][s]
print(ans)
main()Cách 3Chia đôi tập – O(2N/2·N) · 100%
Làm đúng như nhận xét ở Lời mở đầu:
- Chia mảng thành nửa đầu $A$ ($h = \lfloor N/2 \rfloor$ món) và nửa sau $B$ ($N - h$ món).
- Với mỗi nửa, liệt kê tổng của mọi tập con và bỏ vào nhóm theo số món:
ga[c]chứa tổng các tập $c$ món của nửa đầu,gb[c]tương tự cho nửa sau. Dùng mẹo bỏ bit thấp nhất:sum[mask] = sum[mask & (mask - 1)] + a[ctz(mask)]để mỗi mask chỉ tốn $O(1)$. - Sắp xếp từng nhóm
gb[c]. - Với mỗi $c_1$ và mỗi tổng $s$ trong
ga[c1]: nửa sau phải chọn đúng $c_2 = K - c_1$ món (bỏ qua nếu $c_2$ âm hoặc lớn hơn số món nửa sau). Số tổng $t$ tronggb[c2]thỏa $L - s \le t \le R - s$ bằngupper_bound(R - s) - lower_bound(L - s).
Mỗi nửa có tối đa $2^{20}$ tập con; sắp xếp và chặt nhị phân tốn $O(2^{20} \cdot 20) \approx 2 \cdot 10^7$ phép – chạy cỡ $0{,}3$ giây.
- Đúng $K$ món: nếu quên nhóm theo số món mà ghép mọi tập con của hai nửa, ta đếm cả các cách chọn $K - 1$, $K + 1$ món... Ví dụ của đề "tình cờ" không có tập nào khác $3$ món rơi vào kinh phí, nên lỗi này vẫn qua ví dụ!
- Hai đầu đoạn: đếm $t \le R - s$ phải dùng
upper_bound, đếm $t \ge L - s$ dùnglower_bound. Lẫn hai hàm là mất các cách có tổng đúng bằng $L$ hoặc $R$. - Tràn số: tổng một nửa tới $2 \cdot 10^{10}$, đáp án tới $1{,}38 \cdot 10^{11}$ – đều phải
long long.
Các bạn nhập thử (tối đa 10 món) và bấm "Tiếp" để xem từng bước ghép hai nửa:
Code hoàn chỉnh (bản Python liệt kê tổng theo từng nhóm số món bằng cách "thêm dần từng món", ý tưởng y hệt):
#include <bits/stdc++.h>
using namespace std;
// Liet ke moi tap con cua mot nua, chia theo so mon da chon
void enumerate(const vector<long long>& a, vector<vector<long long>>& g) {
int m = a.size();
g.assign(m + 1, {});
vector<long long> sum(1 << m, 0);
g[0].push_back(0);
for (int mask = 1; mask < (1 << m); mask++) {
int i = __builtin_ctz(mask); // mon co chi so nho nhat trong mask
sum[mask] = sum[mask & (mask - 1)] + a[i]; // = tong cua mask bo mon i, cong them a[i]
g[__builtin_popcount(mask)].push_back(sum[mask]);
}
}
int main() {
int n, k;
long long L, R;
cin >> n >> k >> L >> R;
vector<long long> a(n);
for (auto& x : a) cin >> x;
int h = n / 2;
vector<long long> A(a.begin(), a.begin() + h), B(a.begin() + h, a.end());
vector<vector<long long>> ga, gb;
enumerate(A, ga); // nua dau: ga[c] = tong cua cac tap c mon
enumerate(B, gb); // nua sau
for (auto& v : gb) sort(v.begin(), v.end());
long long ans = 0;
for (int c1 = 0; c1 < (int)ga.size(); c1++) {
int c2 = k - c1; // nua sau phai chon dung k - c1 mon
if (c2 < 0 || c2 >= (int)gb.size()) continue;
const vector<long long>& v = gb[c2];
for (long long s : ga[c1]) { // dem t trong v voi L - s <= t <= R - s
ans += upper_bound(v.begin(), v.end(), R - s) - lower_bound(v.begin(), v.end(), L - s);
}
}
cout << ans << "\n";
return 0;
}import sys
from bisect import bisect_left, bisect_right
def groups(a):
# g[c] = danh sach tong cua moi tap con gom dung c mon
g = [[0]]
for x in a:
g.append([])
for c in range(len(g) - 1, 0, -1):
g[c] += [s + x for s in g[c - 1]]
return g
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0]); k = int(data[1]); L = int(data[2]); R = int(data[3])
a = [int(x) for x in data[4:4 + n]]
h = n // 2
ga = groups(a[:h]) # nua dau
gb = groups(a[h:]) # nua sau
for v in gb:
v.sort()
ans = 0
for c1 in range(len(ga)):
c2 = k - c1 # nua sau phai chon dung k - c1 mon
if c2 < 0 or c2 >= len(gb):
continue
v = gb[c2]
for s in ga[c1]: # dem t trong v voi L - s <= t <= R - s
ans += bisect_right(v, R - s) - bisect_left(v, L - s)
sys.stdout.write(str(ans) + "\n")
main()Bộ test chấm "bắt" những lỗi nào?
Bộ test có 30 test: 10 test subtask 1 ($N \le 20$, có $N = 1$, $K = 1$, $K = N$, giá bằng nhau, đáp án $0$...), 9 test subtask 2 ($N = 38..40$, $a_i \le 1000$) và 11 test subtask 3 ($N = 37..40$, giá tới $10^9$). Ở hai subtask sau, $K$ luôn được chọn để số cách chọn $K$ món trong $N$ món vượt $5 \cdot 10^9$ và đoạn $[L, R]$ nằm giữa phân bố tổng – vét cạn hay quay lui có cắt nhánh đều không kịp. Nhiều test có giá là bội của $10^8$ hoặc bằng nhau để có rất nhiều tổng đúng bằng $L$, $R$; nhiều test có đáp án vượt $2^{31}$ (tới $\binom{40}{20}$).
| Cách làm | Sub 1 (30%) | Sub 2 (30%) | Sub 3 (40%) | Điểm |
|---|---|---|---|---|
| Cách 1 – vét mọi tập con | Đúng | Sai/TLE | Sai/TLE | 30 |
| Cách 2 – cái túi đếm số cách | Đúng | Đúng | Sai/TLE | 60 |
| Cách 3 – chia đôi tập | Đúng | Đúng | Đúng | 100 |
| Quay lui chọn đúng K món, cắt nhánh theo tổng | Đúng | TLE | TLE | 30 |
Sai 1 – đáp án kiểu int | Đúng | 3/9 test | 2/11 test | ≈ 47 |
Sai 2 – tổng mỗi nửa kiểu int | 5/10 test | Đúng | WA | 45 |
Sai 3 – lẫn lower_bound/upper_bound ở đầu R | 3/10 test | 1/9 test | 2/11 test | ≈ 20 |
| Sai 4 – quên điều kiện đúng K món | 4/10 test | 2/9 test | 2/11 test | ≈ 26 |
Ghi chú của mình: các cách C++ ở trên đã được chấm thử với đúng bộ test của bài: Cách 1 đúng 10/10 test subtask 1 và trượt mọi test sau; Cách 2 đúng hết hai subtask đầu, trượt cả 11 test subtask 3; Cách 3 đúng 30/30 test, test lâu nhất khoảng 0,36 giây. Cách quay lui "thông minh" (sắp xếp giá, cắt nhánh khi tổng nhỏ nhất có thể đã vượt $R$ hoặc tổng lớn nhất có thể chưa tới $L$) chạy quá 3 giây ở cả 20 test của hai subtask sau. Cả bốn lời giải sai đều ra đúng ví dụ của đề – đó là lý do các bạn nên tự sinh thêm vài test nhỏ và so với cách vét cạn trước khi nộp.
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 😇
- Không biết học gì trước, học gì sau, học lan man nên kiến thức bị hổng.
- Bí bài không ai gỡ, ngồi cả buổi vẫn không ra rồi bỏ cuộc.
- Code chạy được nhưng không đủ điểm, không biết sai ở đâu, chậm ở đâu.
- Không có đề thi thử và người chấm, nên không biết mình đang ở mức nào.
- Dễ nản giữa chừng khi không có ai theo sát.
- Lộ trình 111 buổi video sắp sẵn từ dòng code đầu tiên đến đề HSG thật của các tỉnh.
- Thầy trực tiếp gỡ bí, chữa bài cho từng em qua nhóm Zalo riêng.
- Hệ thống chấm bài tự động 24/7 và thi thử HSG hằng tuần để biết chính xác mình đang ở đâu.
- Đóng học phí một lần, thầy kèm lâu dài: từ thi chuyên Tin đến HSG quốc gia và cả khi lên đại học.
Nhận xét
Đăng nhận xét