Hộp màu (COLORBOX
Đề bài
Vì có kết quả cao trong kỳ thi học sinh giỏi vừa qua nên Phát được mẹ thưởng cho một hộp màu tuyệt đẹp. Bộ màu ấy bao gồm $n$ cây màu được xếp theo thứ tự từ trái qua phải, cây màu thứ $i$ ($1 \le i \le n$) có màu được mô tả bởi một số nguyên $a_i$.
Tuy nhiên, có một số sơ suất trong quá trình sản xuất nên hộp màu của Phát có thể chứa một số cây màu giống nhau. Vì là một người thích sự hoàn hảo nên Phát muốn bỏ bớt một số cây màu sao cho những cây màu còn lại đôi một phân biệt với nhau.
Để làm vậy, Phát sẽ chọn nhiều nhất một đoạn con gồm các cây màu liên tiếp rồi bỏ chúng đi, tức là, Phát sẽ chọn hai số nguyên $l$ và $r$ thoả mãn $1 \le l \le r \le n$ rồi bỏ các cây màu từ vị trí $l$ đến vị trí $r$ và giữ nguyên các cây màu còn lại.
Hãy giúp Phát tìm ra số lượng cây màu bị bỏ đi ít nhất sao cho các cây màu còn lại thoả mãn điều kiện.
Input:
- Dòng đầu tiên chứa số nguyên $n$ ($1 \le n \le 10^6$) là số lượng cây màu.
- Dòng tiếp theo chứa $n$ số nguyên $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le n$).
Output: in ra một số nguyên duy nhất là số lượng cây màu bị bỏ đi.
Scoring:
- Subtask 1 (20% số điểm): $n \le 10^2$.
- Subtask 2 (20% số điểm): $n \le 10^3$.
- Subtask 3 (30% số điểm): $n \le 10^5$.
- Subtask 4 (30% số điểm): không có ràng buộc gì thêm.
4
1 1 2 225
1 4 1 4 52Giải thích:
- Trong ví dụ đầu tiên, Phát có thể bỏ đi các cây màu từ vị trí 2 đến vị trí 3.
- Trong ví dụ thứ hai, Phát có thể chọn một trong ba cách sau: bỏ đi các cây màu từ vị trí 1 đến vị trí 2; bỏ đi các cây màu từ vị trí 2 đến vị trí 3; bỏ đi các cây màu từ vị trí 3 đến vị trí 4.
Lời mở đầu
Bài này mình được một em học viên hỏi và mình đã hướng dẫn chi tiết cách thức giải quyết cho em ấy. Tin rằng sẽ có giá trị với nhiều bạn nên mình chia sẻ đề bài để các bạn thử sức làm, kèm thêm đó là lời giải để bạn nào không giải quyết được thì có thể tham khảo nhen. Hi vọng mang đến được giá trị cho các bạn 😇. Bài này các bạn có thể xem đề bài và nộp tại đây nha:
Bài này có thể giải quyết theo two pointers (2 con trỏ) với độ phức tạp $O(N)$. Mình sẽ trình bày ý tưởng trước, em hiểu sau đó thử tự cài đặt 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 OJLộ trình lời giải, bấm vào từng phần để nhảy tới:
Phân tíchNói ngắn gọn lại đề bài
Thì trước tiên nói ngắn gọn lại đề bài: hãy tìm đoạn $L \to R$ ngắn nhất sao cho nếu loại bỏ các phần tử trong đoạn $L \to R$ xong thì phần còn lại các phần tử đều phân biệt nhau hết.
Thay vì nói về việc đi loại bỏ thì ta hiểu là các thằng còn lại sẽ là những thằng phân biệt. Nếu tính vị trí index từ 1 đến $N$ thì các thằng còn lại sẽ là: $a[1] \to a[L-1]$ và $a[R+1] \to a[N]$, tất cả đều phân biệt, không có thằng nào bị trùng nhau. Em ok chứ? À mà cũng nói rõ đoạn $L \to R$ ta chọn thì đương nhiên $L \le R$ nha, từ Left đến Right mà.
Ví dụ 3 1 4 1 5 9 2 6: bỏ đoạn $[4, 4]$ (ô đỏ) thì phần giữ lại 3 1 4 (xanh lá) và 5 9 2 6 (tím) phân biệt hết → đáp án 1.
- Trường hợp đặc biệt: nếu ngay từ đầu cả dãy đã phân biệt thì Phát khỏi bỏ gì cả (đề nói "nhiều nhất một đoạn"), đáp án là 0.
- Khi đề bài nói $1 \le a_i \le n$ mà $n \le 10^6$ là số nhỏ, giá trị các phần tử tối đa chỉ là $10^6$, thì trước mắt thấy có mùi mảng đánh dấu ở đây :)) Mảng
check[v] = truenghĩa là màu $v$ đã xuất hiện trong phần được giữ lại.
Cách 1Thử mọi L, lùi R từ cuối: Subtask 1, 2
Cách dễ nghĩ nhất: thử lần lượt từng vị trí bắt đầu $L = 1, 2, \ldots$ Với mỗi $L$:
- Đánh dấu các màu của phần bên trái $a[1] \to a[L-1]$. Nếu phần bên trái đã có 2 thằng trùng nhau thì $L$ này và mọi $L$ lớn hơn đều hỏng → dừng hẳn.
- Cho $R$ chạy từ $N$ lùi về: chừng nào $a[R]$ chưa bị đánh dấu thì giữ lại nó (đánh dấu) và lùi $R$. Gặp $a[R]$ đã đánh dấu thì bắt buộc phải bỏ từ $L$ đến $R$ → độ dài $R - L + 1$.
Cho $L$ chạy tới tận $N + 1$ (bên trái giữ hết) để bắt luôn trường hợp cả dãy đã phân biệt (khi đó $R$ lùi về $L - 1 = N$, độ dài 0). Mỗi $L$ tốn $O(N)$ (tạo lại mảng đánh dấu, quét trái, quét phải) nên tổng $O(N^2)$: $n = 10^3$ chỉ khoảng $10^6$ phép tính, còn $n = 10^5$ là $10^{10}$ → TLE.
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
vector<int> a(n + 1);
for(int i = 1; i <= n; ++i){
cin >> a[i];
}
int Min = n;
for(int L = 1; L <= n + 1; ++L){
vector<bool> mark(n + 1, false);
bool ok = true;
for(int i = 1; i < L; ++i){
if(mark[a[i]] == true){
ok = false;
break;
}
mark[a[i]] = true;
}
if(ok == false){
break;
}
int R = n;
while(R >= L && mark[a[R]] == false){
mark[a[R]] = true;
R--;
}
Min = min(Min, R - L + 1);
}
cout << Min;
return 0;
}n = int(input())
a = [0] + list(map(int, input().split()))
Min = n
for L in range(1, n + 2):
mark = [False] * (n + 1)
ok = True
for i in range(1, L):
if mark[a[i]]:
ok = False
break
mark[a[i]] = True
if not ok:
break
R = n
while R >= L and not mark[a[R]]:
mark[a[R]] = True
R -= 1
Min = min(Min, R - L + 1)
print(Min)Ý tưởngLMax, RMin và hai con trỏ cùng lùi
Thì giờ nhé, có phải nếu cho rằng $L$ là 1 giá trị xuất phát từ vị trí 1 trở đi thì tối đa $L$ sẽ chỉ ở ngay tại vị trí phần tử đầu tiên tính từ trái qua phải mà tại đó nó bị trùng với phần tử nào trước đó.
Ví dụ mảng có 10 phần tử là 1 2 3 1 2 5 6 3 4 8 thì $L$ tối đa sẽ chỉ ở vị trí 4, vì tại $a[4]$ là số 1 bị trùng với trước đó là $a[1]$ cũng là số 1. $L$ có thể là 1, 2, 3, 4; tối đa là 4 thôi. $L$ không thể bắt đầu từ vị trí 5 trở lên được, bởi vì nếu chọn $L = 5$ thì $L - 1 = 4$, mà từ $a[1]$ đến $a[4]$ ta đã thấy có 2 thằng trùng nhau rồi đó (là $a[1]$ và $a[4]$ luôn). Chọn $L = 6, 7, 8, 9, 10$ thì càng không được.
Từ trái qua: $a[1..3] = 1, 2, 3$ chưa trùng; $a[4] = 1$ trùng với $a[1]$ → $L_{Max} = 4$.
Từ phải qua: $a[10..4]$ chưa trùng; $a[3] = 3$ trùng với $a[8]$ → $R_{Min} = 3$. Đáp án của dãy này là 3 (bỏ $a[2..4]$).
Và điều tương tự với $R$: khi chọn từ $N$ lùi về trước ($N, N-1, N-2, \ldots$) thì $R$ nhỏ nhất chỉ là vị trí $i$ đầu tiên tính từ phải qua trái mà tại đó $a[i]$ bị trùng với một trong các thằng $a[N], a[N-1], \ldots, a[i+1]$. Ở ví dụ trên: đi từ phải qua 8, 4, 3, 6, 5, 2, 1 đều mới, tới $a[3] = 3$ thì trùng với $a[8] = 3$ → $R_{Min} = 3$. Đó chỗ này em suy ngẫm hen. Và việc kiểm tra làm sao biết bị trùng thì dùng mảng đánh dấu rất tiện lợi trong tình huống này.
Hai con trỏ chạy đồng thời
Gọi $L_{Max}$ là vị trí tối đa mà $L$ có thể chọn, tương tự $R_{Min}$ là vị trí bé nhất mà $R$ có thể chọn.
- Ngay từ đầu xét $L = L_{Max}$, tức là đã có 1 mảng đánh dấu các phần tử $a[1], a[2], \ldots, a[L_{Max}-1]$ xuất hiện. Rồi ta tìm vị trí $R$ tương ứng bằng cách xét từ cuối dãy trở về trước: cứ mỗi phần tử $a[R]$ mà chưa có trong mảng đánh dấu thì đánh dấu nó và lùi $R$; nếu phát hiện $a[R]$ đã xuất hiện thì dừng tại đó, đó chính là vị trí $R$ bé nhất tương ứng với $L$ đã chọn. Tính độ dài $R - L + 1$ lưu vào biến đáp án Min.
- Sau đó $L$
--để xét các vị trí lùi về trước. Đồng nghĩa ta sẽ không giữ phần tử $a[L]$ mới (trước đó là $a[L_{Max}-1]$) nữa, cập nhật lại nó trong mảng đánh dấu làfalsetức là chưa xuất hiện. - Lúc này vị trí $R$ ở lần trước sẽ có khả năng lùi tiếp: nếu xét lại $a[R]$ trong mảng đánh dấu mà thấy nó đã là
falsethì $R$--, đến khi nào $a[R]$ trong mảng đánh dấu làtruethì mới dừng lại. Rồi lại tính độ dài $R - L + 1$ so sánh với Min và cập nhật nếu cần. - Cứ như thế $L$
--thì kiểm tra nếu được thì $R$ cũng--theo, chạy đồng thời, đến khi $L$ về 0 thì thôi. Sau cùng xuất ra đáp án Min.
Minh hoạHai con trỏ L, R trên hộp màu
Em nhập dãy màu (tối đa 16 cây, giá trị từ 1 đến n) rồi bấm Tiếp để xem cách tìm $L_{Max}$, $R_{Min}$ và hai con trỏ cùng lùi. Ô xanh lá là phần giữ bên trái, ô tím là phần giữ bên phải, ô đỏ là đoạn bị bỏ:
Cách 2Mảng đánh dấu + hai con trỏ – O(N)
Source code giải quyết theo tư tưởng anh đã trình bày ở trên và cũng đã nộp thành công trên web, em xem để được hiểu rõ hơn. Anh nói trước là code này anh code vội ra theo đúng tư tưởng đã chia sẻ đó với em chứ chưa có clean đâu nha. Anh sợ clean lại mất công em đọc không hiểu. Em xem hiểu rồi clean lại sau nhé:
check3: kiểm tra cả dãy đã phân biệt chưa (flag) → nếu rồi in 0.check: tìm $L_{Max}$, sau đó dùng tiếp làm mảng đánh dấu cho hai con trỏ.check2: tìm $R_{Min}$.
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
vector<int> a(n + 1);
vector<bool> check3(n + 1, false);
bool flag = true;
for(int i = 1; i <= n; ++i){
cin >> a[i];
if(check3[a[i]] == false){
check3[a[i]] = true;
}
else{
flag = false;
}
}
if(flag == true){
cout << 0;
return 0;
}
vector<bool> check(n + 1, false);
int LMax = n;
for(int i = 1; i <= n; ++i){
if(check[a[i]] == true){
LMax = i;
break;
}
check[a[i]] = true;
}
vector<bool> check2(n + 1, false);
int RMin = n;
for(int i = n; i >= 1; --i){
if(check2[a[i]] == true){
RMin = i;
break;
}
check2[a[i]] = true;
}
int L = LMax;
int R = n;
int Min = n;
while(L >= 1 && R >= RMin){
while(check[a[R]] == false){
check[a[R]] = true;
R--;
}
Min = min(Min, R - L + 1);
L--;
check[a[L]] = false;
}
cout << Min;
return 0;
}n = int(input())
a = [0] + list(map(int, input().split()))
check3 = [False] * (n + 1)
flag = True
for i in range(1, n + 1):
if not check3[a[i]]:
check3[a[i]] = True
else:
flag = False
if flag:
print(0)
else:
check = [False] * (n + 1)
LMax = n
for i in range(1, n + 1):
if check[a[i]]:
LMax = i
break
check[a[i]] = True
check2 = [False] * (n + 1)
RMin = n
for i in range(n, 0, -1):
if check2[a[i]]:
RMin = i
break
check2[a[i]] = True
L = LMax
R = n
Min = n
while L >= 1 and R >= RMin:
while not check[a[R]]:
check[a[R]] = True
R -= 1
Min = min(Min, R - L + 1)
L -= 1
if L >= 1:
check[a[L]] = False
print(Min)Một chi tiết nhỏ: ở vòng lặp cuối cùng khi $L$ giảm về 0, dòng check[a[L]] = false; sẽ truy cập a[0]. Vì a có $n + 1$ phần tử và a[0] = 0 nên chỉ là gán check[0] = false, vô hại (bản Python thì mình thêm if L >= 1 cho rõ rà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