Dây Đèn (HSG9 Hà Nội 2025 – Bài 3)
Đề bài
DÂY ĐÈN
Để trang trí Tết, Nam treo một dây đèn gồm $N$ bóng đèn, được đánh số từ $1$ đến $N$, từ trái sang phải. Mỗi bóng đèn khi bật sẽ có hai màu vàng hoặc đỏ. Dây đèn được nhúng một mã lệnh cho phép nhận một số tự nhiên $X$. Khi đó, màu của bóng đèn thứ $X$ và các bóng đèn cách bóng đèn thứ $X$ không quá $K$ bóng đèn sẽ đều đổi từ vàng thành đỏ hoặc ngược lại.
Ban đầu các bóng đèn đều có màu vàng. Để dây đèn trông đẹp mắt, Nam đã lập trình để điều khiển màu của các bóng đèn. Chương trình của Nam có $M$ dòng lệnh, mỗi dòng lệnh tương ứng với một lần gọi mã lệnh của dây đèn. Vì số lượng bóng đèn quá lớn, sau khi lập trình xong, Nam muốn kiểm tra ngẫu nhiên màu một số bóng đèn xem có đúng như ý tưởng ban đầu không.
Yêu cầu: Cho các số tự nhiên $X$ là tham số của $M$ dòng lệnh trong chương trình của Nam. Hãy lập trình để trả lời $Q$ câu hỏi tương ứng với các lần kiểm tra của Nam. Biết rằng mỗi câu hỏi chứa một số nguyên dương $P$ để xác định xem bóng đèn thứ $P$ trong dây đèn có màu vàng hay đỏ.
Dữ liệu vào từ file văn bản DAYDEN.INP:
- Dòng đầu tiên gồm bốn số nguyên dương lần lượt là $N, M, Q, K$ $(1 \le N \le 10^9;\ 1 \le M \le 10^5;\ 1 \le Q \le 10^5;\ 0 \le K \le N)$;
- Dòng thứ hai gồm $M$ số nguyên dương $X_i$ mô tả tham số của lệnh thứ $i$ $(1 \le X_i \le N)$;
- Dòng thứ ba gồm $Q$ số nguyên dương $P_i$ mô tả câu hỏi thứ $i$ $(1 \le P_i \le N)$.
Kết quả ghi ra file văn bản DAYDEN.OUT: Gồm $Q$ dòng, dòng thứ $i$ là câu trả lời cho câu hỏi thứ $i$. Nếu bóng đèn tại vị trí $P_i$ đang có màu vàng thì ghi ra ký tự "V", ngược lại ghi ra ký tự "D".
Ràng buộc:
- Có $60\%$ số test ứng với $60\%$ số điểm của bài thoả mãn: $N, M, Q \le 10^3$;
- $20\%$ số test khác ứng với $20\%$ số điểm của bài thoả mãn: $N, M \le 10^5$;
- $20\%$ số test còn lại ứng với $20\%$ số điểm của bài không có ràng buộc gì thêm.
Lưu ý: đề thi gốc đọc/ghi file DAYDEN.INP / DAYDEN.OUT; trên CLUE OJ thì đọc từ bàn phím và in ra màn hình (code bên dưới có đoạn if(fopen(...)) nên nộp kiểu nào cũng chạy đúng).
7 2 4 1
3 5
2 7 4 5D
V
V
DGiải thích (theo đề):
- Sau lần gọi mã lệnh thứ nhất, các bóng trong dây đèn có màu là: $V, D, D, D, V, V, V$;
- Sau lần gọi mã lệnh thứ hai, các bóng trong dây đèn có màu là: $V, D, D, V, D, D, V$.
Lời mở đầu
Đây là bài 3 trong đề thi học sinh giỏi Tin học lớp 9 thành phố Hà Nội năm 2025. Bài này rất hay để luyện đúng 3 "nấc" kiến thức mà mình hay dạy cho các bạn lớp 9: duyệt trâu → mảng hiệu (difference array) → nén số. Mỗi subtask của đề ứng đúng với một nấc, nên mình viết lời giải theo từng subtask để các bạn thấy được tư duy đi lên từng bước nha. Hy vọng mang đến được giá trị cho các bạn 😇.
Bạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì link bài đây nhé:
Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.
Nộp bài trên CLUE OJMình giải thích ví dụ để bạn nào chưa hiểu đề sẽ hiểu rõ. Dây có $N = 7$ bóng, $K = 1$, nghĩa là mỗi lần gọi mã lệnh với tham số $X$ thì bóng thứ $X$ và các bóng cách nó không quá 1 bóng (tức bóng $X - 1$, $X$, $X + 1$) sẽ đổi màu: vàng ($V$) thành đỏ ($D$), đỏ thành vàng.
Bóng 4 bị đổi màu 2 lần (đỏ rồi lại vàng). Các câu hỏi $P = 2, 7, 4, 5$ nên đáp án lần lượt là D, V, V, D.
Lộ trình lời giải, bấm vào từng phần để nhảy tới:
Subtask 1Duyệt trâu từng bóng đèn – O(M·K + Q)
Ở subtask này $N, M, Q \le 10^3$ nên ta cứ làm đúng theo đề. Với mỗi lần áp mã lệnh lên vị trí $X_i$, ta nhận thấy 2 điều:
- Phạm vi các bóng đèn bị thay đổi là đoạn từ $\max(1, X_i - K)$ đến $\min(N, X_i + K)$. Chỉ số bị thay đổi không thể nhỏ hơn $1$ (đầu dây) và không thể vượt quá $N$ (số lượng bóng của dây đèn).
- Bóng thứ $j$ có màu gì chỉ phụ thuộc vào số lần nó bị đổi màu. Ban đầu là vàng, đổi 1 lần thành đỏ, 2 lần lại về vàng, 3 lần đỏ… Vậy nếu số mã lệnh làm thay đổi nó là chẵn thì đèn màu vàng, còn lẻ thì màu đỏ. Thứ tự các lệnh không quan trọng gì cả!
D, chẵn thì in V.Source code để các bạn tham khảo nếu làm theo hướng này:
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n, m, q, k, x[100005], sl[100005], p;
signed main(){
if(fopen("dayden.inp", "r")){
freopen("dayden.inp", "r", stdin);
freopen("dayden.out", "w", stdout);
}
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m >> q >> k;
for (int i = 1; i <= m; i++){
cin >> x[i];
for (int j = max((long long)1, x[i] - k); j <= n && j < x[i] + k + 1; j++){
sl[j]++;
}
}
for (int i = 1; i <= q; i++){
cin >> p;
if (sl[p] % 2 == 1) cout << 'D' << endl;
else cout << 'V' << endl;
}
}import sys, os
def main():
if os.path.exists('dayden.inp'):
sys.stdin = open('dayden.inp')
sys.stdout = open('dayden.out', 'w')
data = sys.stdin.read().split()
n, m, q, k = int(data[0]), int(data[1]), int(data[2]), int(data[3])
x = [0] + [int(v) for v in data[4:4 + m]]
sl = [0] * (n + 2)
for i in range(1, m + 1):
j = max(1, x[i] - k)
while j <= n and j < x[i] + k + 1:
sl[j] += 1
j += 1
res = []
for i in range(q):
p = int(data[4 + m + i])
res.append('D' if sl[p] % 2 == 1 else 'V')
print('\n'.join(res))
main()
sys.stdout.flush()Trong vòng for của $j$, điều kiện j <= n && j < x[i] + k + 1 chính là $j \le \min(N, X_i + K)$ viết gộp lại đó các bạn. Các bạn bấm Tiếp để chạy tay từng dòng nha, phần "Dữ liệu" có vẽ cả mảng $sl$ lẫn màu của dây đèn:
Đánh giá độ phức tạp của cách làm này:
- Không gian: mảng $sl$ có $N$ phần tử nên là $O(N)$ – vì vậy cách này chỉ dùng được khi $N$ nhỏ.
- Thời gian: mỗi lệnh duyệt tối đa $\min(N, 2K + 1)$ bóng, có $M$ lệnh, cộng thêm $Q$ câu hỏi trả lời $O(1)$: tổng là $O(M \cdot K + Q)$ (chính xác hơn là $O(M \cdot \min(N, K) + Q)$). Với $N, M, Q \le 10^3$ thì chỉ khoảng $10^6$ phép tính, chạy vèo vèo.
sl[100005] cũng không đủ chỗ.Subtask 2Mảng hiệu – O(N + M + Q)
Ta sẽ cố gắng tối ưu từ subtask 1. Điểm chậm nằm ở chỗ: với mỗi mã lệnh áp lên đoạn $[L, R]$ (với $L = \max(1, X_i - K)$, $R = X_i + K$), ta phải cập nhật trâu từng phần tử của đoạn. Thay vào đó, ta có thể dùng mảng hiệu để "cộng 1 cho cả đoạn" chỉ với 2 phép tính:
sl[L]++ và sl[R + 1]--. Sau khi xử lý xong tất cả các lệnh, ta cộng dồn: sl[i] += sl[i - 1] với $i$ từ $1$ đến $N$. Khi đó $sl[i]$ chính là số đoạn phủ lên vị trí $i$.Vì sao đúng? Sau khi cộng dồn, $sl[i]$ bằng tổng các "dấu" ở vị trí $\le i$. Một đoạn $[L, R]$ để lại dấu $+1$ ở $L$ và $-1$ ở $R + 1$, nên nó đóng góp $+1$ cho mọi $i$ trong $[L, R]$ (đã qua dấu $+1$ nhưng chưa tới dấu $-1$), còn với $i \lt L$ thì chưa có gì và với $i \gt R$ thì $+1 - 1 = 0$. Bạn nào chưa biết mảng hiệu có thể đọc thêm bài viết rất hay trên VNOI Wiki – Mảng cộng dồn và mảng hiệu nha.
Vì $N \le 10^5$ khá nhỏ nên dùng mảng hiệu sẽ không tốn nhiều dung lượng. Sau đó ta mất $O(N)$ để tính lại mảng $sl$. Các bạn nhập thử dữ liệu nhỏ vào khung minh hoạ dưới đây và bấm Tiếp: hàng trên là màu thật của dây đèn, hàng dưới là mảng hiệu – để ý mỗi lệnh chỉ "đánh dấu" đúng 2 ô thôi nha:
Source code để các bạn tham khảo nếu làm theo hướng này:
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n, m, q, k, x[100005], sl[200005], p;
signed main(){
if(fopen("dayden.inp", "r")){
freopen("dayden.inp", "r", stdin);
freopen("dayden.out", "w", stdout);
}
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m >> q >> k;
for (int i = 1; i <= m; i++){
cin >> x[i];
sl[max((long long)1, x[i] - k)]++;
sl[x[i] + k + 1]--;
}
for (int i = 1; i <= n; i++) sl[i] += sl[i - 1];
for (int i = 1; i <= q; i++){
cin >> p;
if (sl[p] % 2 == 1) cout << 'D' << endl;
else cout << 'V' << endl;
}
}import sys, os
def main():
if os.path.exists('dayden.inp'):
sys.stdin = open('dayden.inp')
sys.stdout = open('dayden.out', 'w')
data = sys.stdin.read().split()
n, m, q, k = int(data[0]), int(data[1]), int(data[2]), int(data[3])
sl = [0] * (2 * n + 3)
for i in range(m):
x = int(data[4 + i])
sl[max(1, x - k)] += 1
sl[x + k + 1] -= 1
for i in range(1, n + 1):
sl[i] += sl[i - 1]
res = []
for i in range(q):
p = int(data[4 + m + i])
res.append('D' if sl[p] % 2 == 1 else 'V')
print('\n'.join(res))
main()
sys.stdout.flush()sl[x[i] + k + 1], mà $X_i \le N$ và $K \le N$ nên chỉ số này có thể lên tới $2N + 1 \approx 2 \cdot 10^5$. Vị trí lớn hơn $N$ thì không bao giờ được dùng khi cộng dồn, nhưng vẫn phải có chỗ để ghi, không thì truy cập ra ngoài mảng.Đánh giá độ phức tạp của cách làm này:
- Không gian: mảng $sl$ cỡ $2N$ phần tử: $O(N)$.
- Thời gian: mỗi lệnh chỉ còn $O(1)$, cộng dồn một lần $O(N)$, trả lời mỗi câu hỏi $O(1)$: tổng $O(N + M + Q)$.
long long là khoảng 16 GB bộ nhớ – không thể nào. Vòng cộng dồn $O(N)$ cũng quá chậm. Phải nghĩ tiếp thôi!Subtask 3Nén số + mảng hiệu – O((M + Q) log(M + Q))
Lần này $N$ đã tăng lên $10^9$ và gây khó khăn cho chúng ta khi sử dụng mảng hiệu vì tốn quá nhiều dung lượng. Chúng ta sẽ tìm cách xử lý điều này.
Nhận thấy rằng cho dù $N$ lớn nhưng thực chất ta chỉ cần quan tâm các vị trí như $\max(1, X_i - K)$ và $X_i + K + 1$ với các mã lệnh được áp lên (đây là những chỗ mảng hiệu bị "đánh dấu"), và những vị trí $P_i$ cần trả lời truy vấn. Những số không được đề cập đến còn lại thực sự vô dụng trong suốt quá trình xử lý bài toán, và chúng ta chỉ cần quan tâm đến tính thứ tự của các vị trí được quan tâm. Tối đa chỉ có $2M + Q \le 3 \cdot 10^5$ vị trí như vậy.
Tại sao làm vậy vẫn đúng? Sau khi cộng dồn, giá trị ở một vị trí $P$ bằng tổng các dấu $+1/-1$ đặt ở những vị trí $\le P$. Mọi dấu đều được đặt tại các vị trí được quan tâm, và $P$ cũng là một vị trí được quan tâm, nên việc "co" những khoảng trống không có dấu nào lại hoàn toàn không làm thay đổi tổng này. Nói cách khác: giữa hai vị trí được quan tâm liên tiếp, màu đèn không đổi.
Trong code của mình, mình dùng map<int,int> st để làm việc này cho gọn: thêm các vị trí vào st (map tự sắp xếp tăng dần và tự bỏ trùng), sau đó duyệt st từ nhỏ đến lớn và gán lại st[vị trí] = ++_ – tức là chỉ số mới. Lúc thêm vào thì st[...]++ chỉ để tạo khoá trong map, giá trị đếm lúc đó không quan trọng vì sẽ bị ghi đè.
Các bạn xem khung minh hoạ quá trình nén số và làm mảng hiệu trên chỉ số mới (thử nút N = 10^9 để thấy $N$ lớn cỡ nào cũng không sao nha):
Source code để các bạn tham khảo nếu làm theo hướng này:
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n, m, q, k, x[100005], p[100005], sl[300005];
signed main(){
if(fopen("dayden.inp", "r")){
freopen("dayden.inp", "r", stdin);
freopen("dayden.out", "w", stdout);
}
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m >> q >> k;
map<int,int> st;
for (int i = 1; i <= m; i++){
cin >> x[i];
st[max((long long)1, x[i] - k)]++;
st[x[i] + k + 1]++;
}
for (int i = 1; i <= q; i++){
cin >> p[i];
st[p[i]]++;
}
int _ = 0;
for (auto i : st) st[i.first] = ++_;
for (int i = 1; i <= m; i++){
int curL = st[max((long long)1, x[i] - k)];
int curR = st[x[i] + k + 1];
sl[curL]++;
sl[curR]--;
}
for (int i = 1; i <= _; i++) sl[i] += sl[i - 1];
for (int i = 1; i <= q; i++){
if (sl[st[p[i]]] % 2 == 1) cout << 'D' << endl;
else cout << 'V' << endl;
}
}import sys, os
def main():
if os.path.exists('dayden.inp'):
sys.stdin = open('dayden.inp')
sys.stdout = open('dayden.out', 'w')
data = sys.stdin.read().split()
n, m, q, k = int(data[0]), int(data[1]), int(data[2]), int(data[3])
x = [int(v) for v in data[4:4 + m]]
p = [int(v) for v in data[4 + m:4 + m + q]]
# các vị trí "được quan tâm": đầu đoạn, sau cuối đoạn, vị trí hỏi
keys = set()
for v in x:
keys.add(max(1, v - k))
keys.add(v + k + 1)
for v in p:
keys.add(v)
st = {}
cnt = 0
for key in sorted(keys): # nén số: đánh lại chỉ số 1, 2, 3, ...
cnt += 1
st[key] = cnt
sl = [0] * (cnt + 2)
for v in x:
sl[st[max(1, v - k)]] += 1
sl[st[v + k + 1]] -= 1
for i in range(1, cnt + 1):
sl[i] += sl[i - 1]
print('\n'.join('D' if sl[st[v]] % 2 == 1 else 'V' for v in p))
main()
sys.stdout.flush()Giải thích 1 số chỗ trong code ở trên:
#define int long long: vì $X_i + K + 1$ có thể lên tới $2 \cdot 10^9 + 1$, vượt quá giới hạn củaint(khoảng $2.1 \cdot 10^9$) nên mình cho tất cả thànhlong longcho chắc. Lúc này hàmmainphải khai báo làsigned main().max((long long)1, x[i] - k): hàmmaxyêu cầu 2 tham số cùng kiểu, màx[i] - klàlong longnên số1cũng phải ép sanglong long.for (auto i : st) st[i.first] = ++_;: duyệt map theo thứ tự khoá tăng dần, gán lại giá trị là chỉ số mới $1, 2, 3, \ldots$. Biến_cuối cùng chính là số vị trí sau khi nén (tối đa $3 \cdot 10^5$, nên mảngsl[300005]là đủ).- Bản Python dùng
set+sorted+dictthay chomapcủa C++, ý tưởng y hệt.
Đánh giá độ phức tạp của cách làm này:
- Không gian: map và mảng $sl$ có tối đa $2M + Q$ phần tử: $O(M + Q)$, không còn phụ thuộc vào $N$ nữa.
- Thời gian: mỗi thao tác trên
maptốn $O(\log(M + Q))$, có $O(M + Q)$ thao tác như vậy; cộng dồn $O(M + Q)$. Tổng là $O((M + Q) \log(M + Q))$.
endl, mà endl ngoài xuống dòng còn ép đẩy dữ liệu ra ngay (flush). Với $10^5$ dòng thì vẫn ổn, nhưng các bạn đổi thành '\n' sẽ chạy nhanh hơn một chút đó. Trên máy mình, test $M = Q = 10^5$, $N = 10^9$ chạy khoảng 0.6 – 0.9 giây tuỳ lần đo; đổi sang '\n' thì giảm được khoảng 0.1 – 0.3 giây.- 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