Song ca (Đề tự luyện HSG Tin quốc gia – Bài 1)
Đề bài
Song ca
Đội văn nghệ của thầy Sơn có $N$ học sinh, thầy có danh sách $K$ bản vọng cổ. Bạn thứ $i$ cho biết một xâu nhị phân độ dài $K$: ký tự thứ $j$ là 1 nếu bạn đó thuộc bản thứ $j$. Độ ăn ý của một cặp hai bạn khác nhau là số bản mà cả hai cùng thuộc.
Tính $D$ = độ ăn ý lớn nhất của một cặp, và $C$ = số cặp (không tính thứ tự) có độ ăn ý đúng bằng $D$.
Dữ liệu vào: dòng đầu $N, K$ $(2 \le N \le 2\cdot 10^5;\ 1 \le K \le 22)$; $N$ dòng sau, mỗi dòng một xâu 0/1 độ dài $K$.
Kết quả: hai số $D$ và $C$.
- Subtask 1 (20%): $N \le 2000$.
- Subtask 2 (20%): $K \le 10$.
- Subtask 3 (25%): $K \le 17$.
- Subtask 4 (35%): không có ràng buộc gì thêm.
Giới hạn thời gian: C++ 1 giây, Python/PyPy 3 giây.
6 5
10111
01101
11110
10110
01011
000113 3Ba cặp (1, 3), (1, 4), (3, 4) cùng thuộc ba bản $1, 3, 4$ nên có độ ăn ý $3$; không cặp nào ăn ý từ $4$ trở lên. Ví dụ cặp (2, 5) chỉ cùng thuộc bản $2$ và $5$.
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 Song caLời mở đầu
Mỗi bạn là một xâu nhị phân độ dài $K$, tức là một số nguyên $a_i$ trong đoạn $[0, 2^K)$ (ta đọc xâu như số nhị phân, ký tự đầu là bit cao nhất). Khi đó các bản mà hai bạn cùng thuộc chính là các bit $1$ của a[i] & a[j], và độ ăn ý là số bit 1 của số đó (hàm __builtin_popcount).
Đề hỏi một bài toán "trên mọi cặp" với $N = 2\cdot 10^5$, tức là khoảng $2\cdot 10^{10}$ cặp – không thể duyệt. Nhưng $K \le 22$ lại rất nhỏ: chỉ có $2^{22} \approx 4$ triệu tập bản khác nhau. Nút thắt của bài là chuyển từ "đếm cặp học sinh" sang "đếm theo tập bản vọng cổ":
Đổi góc nhìn: từ "cặp bạn" sang "tập bản vọng cổ mà cả nhóm cùng thuộc".
Lộ trình:
Cách 1Duyệt mọi cặp – O(N²) · 20%
Đổi mỗi xâu thành số nguyên a[i] (đọc từ trái sang: a = a*2 + bit). Với mỗi cặp $i < j$, độ ăn ý là popcount(a[i] & a[j]). Giữ giá trị lớn nhất best và số cặp đạt nó: gặp giá trị lớn hơn thì đặt lại bộ đếm, gặp bằng thì tăng bộ đếm.
Với $N \le 2000$ có khoảng $2\cdot 10^6$ cặp – rất nhanh. Nhưng với $N = 2\cdot 10^5$ là $2\cdot 10^{10}$ cặp, quá chậm.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
int n, k;
cin >> n >> k;
vector<int> a(n);
for (int i = 0; i < n; i++) {
string s; cin >> s;
a[i] = 0;
for (char c : s) a[i] = a[i] * 2 + (c - '0');
}
int best = -1; long long cnt = 0;
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++) {
int d = __builtin_popcount(a[i] & a[j]); // so ban cung thuoc
if (d > best) { best = d; cnt = 0; }
if (d == best) cnt++;
}
cout << best << " " << cnt << "\n";
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0])
a = [int(data[2 + i], 2) for i in range(n)]
best = -1; cnt = 0
for i in range(n):
x = a[i]
for j in range(i + 1, n):
d = bin(x & a[j]).count("1") # so ban cung thuoc
if d > best:
best = d; cnt = 1
elif d == best:
cnt += 1
print(best, cnt)
main()Cách 2Gộp các bạn cùng "kiểu" – O(4^K) · 40%
Khi $K \le 10$ chỉ có tối đa $2^{10} = 1024$ xâu khác nhau, trong khi $N$ có thể tới $2\cdot 10^5$: rất nhiều bạn thuộc giống hệt nhau. Gọi $f[x]$ là số bạn có xâu đúng bằng $x$. Ta duyệt cặp kiểu thay vì cặp bạn:
- hai kiểu khác nhau $x < y$: có $f[x]\cdot f[y]$ cặp bạn, mỗi cặp ăn ý
popcount(x & y); - hai bạn cùng kiểu $x$: có $\binom{f[x]}{2} = \frac{f[x](f[x]-1)}{2}$ cặp, mỗi cặp ăn ý
popcount(x).
Số cặp kiểu tối đa là $\frac{(2^K)^2}{2}$, với $K = 10$ chỉ khoảng nửa triệu. Code ghép thêm Cách 1 cho trường hợp $N \le 2000$.
int. Biến đếm và cả tích $f[x]\cdot f[y]$ phải là long long.#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
int n, k;
cin >> n >> k;
vector<int> a(n);
for (int i = 0; i < n; i++) {
string s; cin >> s;
a[i] = 0;
for (char c : s) a[i] = a[i] * 2 + (c - '0');
}
int best = -1; long long cnt = 0;
auto upd = [&](int d, long long w) {
if (w == 0) return;
if (d > best) { best = d; cnt = 0; }
if (d == best) cnt += w;
};
if (n <= 2000) { // Cach 1: duyet moi cap ban
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++) upd(__builtin_popcount(a[i] & a[j]), 1);
} else { // K nho: duyet moi cap "kieu" (xau)
vector<long long> f(1 << k, 0);
for (int x : a) f[x]++;
vector<int> ms;
for (int m = 0; m < (1 << k); m++) if (f[m]) ms.push_back(m);
for (size_t i = 0; i < ms.size(); i++) {
upd(__builtin_popcount(ms[i]), f[ms[i]] * (f[ms[i]] - 1) / 2); // hai ban cung kieu
for (size_t j = i + 1; j < ms.size(); j++)
upd(__builtin_popcount(ms[i] & ms[j]), f[ms[i]] * f[ms[j]]);
}
}
cout << best << " " << cnt << "\n";
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0]); k = int(data[1])
a = [int(data[2 + i], 2) for i in range(n)]
best = -1; cnt = 0
if n <= 2000: # Cach 1: duyet moi cap ban
for i in range(n):
x = a[i]
for j in range(i + 1, n):
d = bin(x & a[j]).count("1")
if d > best:
best = d; cnt = 1
elif d == best:
cnt += 1
else: # K nho: duyet moi cap "kieu" (xau)
f = [0] * (1 << k)
for x in a:
f[x] += 1
pc = [bin(m).count("1") for m in range(1 << k)]
ms = [m for m in range(1 << k) if f[m]]
for i in range(len(ms)):
x = ms[i]; fx = f[x]
if fx >= 2:
d = pc[x]; w = fx * (fx - 1) // 2
if d > best:
best = d; cnt = w
elif d == best:
cnt += w
for j in range(i + 1, len(ms)):
y = ms[j]
d = pc[x & y]
if d > best:
best = d; cnt = fx * f[y]
elif d == best:
cnt += fx * f[y]
print(best, cnt)
main()Cách 3Đếm theo tập bản – O(3^K) · 65%
Với $K = 17$ có hơn $10^5$ kiểu khác nhau, Cách 2 phải duyệt $5\cdot 10^9$ cặp kiểu. Ta cần thoát hẳn khỏi việc duyệt cặp.
Bước 1 – tính $g[S]$. Ta nói xâu $T$ chứa tập $S$ nếu mọi bit $1$ của $S$ cũng là bit $1$ của $T$, tức là (T & S) == S ($T$ là tập cha của $S$). Khi đó
Duyệt mọi tập cha $T$ của $S$ bằng mẹo T = (T + 1) | S: bắt đầu từ $T = S$, mỗi bước cộng thêm 1 rồi "ép" lại các bit của $S$, ta đi qua các tập cha của $S$ theo thứ tự tăng dần cho tới $2^K - 1$.
Bước 2 – tìm $D$. Theo nhận xét chính, $D = \max\{\,|S| : g[S] \ge 2\,\}$. Lưu ý phải là $\ge 2$: một bạn thuộc nhiều bản nhất chưa chắc có "bạn diễn" thuộc nhiều như thế (ở ví dụ, bạn 1 và bạn 3 thuộc 4 bản nhưng $D = 3$).
Bước 3 – đếm $C$. Xét một cặp có độ ăn ý đúng $D$, tập bản chung của nó là $A$ với $|A| = D$. Cặp này được đếm trong $\binom{g[S]}{2}$ với mọi $S \subseteq A$. Nhưng nếu chỉ lấy các $S$ có đúng $|S| = D$ thì chỉ còn $S = A$: cặp được đếm đúng một lần. Ngược lại, hai bạn cùng chứa một $S$ với $|S| = D$ thì có độ ăn ý $\ge D$, mà không có cặp nào vượt $D$, nên độ ăn ý đúng bằng $D$. Vậy
$$C = \sum_{|S| = D} \binom{g[S]}{2}.$$Mô phỏng dưới đây tính $g[S]$ cho từng tập $S$ (theo thứ tự số bản giảm dần) rồi chọn $D$ và cộng ra $C$:
Mỗi tập $S$ có $2^{K - |S|}$ tập cha, nên tổng số bước là $\sum_S 2^{K-|S|} = 3^K$ (mỗi bản: thuộc $S$, không thuộc $S$ nhưng thuộc $T$, hoặc không thuộc cả hai). Với $K = 17$, $3^{17} \approx 1{,}3\cdot 10^8$ – vừa đủ nhanh; nhưng $3^{22} \approx 3\cdot 10^{10}$ thì quá chậm. Code ghép thêm Cách 1 khi $N \le 2000$ (vì khi đó $K$ có thể tới 22).
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
int n, k;
cin >> n >> k;
int full = (1 << k) - 1;
vector<int> a(n);
for (int i = 0; i < n; i++) {
string s; cin >> s;
a[i] = 0;
for (char c : s) a[i] = a[i] * 2 + (c - '0');
}
int best = -1; long long cnt = 0;
if (n <= 2000) { // Cach 1: duyet moi cap ban
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++) {
int d = __builtin_popcount(a[i] & a[j]);
if (d > best) { best = d; cnt = 0; }
if (d == best) cnt++;
}
} else {
vector<long long> f(full + 1, 0), g(full + 1, 0);
for (int x : a) f[x]++;
// g[S] = so ban thuoc moi ban trong S = tong f[T] voi T chua S
for (int S = 0; S <= full; S++)
for (int T = S; ; T = (T + 1) | S) {
g[S] += f[T];
if (T == full) break;
}
for (int S = 0; S <= full; S++)
if (g[S] >= 2) best = max(best, __builtin_popcount(S));
for (int S = 0; S <= full; S++)
if (__builtin_popcount(S) == best) cnt += g[S] * (g[S] - 1) / 2;
}
cout << best << " " << cnt << "\n";
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0]); k = int(data[1])
a = [int(data[2 + i], 2) for i in range(n)]
best = -1; cnt = 0
if n <= 2000: # Cach 1: duyet moi cap ban
for i in range(n):
x = a[i]
for j in range(i + 1, n):
d = bin(x & a[j]).count("1")
if d > best:
best = d; cnt = 1
elif d == best:
cnt += 1
else:
full = (1 << k) - 1
f = [0] * (full + 1)
for x in a:
f[x] += 1
g = [0] * (full + 1)
# g[S] = tong f[T] voi T chua S (duyet moi tap cha T cua S)
for S in range(full + 1):
T = S; tot = 0
while True:
tot += f[T]
if T == full:
break
T = (T + 1) | S
g[S] = tot
pc = [bin(m).count("1") for m in range(full + 1)]
for S in range(full + 1):
if g[S] >= 2 and pc[S] > best:
best = pc[S]
for S in range(full + 1):
if pc[S] == best:
cnt += g[S] * (g[S] - 1) // 2
print(best, cnt)
main()Cách 4Tổng trên tập cha bằng SOS DP – O(K · 2^K) · 100%
Cách 3 lãng phí ở chỗ mỗi $g[S]$ được tính lại từ đầu. Ý tưởng "Sum over Subsets" (ở đây là tổng trên tập cha): cộng dồn lần lượt theo từng bit, giống như tính tổng tiền tố trên một bảng $K$ chiều, mỗi chiều chỉ có 2 giá trị $0, 1$.
Bắt đầu với f[m] = số bạn có xâu đúng bằng $m$. Lần lượt với từng bit $b = 0, 1, \ldots, K-1$:
for (int m = 0; m < (1 << k); m++)
if (!(m >> b & 1)) f[m] += f[m | (1 << b)];Bất biến: sau khi xử lý xong các bit $0..b$, f[m] bằng số bạn có xâu $T$ thỏa mãn: $T$ trùng $m$ ở các bit $> b$, và $T$ chứa $m$ ở các bit $\le b$. Khi xử lý bit $b$: nếu bit $b$ của $m$ là $0$ thì $T$ được phép có bit $b$ bằng $0$ (phần đã có trong f[m]) hoặc $1$ (phần nằm trong f[m | 1<<b]); nếu bit $b$ của $m$ là $1$ thì $T$ bắt buộc có bit $b$ bằng $1$ – giữ nguyên. Sau bit cuối cùng, f[m] chính là $g[m]$.
f[m | 1<<b] (là ô có bit $b$ bằng 1, không bị sửa trong lượt này), nên thứ tự duyệt $m$ không quan trọng.Xem các lượt cộng dồn chạy trên dữ liệu nhỏ (mỗi lượt một bit; lượt $b$ ứng với bản thứ $K - b$ vì ký tự đầu xâu là bit cao nhất):
Ghép lại với bước 2 và bước 3 của Cách 3, ta có lời giải hoàn chỉnh. Tổng cộng $K \cdot 2^{K-1} \approx 4{,}6\cdot 10^7$ phép cộng với $K = 22$ – chưa tới 0,1 giây.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
int n, k;
cin >> n >> k;
vector<long long> f(1 << k, 0);
for (int i = 0; i < n; i++) {
string s; cin >> s;
int m = 0;
for (char c : s) m = m * 2 + (c - '0');
f[m]++;
}
for (int b = 0; b < k; b++)
for (int m = 0; m < (1 << k); m++)
if (!(m >> b & 1)) f[m] += f[m | (1 << b)];
int best = -1;
for (int m = 0; m < (1 << k); m++)
if (f[m] >= 2) best = max(best, __builtin_popcount(m));
long long cnt = 0;
for (int m = 0; m < (1 << k); m++)
if (__builtin_popcount(m) == best) cnt += f[m] * (f[m] - 1) / 2;
cout << best << " " << cnt << "\n";
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0]); k = int(data[1])
size = 1 << k
f = [0] * size
for i in range(2, 2 + n):
f[int(data[i], 2)] += 1
# cong don theo tap cha: sau buoc nay f[m] = so ban thuoc moi ban trong m
for b in range(k):
step = 1 << b
for m in range(size):
if not m & step:
f[m] += f[m | step]
pc = [0] * size # pc[m] = so bit 1 cua m
for m in range(1, size):
pc[m] = pc[m >> 1] + (m & 1)
best = -1
for m in range(size):
if f[m] >= 2 and pc[m] > best:
best = pc[m]
cnt = 0
for m in range(size):
if pc[m] == best:
x = f[m]
cnt += x * (x - 1) // 2
sys.stdout.write("%d %d\n" % (best, cnt))
main()Bộ test chấm "bắt" những lỗi nào?
| Cách làm | Sub 1 (20%) | Sub 2 (20%) | Sub 3 (25%) | Sub 4 (35%) | Điểm |
|---|---|---|---|---|---|
| Cách 1 – Duyệt mọi cặp O(N²) | Đúng | TLE | TLE | TLE | 20 |
| Cách 2 – Gộp theo kiểu xâu O(4^K) | Đúng | Đúng | TLE | TLE | 40 |
| Cách 3 – Đếm theo tập, duyệt tập cha O(3^K) | Đúng | Đúng | Đúng | TLE | 65 |
| Cách 4 – SOS DP (sol.cpp) | Đúng | Đúng | Đúng | Đúng | 100 |
Sai: dùng int cho f và biến đếm (tràn số) | 11/11 | 6/9 | 6/8 | 7/10 | 76,6 |
| Sai: chọn D theo g[S] ≥ 1 (quên cặp cần hai bạn) | 5/11 | 4/9 | 2/8 | 2/10 | 31,2 |
| Sai: tham lam từng bit tìm AND lớn nhất theo giá trị số | 5/11 | 3/9 | 0/8 | 0/10 | 15,8 |
| Chậm: duyệt mọi tập con của từng bạn O(Σ 2^|a_i|) | 10/11 | 9/9 | 6/8 | 1/10 | ≈ 60 |
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: bộ test có 38 test (11 + 9 + 8 + 10), mỗi cách ở trên đạt đúng số điểm công bố, còn ba lời giải sai và một lời giải "đúng nhưng chậm" bị bắt như bảng trên. Lời giải chuẩn sol.cpp chạy test lâu nhất hết khoảng 0,3 giây; bản Python sol.py cho cùng đáp án trên mọi test (trên CPython mất khoảng 3 giây ở test K = 22, các em nhớ chọn PyPy 3 khi nộp). "TLE" nghĩa là chạy quá 3 lần giới hạn thời gian; riêng dòng "Chậm" được chấm với đúng giới hạn 1 giây. Lỗi tràn số chỉ lộ ra ở các test có rất nhiều bạn cùng thuộc một bộ bản tối ưu, nên nó vẫn "ăn" được khá nhiều điểm – đừng để mất điểm oan như vậy 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 😇
- 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