Tuyển sinh 🎓 Mình nhận đào tạo lập trình giải thuật thi đấu: thi vào lớp 10 chuyên tin · thi học sinh giỏi tin học cấp tỉnh/thành · thi vào đội tuyển quốc gia · Olympic tin học sinh viên / ICPC · phỏng vấn thuật toán. Bấm vào đây để xem thông tin khóa học → Xem khóa học
Thi thử miễn phí
🏆 Thi thử HSG Tin học tuần này trên ClueOJ
Mở công khai cho mọi người · đề do thầy Nguyễn Việt Nam Sơn biên soạn
Lịch thi, đề cũ & lời giải →

Đèn Lồng (HSG12 Hà Nội 2025 – Bài 3)

Đèn Lồng (HSG12 Hà Nội 2025 – Bài 3)
Nguồn: Đề thi HSG lớp 12 Hà Nội 2025 – Bài 3 Độ khó: Khá Tìm kiếm nhị phân Cửa sổ trượt Prefix sum Tham lam

Đề bài

Bài III. Đèn lồng (4,0 điểm)

Khu phố Nam ở đã treo $N$ chiếc đèn lồng, được đánh số từ $1$ đến $N$, từ trái sang phải. Ban đầu, chiếc đèn lồng thứ $i$ có màu kí hiệu $A_i$ $(1 \le A_i \le 9)$. Một dãy đèn lồng liên tiếp được gọi là "cát tường" nếu có không quá $K$ màu khác nhau, độ dài của dãy đèn được tính là số lượng đèn trong dãy đó.

Để chào mừng năm mới sắp đến, khu phố của Nam quyết định thay một số đèn sao cho xuất hiện dãy đèn "cát tường" là dài nhất có thể. Do ngân sách có hạn, khu phố chỉ thay thế được tối đa $X$ chiếc đèn lồng.

Ví dụ: Với $K = 2$, xét dãy $6$ đèn lồng liên tiếp có kí hiệu màu của từng chiếc là $\{4, 1, 5, 3, 3, 1\}$. Dãy này đang xuất hiện dãy "cát tường" dài nhất có độ dài $3$ là $\{5, 3, 3\}$ hoặc $\{3, 3, 1\}$. Khi $X = 1$, ta có thể thay đèn thứ $3$ thành màu $1$ hoặc màu $3$, được dãy đèn có kí hiệu màu là $\{4, 1, 1, 3, 3, 1\}$ hoặc $\{4, 1, 3, 3, 3, 1\}$ thì sẽ xuất hiện dãy "cát tường" dài nhất có độ dài $5$.

Yêu cầu: Em hãy lập trình xác định độ dài lớn nhất của dãy đèn "cát tường" sau khi thay thế tối đa $X$ chiếc đèn lồng.

Dữ liệu vào từ file văn bản DENLONG.INP:

  • Dòng đầu tiên gồm ba số nguyên dương lần lượt là $N, K, X$ $(1 \le K \le 9;\ 1 \le X \le N \le 10^5)$ với $N$ là số đèn lồng đã treo, $K$ là giá trị lớn nhất về số màu trong dãy đèn "cát tường", $X$ là số lượng đèn nhiều nhất có thể thay thế;
  • Dòng thứ hai gồm $N$ số nguyên dương $A_i$ mô tả màu của chiếc đèn thứ $i$ $(1 \le A_i \le 9)$.

Kết quả ghi ra file văn bản DENLONG.OUT: Một số nguyên duy nhất là kết quả của bài toán.

Ràng buộc:

  • Có $40\%$ số test ứng với $40\%$ số điểm của bài thoả mãn: $N \le 10^2;\ 1 \le A_i \le 2$;
  • $30\%$ số test khác ứng với $30\%$ số điểm của bài thoả mãn: $N \le 10^3;\ K = X = 1$;
  • $20\%$ số test khác ứng với $20\%$ số điểm của bài thoả mãn: $N \le 10^5;\ K = 1$;
  • $10\%$ số test còn lại ứng với $10\%$ số điểm của bài không có ràng buộc gì thêm.

Lưu ý: trên hệ thống chấm online CLUE OJ thì đọc dữ liệu từ bàn phím và in kết quả ra màn hình (giới hạn trên CLUE OJ: 1 giây, 1 GB).

DENLONG.INP
6 2 2
1 9 3 2 3 5
DENLONG.OUT
5

Giải thích (trong đề): Một trong những cách thay thế $2$ chiếc đèn để khu phố xuất hiện dãy $5$ đèn liên tiếp "cát tường" là: thay thế đèn thứ $2$ thành màu $3$, thay thế đèn thứ $4$ thành màu $3$. Dãy đèn sau khi thay thế sẽ có màu: $\{1, 3, 3, 3, 3, 5\}$.

Lời mở đầu

Đây là bài 3 trong đề thi học sinh giỏi Tin học lớp 12 thành phố Hà Nội năm 2025. Bài này chia subtask rất "có tâm": mỗi subtask là một bậc thang kiến thức – vét cạn, mảng cộng dồn (prefix sum), chặt nhị phân, rồi cửa sổ trượt. Mình viết lời giải chi tiết đủ cả 4 subtask để nhiều bạn được tham khảo luôn, nhất là các bạn đang ôn thi HSG cần luyện kỹ năng "ăn điểm từng subtask". 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é:

Link nộp bài

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 OJ

Tóm tắt đề: có dãy $N$ màu $A_1, \ldots, A_N$ (mỗi màu từ $1$ đến $9$). Được đổi màu tối đa $X$ chiếc (đổi sang màu bất kỳ). Sau khi đổi, tìm đoạn liên tiếp dài nhất mà trong đoạn có không quá $K$ màu khác nhau.

Mình giải thích ví dụ để bạn nào chưa hiểu đề sẽ hiểu rõ. Dãy ban đầu ($K = 2$, $X = 2$):

112933425365

Xét đoạn đèn $2..6$ là $\{9, 3, 2, 3, 5\}$: có $4$ màu khác nhau ($9, 3, 2, 5$), mà chỉ được giữ tối đa $K = 2$ màu. Màu $3$ xuất hiện $2$ lần, các màu $9, 2, 5$ mỗi màu $1$ lần. Ta giữ màu $3$ và một màu nữa, ví dụ màu $5$, rồi đổi đèn màu $9$ và đèn màu $2$ sang màu $3$ – tốn đúng $2$ lần thay $\le X$:

112333435365

Được đoạn $5$ đèn liên tiếp chỉ có $2$ màu ($3$ và $5$). Còn cả $6$ đèn thì có $5$ màu khác nhau, phải giữ $2$ màu (nhiều nhất là màu $3$ với $2$ đèn và một màu $1$ đèn) nên phải thay $6 - 2 - 1 = 3 \gt X$ đèn – không được. Vậy đáp án là $5$.

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Subtask 1Chỉ có 2 màu – vét cạn O(N³)

Vì $A_i \le 2$ nên trong mảng $a$ sẽ có không quá $2$ giá trị phân biệt. Do đó, nếu $K \ge 2$ thì cả dãy đã là "cát tường", đáp án luôn là $N$.

Việc còn lại là xử lý trường hợp $K = 1$ (cả đoạn phải cùng một màu). Ta có thể duyệt các đoạn $(i, j)$ và xem xét có thể biến đổi đoạn $(i, j)$ thành một đoạn thoả mãn hay không. Gọi:

  • $sl_1$: số đèn có giá trị là $1$ trong đoạn.
  • $sl_2$: số đèn có giá trị là $2$ trong đoạn.

Để biến đổi đoạn $(i, j)$ thành đoạn chỉ có một màu, ta chỉ có hai lựa chọn: chuyển hết các đèn màu $1$ thành màu $2$ (thay $sl_1$ đèn), hoặc chuyển hết các đèn màu $2$ thành màu $1$ (thay $sl_2$ đèn). Do đó số lần thay tối thiểu để biến đổi đoạn $(i, j)$ thành dãy thỏa mãn là $\min(sl_1, sl_2)$. Khi này chỉ cần kiểm tra xem nó có vượt quá $X$ hay không.

Ý chính subtask 1
$K \ge 2$: đáp án $= N$. $K = 1$: với mỗi đoạn $(i, j)$, nếu $\min(sl_1, sl_2) \le X$ thì cập nhật $ans = \max(ans, j - i + 1)$.

Source code để các bạn tham khảo nếu làm theo hướng này:

#include<bits/stdc++.h>
using namespace std;
int n, k, x, a[100005];
namespace sub1{
    int solve(){
        if (k >= 2) return n;
        int ans = 0;
        for (int i = 1; i <= n; i ++){
            for (int j = i; j <= n; j ++){
                int sl_1 = 0, sl_2 = 0;
                for (int k = i; k <= j; k ++){
                    if (a[k] == 1) sl_1 ++;
                    else sl_2 ++;
                }
                if (min(sl_1, sl_2) <= x){
                    ans = max(ans, j - i + 1);
                }
            }
        }
        return ans;
    }
};
int main(){
    if(fopen("DENLONG.inp", "r")){
        freopen("DENLONG.inp", "r", stdin);
        freopen("DENLONG.out", "w", stdout);
    }
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> k >> x;
    for (int i = 1; i <= n; i ++) cin >> a[i];
    cout << sub1::solve() << endl;
}
import sys, os

def solve():
    if k >= 2:
        return n
    ans = 0
    for i in range(1, n + 1):
        for j in range(i, n + 1):
            sl_1 = sl_2 = 0
            for t in range(i, j + 1):
                if a[t] == 1:
                    sl_1 += 1
                else:
                    sl_2 += 1
            if min(sl_1, sl_2) <= x:
                ans = max(ans, j - i + 1)
    return ans

if os.path.exists("DENLONG.inp"):
    sys.stdin = open("DENLONG.inp", "r")
    sys.stdout = open("DENLONG.out", "w")
data = sys.stdin.buffer.read().split()
n, k, x = int(data[0]), int(data[1]), int(data[2])
a = [0] + [int(v) for v in data[3:3 + n]] + [0]
print(solve())

Khung chạy tay dưới đây mặc định dùng một test thuộc subtask 1. Nút Test đề (ngoài subtask) cho thấy code subtask 1 in ra $6$ – sai, vì test của đề có màu tới $9$, không thuộc subtask này.

C++▶ Chạy tay từng dòng codeSubtask 1 (A ≤ 2): K ≥ 2 thì in N; K = 1 thì thử mọi đoạn, chi phí = min(số đèn màu 1, số đèn màu 2).
Dữ liệu mẫu:
1#include<bits/stdc++.h>
2using namespace std;
3int n, k, x, a[100005];
4namespace sub1{
5 int solve(){
6 if (k >= 2) return n;
7 int ans = 0;
8 for (int i = 1; i <= n; i ++){
9 for (int j = i; j <= n; j ++){
10 int sl_1 = 0, sl_2 = 0;
11 for (int k = i; k <= j; k ++){
12 if (a[k] == 1) sl_1 ++;
13 else sl_2 ++;
14 }
15 if (min(sl_1, sl_2) <= x){
16 ans = max(ans, j - i + 1);
17 }
18 }
19 }
20 return ans;
21 }
22};
23int main(){
24 if(fopen("DENLONG.inp", "r")){
25 freopen("DENLONG.inp", "r", stdin);
26 freopen("DENLONG.out", "w", stdout);
27 }
28 ios::sync_with_stdio(0);
29 cin.tie(0);
30 cin >> n >> k >> x;
31 for (int i = 1; i <= n; i ++) cin >> a[i];
32 cout << sub1::solve() << endl;
33}

Giải thích 1 số chỗ trong code ở trên: biến lặp trong cùng được đặt tên k, trùng tên với biến toàn cục $k$ (số màu tối đa). Trong vòng for đó, k là biến cục bộ "che" mất biến toàn cục, nhưng vì ta đã dùng $k$ toàn cục ở dòng if (k >= 2) trước rồi nên không ảnh hưởng gì. Code vẫn đúng, nhưng các bạn nên tránh đặt trùng tên như vậy để khỏi nhầm nhé.

Đánh giá độ phức tạp: có $O(N^2)$ đoạn, mỗi đoạn đếm lại mất $O(N)$ nên là $O(N^3)$. Với $N \le 100$ là cỡ $10^6$ phép tính, chạy tức thì.

Không gian$O(N)$
Thời gian$O(N^3)$

Subtask 2K = 1: thử từng màu đích – O(9·N²)

Ta có $K = 1$, điều này có nghĩa ta phải tìm cách thay đổi mảng $a$ sao cho có một dãy phần tử liên tiếp chỉ có các phần tử giống nhau là dài nhất có thể. Gọi giá trị chung của các phần tử trong đoạn đó là $g$. Vì chỉ có $9$ màu, ta sẽ duyệt qua các giá trị có thể của $g$ (từ $1$ đến $9$).

Sau đó, đối với mỗi đoạn $(j, k)$, ta xem phải tốn bao nhiêu lần thay để chuyển hết đoạn $(j, k)$ về cùng bằng $g$. Dễ thấy nó bằng độ dài của đoạn trừ đi số lượng phần tử đã bằng $g$ ngay từ đầu, hay nói cách khác là $val$ – số lượng phần tử không bằng $g$ trong đoạn. Cố định đầu $j$, mỗi lần tăng đầu cuối $k$ thêm $1$ thì ta cập nhật số phần tử bằng $g$ (biến sl) dễ dàng trong $O(1)$, không phải đếm lại cả đoạn như subtask 1. Cuối cùng kiểm tra xem số lần thay đó có vượt quá $X$ hay không, nếu không thì cập nhật kết quả.

Công thức
Với màu đích $g$ và đoạn $(j, k)$: $val = (k - j + 1) - sl$, trong đó $sl$ là số đèn màu $g$ trong đoạn. Nếu $val \le X$ thì $ans = \max(ans, k - j + 1)$.

Source code để các bạn tham khảo nếu làm theo hướng này:

#include<bits/stdc++.h>
using namespace std;
int n, k, x, a[100005];
namespace sub2{
    int solve(){
        int ans = 0;
        for (int i = 1; i <= 9; i ++){
            for (int j = 1; j <= n; j ++){
                int sl = 0;
                for (int k = j; k <= n; k ++){
                    if (a[k] == i) sl ++;
                    if (abs((k - j + 1) - sl) <= x){
                        ans = max(ans, k - j + 1);
                    }
                }
            }
        }
        return ans;
    }
};
int main(){
    if(fopen("DENLONG.inp", "r")){
        freopen("DENLONG.inp", "r", stdin);
        freopen("DENLONG.out", "w", stdout);
    }
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> k >> x;
    for (int i = 1; i <= n; i ++) cin >> a[i];
    cout << sub2::solve() << endl;
}
import sys, os

def solve():
    ans = 0
    for i in range(1, 10):
        for j in range(1, n + 1):
            sl = 0
            for t in range(j, n + 1):
                if a[t] == i:
                    sl += 1
                if abs((t - j + 1) - sl) <= x:
                    ans = max(ans, t - j + 1)
    return ans

if os.path.exists("DENLONG.inp"):
    sys.stdin = open("DENLONG.inp", "r")
    sys.stdout = open("DENLONG.out", "w")
data = sys.stdin.buffer.read().split()
n, k, x = int(data[0]), int(data[1]), int(data[2])
a = [0] + [int(v) for v in data[3:3 + n]] + [0]
print(solve())
C++▶ Chạy tay từng dòng codeSubtask 2 (K = 1): thử màu đích i = 1..9, với mỗi đoạn [j, k] chi phí = độ dài − số đèn đã có màu i.
Dữ liệu mẫu:
1#include<bits/stdc++.h>
2using namespace std;
3int n, k, x, a[100005];
4namespace sub2{
5 int solve(){
6 int ans = 0;
7 for (int i = 1; i <= 9; i ++){
8 for (int j = 1; j <= n; j ++){
9 int sl = 0;
10 for (int k = j; k <= n; k ++){
11 if (a[k] == i) sl ++;
12 if (abs((k - j + 1) - sl) <= x){
13 ans = max(ans, k - j + 1);
14 }
15 }
16 }
17 }
18 return ans;
19 }
20};
21int main(){
22 if(fopen("DENLONG.inp", "r")){
23 freopen("DENLONG.inp", "r", stdin);
24 freopen("DENLONG.out", "w", stdout);
25 }
26 ios::sync_with_stdio(0);
27 cin.tie(0);
28 cin >> n >> k >> x;
29 for (int i = 1; i <= n; i ++) cin >> a[i];
30 cout << sub2::solve() << endl;
31}

Giải thích 1 số chỗ trong code ở trên: abs((k - j + 1) - sl) – thật ra độ dài đoạn luôn $\ge sl$ nên hiệu này không bao giờ âm, có abs hay không đều như nhau. Code này không dùng tới điều kiện $X = 1$ nên chạy đúng cho mọi $X$ (miễn $K = 1$).

Đánh giá độ phức tạp: $9$ màu đích, mỗi màu duyệt $O(N^2)$ đoạn, mỗi đoạn $O(1)$ nên là $O(9 \cdot N^2)$. Với $N \le 10^3$ là khoảng $9 \cdot 10^6$ phép tính – ổn. Nhưng với $N = 10^5$ thì quá chậm (mình đo bản C++ mất khoảng 164 giây).

Không gian$O(N)$
Thời gian$O(9 \cdot N^2)$

Subtask 3K = 1: mảng cộng dồn + chặt nhị phân – O(9·N log N)

Vì $K = 1$ cũng khá tương tự subtask 2 nên ta sẽ tìm cách tối ưu subtask 2. Ta thấy có hai điểm khiến độ phức tạp là $O(9 \cdot N^2)$:

  • Tính toán giá trị $val$.
  • Duyệt tất cả các đoạn $(i, j)$ khá mất thời gian.

Tính nhanh $val$: với mỗi màu đích $g$, ta tạo một mảng prefix sum với $pre_i$ là số các giá trị không bằng $g$ trong mảng từ $1$ đến $i$. Khi này, ta có thể tính $val$ của bất kì đoạn $[j, mid]$ nào trong $O(1)$: $val = pre_{mid} - pre_{j-1}$.

Không duyệt hết các đoạn: với mỗi đầu $j$, nếu đoạn $(j, mid)$ có khả năng chuyển thành đoạn thoả mãn thì đoạn $(j, mid - 1)$ cũng có khả năng – vì $mid$ càng tăng thì $val$ càng tăng (hoặc giữ nguyên), mà nếu $val$ ở $mid$ vẫn $\le X$ thì ở $mid - 1$ chắc chắn cũng thế. Tính chất "đơn điệu" này cho phép ta chặt nhị phân tìm $mid$ lớn nhất thoả $val \le X$.

Ý chính subtask 3
$pre_t = pre_{t-1} + [a_t \ne g]$. Với mỗi $j$: chặt nhị phân $mid \in [j, N]$, nếu $pre_{mid} - pre_{j-1} \le X$ thì cập nhật $ans = \max(ans, mid - j + 1)$ và tìm tiếp bên phải, ngược lại tìm bên trái.

Source code để các bạn tham khảo nếu làm theo hướng này:

#include<bits/stdc++.h>
using namespace std;
int n, k, x, a[100005];
namespace sub3{
    int pre[100005];
    int solve(){
        int ans = 0;
        for (int i = 1; i <= 9; i ++){
            for (int j = 1; j <= n; j ++) pre[j] = 0;
            for (int j = 1; j <= n; j ++){
                pre[j] = pre[j - 1];
                if (a[j] != i) pre[j] ++;
            }
            for (int j = 1; j <= n; j ++){
                int l = j, r = n, mid;
                while (l <= r){
                    mid = (l + r) / 2;
                    if (pre[mid] - pre[j - 1] <= x){
                        l = mid + 1;
                        ans = max(ans, mid - j + 1);
                    }
                    else r = mid - 1;
                }
            }
        }
        return ans;
    }
};
int main(){
    if(fopen("DENLONG.inp", "r")){
        freopen("DENLONG.inp", "r", stdin);
        freopen("DENLONG.out", "w", stdout);
    }
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> k >> x;
    for (int i = 1; i <= n; i ++) cin >> a[i];
    cout << sub3::solve() << endl;
}
import sys, os

def solve():
    ans = 0
    pre = [0] * (n + 1)
    for i in range(1, 10):
        for j in range(1, n + 1):
            pre[j] = pre[j - 1]
            if a[j] != i:
                pre[j] += 1
        for j in range(1, n + 1):
            l, r = j, n
            while l <= r:
                mid = (l + r) // 2
                if pre[mid] - pre[j - 1] <= x:
                    l = mid + 1
                    ans = max(ans, mid - j + 1)
                else:
                    r = mid - 1
    return ans

if os.path.exists("DENLONG.inp"):
    sys.stdin = open("DENLONG.inp", "r")
    sys.stdout = open("DENLONG.out", "w")
data = sys.stdin.buffer.read().split()
n, k, x = int(data[0]), int(data[1]), int(data[2])
a = [0] + [int(v) for v in data[3:3 + n]] + [0]
print(solve())
C++▶ Chạy tay từng dòng codeSubtask 3 (K = 1): pre[t] = số đèn khác màu i trong [1, t]; với mỗi j chặt nhị phân mid xa nhất có pre[mid] − pre[j−1] ≤ x.
Dữ liệu mẫu:
1#include<bits/stdc++.h>
2using namespace std;
3int n, k, x, a[100005];
4namespace sub3{
5 int pre[100005];
6 int solve(){
7 int ans = 0;
8 for (int i = 1; i <= 9; i ++){
9 for (int j = 1; j <= n; j ++) pre[j] = 0;
10 for (int j = 1; j <= n; j ++){
11 pre[j] = pre[j - 1];
12 if (a[j] != i) pre[j] ++;
13 }
14 for (int j = 1; j <= n; j ++){
15 int l = j, r = n, mid;
16 while (l <= r){
17 mid = (l + r) / 2;
18 if (pre[mid] - pre[j - 1] <= x){
19 l = mid + 1;
20 ans = max(ans, mid - j + 1);
21 }
22 else r = mid - 1;
23 }
24 }
25 }
26 return ans;
27 }
28};
29int main(){
30 if(fopen("DENLONG.inp", "r")){
31 freopen("DENLONG.inp", "r", stdin);
32 freopen("DENLONG.out", "w", stdout);
33 }
34 ios::sync_with_stdio(0);
35 cin.tie(0);
36 cin >> n >> k >> x;
37 for (int i = 1; i <= n; i ++) cin >> a[i];
38 cout << sub3::solve() << endl;
39}

Đánh giá độ phức tạp: mỗi màu đích tốn $O(N)$ để dựng mảng $pre$ và $O(N \log N)$ để chặt nhị phân cho $N$ đầu đoạn, nên tổng cộng $O(9 \cdot N \log N)$. Bản C++ với $N = 10^5$ chạy khoảng 0.2 giây.

Không gian$O(N)$
Thời gian$O(9 \cdot N \log N)$
Một cách khác cho K = 1
Thay vì chặt nhị phân cho từng $j$, vì tính đơn điệu ở trên các bạn có thể dùng hai con trỏ (đầu đoạn chỉ tăng, cuối đoạn chỉ tăng) để được $O(9 \cdot N)$. Nhưng với $N \le 10^5$ thì chặt nhị phân như trên đã quá đủ nhanh rồi.

Subtask 4Chặt nhị phân độ dài + cửa sổ trượt – O(9·N log N)

Giờ $K$ bất kỳ. Ta có một nhận xét như sau: nếu tồn tại một đoạn $(i, j)$ có độ dài là $f$ vẫn có khả năng chuyển về một dãy "cát tường" thì cũng sẽ tồn tại một đoạn độ dài $f - 1$ có khả năng chuyển về một dãy thỏa mãn – cụ thể là đoạn $(i, j - 1)$ (bỏ bớt một đèn thì số đèn phải thay chỉ giảm hoặc giữ nguyên).

Nghĩa là nếu độ dài $f$ "làm được" thì mọi độ dài nhỏ hơn đều "làm được" – lại là tính đơn điệu! Đến đây, ta sẽ chặt nhị phân $f$ và kiểm tra xem có đoạn nào độ dài $f$ thỏa mãn không.

Số lần thay để chuyển một đoạn có $d$ màu khác nhau thành không quá $K$ màu có thể xử lý như sau:

  • Nếu $d \le K$: đoạn đã thoả mãn sẵn, tốn $0$ lần thay.
  • Nếu $d \gt K$: phải chọn ra $d - K$ màu để "xoá sổ" – chuyển hết các đèn có màu đó thành một trong $K$ màu còn lại. Ta tham lam chọn $d - K$ màu có số lượng đèn ít nhất, bằng cách sắp xếp lại số lần xuất hiện của mỗi màu và chọn $d - K$ giá trị đầu tiên. Tổng số đèn của các màu bị xoá sổ chính là số lần thay.

Vì chỉ có $9$ màu có thể xảy ra nên ở đây ta có thể xử lý trâu (đếm, sắp xếp mảng tối đa $9$ phần tử) mà không lo chậm.

Chi phí của một đoạn
Gọi $c_1 \le c_2 \le \dots \le c_d$ là số lượng đèn của từng màu có mặt trong đoạn (đã sắp xếp tăng). Số lần thay ít nhất $= c_1 + c_2 + \dots + c_{d-K}$ (bằng $0$ nếu $d \le K$). Đoạn đổi được thành "cát tường" khi tổng này $\le X$.

Kiểm tra độ dài $f$: ta duyệt $i$ từ $1$ đến $N - f + 1$ và xét đoạn $[i, i + f - 1]$. Điều còn cấn lại ở đây là làm sao duy trì được mảng tần suất xuất hiện của các màu cho nhanh. Ta nhận xét khi chuyển từ đoạn $(i, i + f - 1)$ sang $(i + 1, i + f)$ thì chỉ khác biệt ở chỗ là xoá giá trị $a_i$ và thêm giá trị $a_{i+f}$ – đây chính là kỹ thuật cửa sổ trượt, mỗi lần trượt cập nhật mảng đếm trong $O(1)$.

Minh hoạ chặt nhị phân + cửa sổ trượt

Em nhập $K$, $X$ và dãy màu rồi bấm Tiếp: mỗi bước là một cửa sổ độ dài $mid$ (viền vàng). Bên dưới là số lượng đèn của từng màu trong cửa sổ: màu giữ lại (xanh) và màu phải đổi (đỏ, gạch ngang).

Ví dụ nhanh:

Source code để các bạn tham khảo nếu làm theo hướng này (đây cũng là code đầy đủ điểm của bài):

#include<bits/stdc++.h>
using namespace std;
int n, k, x, a[100005];
namespace sub4{
    int cnt[10];
    int check(int l){
        for (int i = 1; i <= 9; i ++) cnt[i] = 0;
        for (int i = 1; i <= l; i ++){
            cnt[a[i]] ++;
        }
        for (int i = 1; i <= n - l + 1; i ++){
            int hic = 0;
            vector<int> meo;
            for (int i = 1; i <= 9; i ++){
                if (cnt[i]){
                    hic ++;
                    meo.push_back(cnt[i]);
                }
            }
            int diff = 0;
            if (hic > k) diff = hic - k;
            int sl = 0;
            sort(meo.begin(), meo.end());
            while(diff --){
                sl += meo[0];
                meo.erase(meo.begin());
            }
            if (sl <= x) return 1;
            cnt[a[i]] --;
            cnt[a[i + l]] ++;
        }
        return 0;
    }
    int solve(){
        int l = 1, r = n, mid, ans = 0;
        while (l <= r){
            mid = (l + r) / 2;
            if (check(mid)){
                l = mid + 1;
                ans = max(ans, mid);
            }
            else r = mid - 1;
        }
        return ans;
    }
};
int main(){
    if(fopen("DENLONG.inp", "r")){
        freopen("DENLONG.inp", "r", stdin);
        freopen("DENLONG.out", "w", stdout);
    }
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> k >> x;
    for (int i = 1; i <= n; i ++) cin >> a[i];
    cout << sub4::solve() << endl;
}
import sys, os

def check(l):
    cnt = [0] * 10
    for i in range(1, l + 1):
        cnt[a[i]] += 1
    for i in range(1, n - l + 2):
        meo = sorted(c for c in cnt[1:] if c)
        hic = len(meo)
        diff = hic - k if hic > k else 0
        sl = sum(meo[:diff])
        if sl <= x:
            return True
        cnt[a[i]] -= 1
        cnt[a[i + l]] += 1
    return False

def solve():
    l, r, ans = 1, n, 0
    while l <= r:
        mid = (l + r) // 2
        if check(mid):
            l = mid + 1
            ans = max(ans, mid)
        else:
            r = mid - 1
    return ans

if os.path.exists("DENLONG.inp"):
    sys.stdin = open("DENLONG.inp", "r")
    sys.stdout = open("DENLONG.out", "w")
data = sys.stdin.buffer.read().split()
n, k, x = int(data[0]), int(data[1]), int(data[2])
a = [0] + [int(v) for v in data[3:3 + n]] + [0]
print(solve())
C++▶ Chạy tay từng dòng codeSubtask 4: chặt nhị phân độ dài l; check(l) trượt cửa sổ độ dài l, chi phí = tổng số đèn của (số màu − k) màu ít đèn nhất.
Dữ liệu mẫu:
1#include<bits/stdc++.h>
2using namespace std;
3int n, k, x, a[100005];
4namespace sub4{
5 int cnt[10];
6 int check(int l){
7 for (int i = 1; i <= 9; i ++) cnt[i] = 0;
8 for (int i = 1; i <= l; i ++){
9 cnt[a[i]] ++;
10 }
11 for (int i = 1; i <= n - l + 1; i ++){
12 int hic = 0;
13 vector<int> meo;
14 for (int i = 1; i <= 9; i ++){
15 if (cnt[i]){
16 hic ++;
17 meo.push_back(cnt[i]);
18 }
19 }
20 int diff = 0;
21 if (hic > k) diff = hic - k;
22 int sl = 0;
23 sort(meo.begin(), meo.end());
24 while(diff --){
25 sl += meo[0];
26 meo.erase(meo.begin());
27 }
28 if (sl <= x) return 1;
29 cnt[a[i]] --;
30 cnt[a[i + l]] ++;
31 }
32 return 0;
33 }
34 int solve(){
35 int l = 1, r = n, mid, ans = 0;
36 while (l <= r){
37 mid = (l + r) / 2;
38 if (check(mid)){
39 l = mid + 1;
40 ans = max(ans, mid);
41 }
42 else r = mid - 1;
43 }
44 return ans;
45 }
46};
47int main(){
48 if(fopen("DENLONG.inp", "r")){
49 freopen("DENLONG.inp", "r", stdin);
50 freopen("DENLONG.out", "w", stdout);
51 }
52 ios::sync_with_stdio(0);
53 cin.tie(0);
54 cin >> n >> k >> x;
55 for (int i = 1; i <= n; i ++) cin >> a[i];
56 cout << sub4::solve() << endl;
57}

Giải thích 1 số chỗ trong code ở trên:

  1. Trong hàm check, vòng lặp đếm màu for (int i = 1; i <= 9; i ++) dùng lại tên i trùng với biến của vòng lặp cửa sổ bên ngoài. Biến bên trong chỉ sống trong vòng for đó, nên khi ra tới cnt[a[i]] -- thì i lại là chỉ số cửa sổ – code vẫn đúng. Nhưng các bạn nên đặt tên khác (ví dụ c) để đọc code đỡ rối nhé.
  2. while(diff --): lặp đúng $diff$ lần (kiểm tra $diff \ne 0$ rồi mới giảm). Mỗi lần lấy phần tử nhỏ nhất meo[0] cộng vào $sl$ rồi xoá nó khỏi vector. Vì meo có tối đa $9$ phần tử nên erase ở đầu vector không tốn đáng kể.
  3. Ở cửa sổ cuối cùng ($i = n - l + 1$), lệnh cnt[a[i + l]] ++ truy cập a[n + 1]. Vì mảng a khai báo toàn cục (kích thước $100005$) nên a[n + 1] = 0, lệnh này chỉ tăng cnt[0] – không dùng tới, vô hại.
  4. Hàm check trả về $1$ ngay khi gặp cửa sổ đầu tiên thỏa mãn, không cần xét các cửa sổ còn lại.

Đánh giá độ phức tạp của cách làm này:

  • Không gian: $O(N)$ cho mảng $a$, mảng đếm chỉ $10$ phần tử.
  • Thời gian: mỗi lần check duyệt $O(N)$ cửa sổ, mỗi cửa sổ tốn khoảng $9$ bước đếm cộng sắp xếp tối đa $9$ phần tử (coi như hằng số), nên một lần check là $O(9 \cdot N)$. Chặt nhị phân gọi check khoảng $\log_2 N \approx 17$ lần nên tổng là $O(9 \cdot N \log N)$. Mình đo bản C++ với $N = 10^5$ chạy khoảng 0.1 – 0.6 giây tùy test.
Không gian$O(N)$
Thời gian$O(9 \cdot N \log N)$
Bạn nào code Python để ý
Bản Python của subtask 4 với $N = 10^5$ mình đo mất khoảng 1.4 – 3.5 giây, còn bản Python subtask 3 khoảng 8 giây – dễ bị TLE. Bài này nên nộp bằng C++ nhé.
Muốn nhanh hơn nữa?
Vì tính đơn điệu "đoạn $(i, j)$ được thì đoạn $(i + 1, j)$ cũng được", các bạn có thể bỏ chặt nhị phân và dùng hai con trỏ: tăng dần đầu cuối $j$, khi đoạn hết thoả mãn thì tăng đầu $i$. Mỗi bước tính lại chi phí bằng mảng đếm $9$ màu như trên, tổng $O(9 \cdot N)$. Với giới hạn của đề thì cách chặt nhị phân ở trên đã đủ điểm rồi.
Ghi chú của mình: code C++ và Python của cả 4 subtask đã được so với code vét cạn (thử mọi đoạn, chi phí = độ dài − tổng số đèn của $K$ màu nhiều nhất) trên 700 bộ test ngẫu nhiên nhỏ ($N \le 15$), mỗi code chỉ chạy trên các test thuộc đúng subtask của nó – khớp hết (3150 lượt chạy). Riêng công thức chi phí cũng được đối chiếu với cách thử mọi cách thay màu trên 285 bộ test rất nhỏ ($N \le 6$) – khớp hết. Thời gian với $N = 10^5$: subtask 4 (C++) khoảng 0.1 – 0.6 giây, subtask 3 (C++) khoảng 0.2 giây, còn subtask 2 (C++) mất khoảng 164 giây – đúng là chỉ dành cho $N \le 10^3$.
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 😇
Tự học thuật toán: khó ở đâu?
Đọc xong một bài giải là bước đầu. Phần lớn học sinh tự học sẽ gặp những trở ngại sau:
  • 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.
Học cùng thầy Nam Sơn, các trở ngại đó được gỡ bỏ:
  • 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