Điệp khúc (Đề tự luyện HSG Tin quốc gia – Bài 3)
Đề bài
Điệp khúc. Thầy Sơn ghi lại một bản đờn ca tài tử trên chợ nổi Cái Răng thành xâu $S$ gồm $N$ chữ cái thường. Một đoạn liên tiếp $S[s..s+2p-1]$ (độ dài chẵn $2p \ge 2$) là một điệp khúc nếu nửa đầu $X = S[s..s+p-1]$ và nửa sau $Y = S[s+p..s+2p-1]$ khác nhau ở không quá $K$ vị trí. Tìm điệp khúc dài nhất; nếu nhiều điệp khúc cùng độ dài lớn nhất thì lấy vị trí bắt đầu nhỏ nhất.
Dữ liệu vào: dòng 1 gồm $N, K$ $(1 \le N \le 2 \cdot 10^5,\ 0 \le K \le 3)$; dòng 2 là xâu $S$ (vị trí đánh số từ $1$).
Kết quả: hai số: độ dài $2p$ lớn nhất và vị trí bắt đầu $s$ nhỏ nhất; nếu không có điệp khúc nào thì in 0 0.
- Subtask 1 (20%): $N \le 300$.
- Subtask 2 (30%): $N \le 5000$.
- Subtask 3 (20%): $K = 0$.
- Subtask 4 (30%): không có ràng buộc gì thêm.
Giới hạn thời gian: C++ 1 giây, Python/PyPy 5 giây.
11 1
bcaaabcabbc8 4aabcabbc (vị trí 4) có nửa đầu aabc, nửa sau abbc, lệch đúng $1$ nốt. Hai đoạn dài $10$ là bcaaabcabb (lệch $2$ nốt) và caaabcabbc (lệch $3$ nốt) nên không có điệp khúc dài hơn.
10 0
baabcabcab6 3Với $K = 0$ hai nửa phải giống hệt. abcabc (vị trí 3), bcabca (4), cabcab (5) đều dài $6$, chọn vị trí nhỏ nhất là $3$.
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 Điệp khúcLời mở đầu
Đây là bài "khó nhưng chưa khó nhất" của đề: ý tưởng chính rất đẹp, nhưng để lấy trọn điểm các em phải kết hợp được ba thứ: hash + chặt nhị phân tìm LCP, kỹ thuật điểm mốc (anchor) và một chút cẩn thận với các chỗ lệch. Mình đi từ từ nhé.
Gọi $p$ là độ dài một nửa. Điệp khúc nửa $p$ bắt đầu tại $s$ so sánh $S_{s+j}$ với $S_{s+p+j}$, tức là so mỗi ký tự với ký tự cách nó đúng $p$ bước. Vì vậy với mỗi $p$ ta định nghĩa mảng "lệch" $$d_p[t] = \begin{cases}1 & S_t \ne S_{t+p}\\ 0 & S_t = S_{t+p}\end{cases}\qquad (0 \le t < N - p).$$ Khi đó có điệp khúc nửa $p$ tại $s$ khi và chỉ khi tổng $d_p[s] + d_p[s+1] + \dots + d_p[s+p-1] \le K$: một cửa sổ dài đúng $p$ trên mảng $d_p$ chứa không quá $K$ số $1$.
Hình 1. Với $p = 3$: nối mỗi vị trí $t$ với $t+3$; cung đỏ là chỗ lệch. Cửa sổ $d_3[0..2]$ có tổng $1 \le K = 1$ nên abcabd là điệp khúc.
abab có điệp khúc nửa $2$ nhưng không có điệp khúc nửa $1$ (không có hai chữ liền nhau giống nhau). Tính chất "có/không" không đơn điệu theo $p$, nên ta phải xét mọi $p$ từ $\lfloor N/2 \rfloor$ giảm dần, gặp $p$ đầu tiên có điệp khúc thì dừng; với $p$ đó lấy $s$ nhỏ nhất. Bộ test có hẳn những test bắt lỗi này.Vậy toàn bộ bài toán quy về: với mỗi $p$ (giảm dần), tìm cửa sổ dài $p$ trái nhất trên $d_p$ có tổng $\le K$. Các cách dưới đây chỉ khác nhau ở chỗ làm việc đó nhanh tới đâu.
Cách 1Duyệt trâu – O(N³) · 20%
Làm đúng như định nghĩa: thử $p$ từ lớn xuống nhỏ, thử $s$ từ trái sang phải, đếm số vị trí lệch giữa hai nửa trong $O(p)$. Điệp khúc đầu tiên tìm được chính là đáp án (dài nhất, rồi trái nhất). Tổng số phép so sánh khoảng $\sum_p (N - 2p + 1)\cdot p \approx N^3/12$: với $N = 300$ chỉ khoảng $2{,}25$ triệu, nhưng với $N = 5000$ đã là $10^{10}$.
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, K;
string s;
cin >> n >> K >> s;
for (int p = n / 2; p >= 1; p--) // thu do dai nua p tu lon den nho
for (int st = 0; st + 2 * p <= n; st++) { // vi tri bat dau (tu trai sang)
int d = 0; // so not lech giua 2 nua
for (int j = 0; j < p; j++)
if (s[st + j] != s[st + p + j]) d++;
if (d <= K) {
cout << 2 * p << " " << st + 1 << "\n";
return 0;
}
}
cout << "0 0\n";
return 0;
}import sys
def main():
data = sys.stdin.read().split()
n = int(data[0]); K = int(data[1]); s = data[2]
for p in range(n // 2, 0, -1): # thu do dai nua p tu lon den nho
for st in range(0, n - 2 * p + 1): # vi tri bat dau (tu trai sang)
d = 0 # so not lech giua 2 nua
for j in range(p):
if s[st + j] != s[st + p + j]:
d += 1
if d <= K:
print(2 * p, st + 1)
return
print(0, 0)
main()Cách 2Cửa sổ trượt trên mảng lệch – O(N²) · 50%
Với một $p$ cố định, các cửa sổ $[s, s+p-1]$ trên $d_p$ nối tiếp nhau: khi trượt từ $s-1$ sang $s$, ta bỏ $d_p[s-1]$ ra và thêm $d_p[s+p-1]$ vào. Như vậy tổng cửa sổ cập nhật trong $O(1)$ và mỗi $p$ chỉ tốn $O(N)$. Tổng cộng $O(N^2)$: đủ nhanh cho $N \le 5000$ (khoảng $1{,}25 \cdot 10^7$ phép tính), nhưng với $N = 2 \cdot 10^5$ thì là $10^{10}$, quá chậm.
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, K;
string s;
cin >> n >> K >> s;
for (int p = n / 2; p >= 1; p--) {
int m = n - p, d = 0; // diff[t] = (s[t] != s[t+p]), t = 0..m-1
for (int t = 0; t < p; t++) d += (s[t] != s[t + p]);
for (int st = 0; st + p <= m; st++) { // cua so diff[st..st+p-1]
if (st > 0) d += (s[st + p - 1] != s[st + 2 * p - 1]) - (s[st - 1] != s[st - 1 + p]);
if (d <= K) {
cout << 2 * p << " " << st + 1 << "\n";
return 0;
}
}
}
cout << "0 0\n";
return 0;
}import sys
def main():
data = sys.stdin.read().split()
n = int(data[0]); K = int(data[1]); s = data[2]
for p in range(n // 2, 0, -1):
m = n - p
diff = [1 if s[t] != s[t + p] else 0 for t in range(m)] # diff[t] = (s[t] != s[t+p])
d = sum(diff[:p])
for st in range(0, m - p + 1): # cua so diff[st..st+p-1]
if st > 0:
d += diff[st + p - 1] - diff[st - 1]
if d <= K:
print(2 * p, st + 1)
return
print(0, 0)
main()Em thử nhập một xâu ngắn rồi bấm Tiếp để xem cửa sổ trượt chạy qua từng $p$. Các ô xanh là nửa đầu $X$, ô vàng là nửa sau $Y$, chữ đỏ là chỗ lệch.
Cách 3K = 0: kỹ thuật điểm mốc + hash – O(N log² N) · 70%
Với $K = 0$, ta cần một cửa sổ dài $p$ trên $d_p$ toàn số 0, tức là một đoạn $p$ vị trí liên tiếp mà $S_t = S_{t+p}$. Cách 2 chậm vì nó "đi bộ" qua từng vị trí $t$. Ý tưởng then chốt để tăng tốc:
Tại mốc $i$, gọi $f$ = số vị trí $i, i+1, \dots$ liên tiếp có $d_p = 0$ (khớp về phải), $b$ = số vị trí $i-1, i-2, \dots$ liên tiếp có $d_p = 0$ (khớp về trái). Có cửa sổ toàn 0 chứa $i$ khi và chỉ khi $b + f \ge p$, và cửa sổ trái nhất bắt đầu tại $i - b$ (nhớ chặn $b \le p - 1$ để cửa sổ thật sự chứa $i$).
Hình 2. Mốc đặt cách nhau $p$; từ mốc $i$ ta "duỗi" về hai phía, nếu tổng độ dài khớp $\ge p$ thì có điệp khúc chứa mốc này.
Tính $f$ và $b$ nhanh. $f$ chính là độ dài tiền tố chung dài nhất (LCP) của hai hậu tố $S[i..]$ và $S[i+p..]$; $b$ là hậu tố chung dài nhất (LCS) của $S[..i-1]$ và $S[..i-1+p]$. Dùng hash đa thức (so sánh hai xâu con trong $O(1)$) kết hợp chặt nhị phân độ dài, mỗi lần tính mất $O(\log N)$.
Độ phức tạp. Với mỗi $p$ có khoảng $N/p$ mốc, nên tổng số mốc là $\sum_{p} N/p = O(N \log N)$ (tổng điều hoà). Nhân với $O(\log N)$ cho mỗi lần chặt nhị phân, ta được $O(N \log^2 N)$ – chạy thoải mái với $N = 2\cdot 10^5$. Khi $K > 0$, code dưới đây quay về Cách 2 nên đạt $20 + 30 + 20 = 70\%$.
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const ull MOD = (1ULL << 61) - 1;
int n, K;
string s;
vector<ull> h, pw;
ull mulmod(ull a, ull b) {
__uint128_t c = (__uint128_t)a * b;
ull r = (ull)(c & MOD) + (ull)(c >> 61);
return r >= MOD ? r - MOD : r;
}
ull get(int x, int len) {
ull r = h[x + len] + MOD - mulmod(h[x], pw[len]);
return r >= MOD ? r - MOD : r;
}
bool same(int x, int y, int len) { return get(x, len) == get(y, len); }
// tien to chung dai nhat (toi da m) cua s[x..] va s[y..] - chat nhi phan
int lcp(int x, int y, int m) {
int lo = 0, hi = m;
while (lo < hi) {
int mid = (lo + hi + 1) / 2;
if (same(x, y, mid)) lo = mid; else hi = mid - 1;
}
return lo;
}
// hau to chung dai nhat (toi da m) cua s[..x] va s[..y]
int lcs(int x, int y, int m) {
int lo = 0, hi = m;
while (lo < hi) {
int mid = (lo + hi + 1) / 2;
if (same(x - mid + 1, y - mid + 1, mid)) lo = mid; else hi = mid - 1;
}
return lo;
}
// Cach 2: cua so truot O(N^2) cho truong hop K > 0
void slow() {
for (int p = n / 2; p >= 1; p--) {
int m = n - p, d = 0;
for (int t = 0; t < p; t++) d += (s[t] != s[t + p]);
for (int st = 0; st + p <= m; st++) {
if (st > 0) d += (s[st + p - 1] != s[st + 2 * p - 1]) - (s[st - 1] != s[st - 1 + p]);
if (d <= K) { printf("%d %d\n", 2 * p, st + 1); return; }
}
}
printf("0 0\n");
}
int main() {
cin >> n >> K >> s;
if (K > 0) { slow(); return 0; }
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ull B = rng() % (MOD - 1000) + 500;
h.assign(n + 1, 0); pw.assign(n + 1, 1);
for (int i = 0; i < n; i++) {
h[i + 1] = (mulmod(h[i], B) + (ull)s[i]) % MOD;
pw[i + 1] = mulmod(pw[i], B);
}
for (int p = n / 2; p >= 1; p--)
for (int i = 0; i + p < n; i += p) { // moc i = 0, p, 2p, ...
int f = lcp(i, i + p, min(n - p, i + p) - i); // khop ve phai
int b = (i == 0) ? 0 : lcs(i - 1, i - 1 + p, min(i, p - 1)); // khop ve trai
if (b + f >= p) {
printf("%d %d\n", 2 * p, i - b + 1);
return 0;
}
}
printf("0 0\n");
return 0;
}import sys, random
def slow(n, K, s): # Cach 2: cua so truot O(N^2) cho K > 0
for p in range(n // 2, 0, -1):
m = n - p
diff = [1 if s[t] != s[t + p] else 0 for t in range(m)]
d = sum(diff[:p])
for st in range(0, m - p + 1):
if st > 0:
d += diff[st + p - 1] - diff[st - 1]
if d <= K:
return "%d %d" % (2 * p, st + 1)
return "0 0"
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0]); K = int(data[1]); s = data[2]
if K > 0:
print(slow(n, K, s)); return
MOD = (1 << 61) - 1
B = random.randrange(500, MOD - 500)
h = [0] * (n + 1); pw = [1] * (n + 1)
for i in range(n):
h[i + 1] = (h[i] * B + s[i]) % MOD
pw[i + 1] = pw[i] * B % MOD
def same(x, y, ln):
return (h[x + ln] - h[x] * pw[ln] - h[y + ln] + h[y] * pw[ln]) % MOD == 0
def lcp(x, y, m): # chat nhi phan
lo, hi = 0, m
while lo < hi:
mid = (lo + hi + 1) >> 1
if same(x, y, mid): lo = mid
else: hi = mid - 1
return lo
def lcs(x, y, m):
lo, hi = 0, m
while lo < hi:
mid = (lo + hi + 1) >> 1
if same(x - mid + 1, y - mid + 1, mid): lo = mid
else: hi = mid - 1
return lo
for p in range(n // 2, 0, -1):
for i in range(0, n - p, p): # moc i = 0, p, 2p, ...
f = lcp(i, i + p, min(n - p, i + p) - i) # khop ve phai
b = 0 if i == 0 else lcs(i - 1, i - 1 + p, min(i, p - 1)) # khop ve trai
if b + f >= p:
print(2 * p, i - b + 1)
return
print(0, 0)
main()unsigned long long nhân thoải mái). Xâu Thue–Morse độ dài $2^{11} = 2048$ và xâu bù của nó luôn cho cùng một giá trị hash modulo $2^{64}$ với mọi cơ số. Bộ test có hẳn những đoạn được dựng như vậy: hash $2^{64}$ sẽ "tưởng" hai đoạn khác nhau là bằng nhau và báo một điệp khúc giả dài $8192$. Lời giải chuẩn dùng modulo nguyên tố $2^{61}-1$ với cơ số ngẫu nhiên.Cách 4Điểm mốc + nhảy qua K chỗ lệch – O(K · N log² N) · 100%
Bây giờ cửa sổ được phép chứa tối đa $K$ số $1$. Vẫn giữ nhận xét điểm mốc: mỗi cửa sổ dài $p$ chứa đúng một mốc $i$. Nhưng thay vì dừng ở chỗ lệch đầu tiên, ta nhảy qua nó và tìm tiếp: một lần LCP cho ta chỗ lệch kế tiếp, nên $K+1$ lần LCP cho ta $K+1$ chỗ lệch đầu tiên bên phải mốc; tương tự $K+1$ lần LCS cho $K+1$ chỗ lệch đầu tiên bên trái.
- Bên phải: $R_0 < R_1 < \dots < R_K$ là vị trí các số $1$ đầu tiên trên $d_p$ tính từ $i$ trở đi. Ta chỉ quan tâm tới $lim = \min(N-p,\ i+p)$: không có cửa sổ nào chứa $i$ vượt quá đó, nên nếu không đủ chỗ lệch thì coi $R_c = lim$ (một "chỗ lệch ảo").
- Bên trái: $L_0 > L_1 > \dots > L_K$ là vị trí các số $1$ đầu tiên tính từ $i-1$ lùi về, chặn bởi $lb = \max(-1,\ i-p)$.
Cửa sổ chứa tối đa $K$ chỗ lệch thì dùng $a$ chỗ lệch bên trái và tối đa $K - a$ chỗ lệch bên phải, với $a = 0, 1, \dots, K$. Khi đó nó phải nằm trong khoảng mở $(L_a,\ R_{K-a})$. Vậy:
Hình 3. Ô đỏ là các số $1$ trên $d_p$. Mỗi cách chia $a$ / $K-a$ cho một khoảng "sạch" chứa tối đa $K$ chỗ lệch.
Tại sao khoảng đó chắc chắn chứa mốc $i$? Vì $L_a \ge i - p$ và $R_{K-a} \le i + p$: một khoảng dài ít nhất $p$ nằm gọn trong $[i-p+1,\ i+p-1]$ thì bắt buộc phải chứa $i$. Do đó cửa sổ bắt đầu tại $L_a + 1$ hợp lệ, và ta không đếm thiếu cũng không đếm thừa.
Vị trí nhỏ nhất. Duyệt các mốc theo thứ tự tăng dần: mốc $i$ chỉ cho các vị trí bắt đầu trong $[i-p+1,\ i]$, mốc sau cho các vị trí lớn hơn. Vậy mốc đầu tiên thành công cho luôn $s$ nhỏ nhất, in ra và kết thúc.
lcp so ký tự đầu, rồi thử độ dài $2, 4, 8, \dots$ cho đến khi hỏng, sau đó mới chặt nhị phân trong $[len, 2len)$. Chi phí chỉ là $O(\log \text{LCP})$: với xâu "ngẫu nhiên" chỗ lệch xuất hiện ngay nên gần như $O(1)$. Nhờ vậy lời giải chuẩn chạy chưa tới $0{,}5$ giây.Độ phức tạp. Mỗi mốc tốn $2(K+1)$ lần LCP/LCS, mỗi lần $O(\log N)$; tổng số mốc $O(N \log N)$. Vậy tổng là $O(K \cdot N \log^2 N)$ với $K \le 3$.
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const ull MOD = (1ULL << 61) - 1;
int n, K;
string s;
vector<ull> h, pw;
ull mulmod(ull a, ull b) {
__uint128_t c = (__uint128_t)a * b;
ull r = (ull)(c & MOD) + (ull)(c >> 61);
return r >= MOD ? r - MOD : r;
}
// ma bam cua s[x..x+len-1]
ull get(int x, int len) {
ull r = h[x + len] + MOD - mulmod(h[x], pw[len]);
return r >= MOD ? r - MOD : r;
}
bool same(int x, int y, int len) { return get(x, len) == get(y, len); }
// tien to chung dai nhat (toi da m ky tu) cua s[x..] va s[y..]
int lcp(int x, int y, int m) {
if (m == 0 || s[x] != s[y]) return 0;
int len = 1;
while (2 * len <= m && same(x, y, 2 * len)) len *= 2;
int lo = len, hi = min(2 * len - 1, m);
while (lo < hi) {
int mid = (lo + hi + 1) / 2;
if (same(x, y, mid)) lo = mid; else hi = mid - 1;
}
return lo;
}
// hau to chung dai nhat (toi da m ky tu) cua s[..x] va s[..y]
int lcs(int x, int y, int m) {
if (m == 0 || s[x] != s[y]) return 0;
int len = 1;
while (2 * len <= m && same(x - 2 * len + 1, y - 2 * len + 1, 2 * len)) len *= 2;
int lo = len, hi = min(2 * len - 1, m);
while (lo < hi) {
int mid = (lo + hi + 1) / 2;
if (same(x - mid + 1, y - mid + 1, mid)) lo = mid; else hi = mid - 1;
}
return lo;
}
int main() {
cin >> n >> K >> s;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ull B = rng() % (MOD - 1000) + 500;
h.assign(n + 1, 0); pw.assign(n + 1, 1);
for (int i = 0; i < n; i++) {
h[i + 1] = (mulmod(h[i], B) + (ull)s[i]) % MOD;
pw[i + 1] = mulmod(pw[i], B);
}
int L[4], R[4];
for (int p = n / 2; p >= 1; p--) {
for (int i = 0; i + p < n; i += p) { // moc i = 0, p, 2p, ...
int lim = min(n - p, i + p), t = i; // tim K+1 cho lech ben phai
for (int c = 0; c <= K; c++) {
t += lcp(t, t + p, lim - t);
R[c] = t;
if (t < lim) t++;
}
int lb = max(-1, i - p); t = i - 1; // tim K+1 cho lech ben trai
for (int c = 0; c <= K; c++) {
t -= lcs(t, t + p, t - lb);
L[c] = t;
if (t > lb) t--;
}
int best = INT_MAX;
for (int a = 0; a <= K; a++) // a cho lech ben trai, K-a ben phai
if (R[K - a] - L[a] - 1 >= p) best = min(best, L[a] + 1);
if (best != INT_MAX) {
printf("%d %d\n", 2 * p, best + 1);
return 0;
}
}
}
printf("0 0\n");
return 0;
}import sys, random
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0]); K = int(data[1]); s = data[2]
MOD = (1 << 61) - 1
B = random.randrange(500, MOD - 500)
h = [0] * (n + 1); pw = [1] * (n + 1)
for i in range(n):
h[i + 1] = (h[i] * B + s[i]) % MOD
pw[i + 1] = pw[i] * B % MOD
def same(x, y, ln): # s[x..x+ln-1] == s[y..y+ln-1] ?
return (h[x + ln] - h[x] * pw[ln] - h[y + ln] + h[y] * pw[ln]) % MOD == 0
def lcp(x, y, m): # tien to chung dai nhat (toi da m)
if m == 0 or s[x] != s[y]:
return 0
ln = 1
while 2 * ln <= m and same(x, y, 2 * ln):
ln *= 2
lo = ln; hi = min(2 * ln - 1, m)
while lo < hi:
mid = (lo + hi + 1) >> 1
if same(x, y, mid): lo = mid
else: hi = mid - 1
return lo
def lcs(x, y, m): # hau to chung dai nhat (toi da m)
if m == 0 or s[x] != s[y]:
return 0
ln = 1
while 2 * ln <= m and same(x - 2 * ln + 1, y - 2 * ln + 1, 2 * ln):
ln *= 2
lo = ln; hi = min(2 * ln - 1, m)
while lo < hi:
mid = (lo + hi + 1) >> 1
if same(x - mid + 1, y - mid + 1, mid): lo = mid
else: hi = mid - 1
return lo
L = [0] * (K + 1); R = [0] * (K + 1)
for p in range(n // 2, 0, -1):
for i in range(0, n - p, p): # moc i = 0, p, 2p, ...
lim = min(n - p, i + p); t = i # K+1 cho lech ben phai
for c in range(K + 1):
t += lcp(t, t + p, lim - t)
R[c] = t
if t < lim: t += 1
lb = max(-1, i - p); t = i - 1 # K+1 cho lech ben trai
for c in range(K + 1):
t -= lcs(t, t + p, t - lb)
L[c] = t
if t > lb: t -= 1
best = -1
for a in range(K + 1):
if R[K - a] - L[a] - 1 >= p:
if best < 0 or L[a] + 1 < best: best = L[a] + 1
if best >= 0:
sys.stdout.write("%d %d\n" % (2 * p, best + 1))
return
sys.stdout.write("0 0\n")
main()Mô phỏng dưới đây chạy đúng thuật toán của Cách 4: với mỗi $p$ giảm dần, đi qua từng mốc, tìm $K+1$ chỗ lệch mỗi bên rồi kiểm tra các cách chia $a$.
Và đây là khung chạy tay từng dòng của chính code C++ ở trên (để dễ theo dõi, khung mô phỏng so sánh ký tự trực tiếp thay cho việc tính mã băm – kết quả của các hàm lcp/lcs là như nhau).
Bộ test chấm "bắt" những lỗi nào?
Bộ test gồm 37 test: subtask 1 có 9 test ($N \le 300$, có $N = 1$, xâu toàn chữ a), subtask 2 có 8 test ($N \approx 5000$), subtask 3 có 9 test và subtask 4 có 11 test (đều $N \approx 2\cdot 10^5$). Mỗi test lớn đều có đáp án $2p \le N/2$ để các cách chậm không thể "dừng sớm", có điệp khúc "mồi nhử" dài hơn nhưng lệch $K+1$ nốt, có điệp khúc mà chỗ lệch nằm hai bên mốc, và 5 test có cấu trúc Thue–Morse (4 test dựng riêng để chống hash $2^{64}$, 1 test xâu không chứa bình phương sinh từ Thue–Morse).
| Cách làm | Sub 1 | Sub 2 | Sub 3 | Sub 4 | Điểm |
|---|---|---|---|---|---|
| Cách 1 – duyệt trâu O(N³) | 9/9 | TLE | TLE | TLE | 20 |
| Cách 2 – cửa sổ trượt O(N²) | 9/9 | 8/8 | TLE | TLE | 50 |
| Cách 3 – điểm mốc cho K = 0 | 9/9 | 8/8 | 9/9 | TLE | 70 |
| Cách 4 – lời giải đầy đủ | 9/9 | 8/8 | 9/9 | 11/11 | 100 |
| Sai: hash tràn số modulo 2^64 | 9/9 | 8/8 | 6/9 | 9/11 | 87,88 |
| Sai: chỉ cho chỗ lệch ở bên phải mốc (chỉ xét a = 0) | 7/9 | 3/8 | 9/9 | 3/11 | 54,99 |
| Sai: chặt nhị phân theo độ dài p | 6/9 | 3/8 | 3/9 | 1/11 | 33,98 |
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: lời giải chuẩn chạy tối đa 0,6 giây, Cách 3 tối đa 0,63 giây ở subtask 3; các ô TLE đều chạy quá 3,5 giây (gấp hơn 3 lần giới hạn). Lời giải chuẩn còn được đối chiếu với chương trình vét cạn trên 1500 test nhỏ ngẫu nhiên và không lệch test nào; bản Python cho kết quả trùng khớp trên mọi test.
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