Sửa Đèn
Đề bài
Sinh ra và lớn lên tại Từ Sơn, tỉnh Bắc Ninh, Ngô Bá Khá – với biệt danh Khá Bảnh, chắc hẳn không còn ai xa lạ vì anh đã bị bế đi, nhưng theo các trang mạng và báo chí gần đây cho thấy, anh Bảnh có quan hệ huyết thống với Elon Musk – người đàn ông giàu nhất thế giới, nếu 1 người bình thường làm 1 ngày 1 tỷ và làm trong 100 năm thì mới $\sim 0{,}0053\%$ tài sản của ông, vì cải tạo tốt và với mong muốn gặp con trai mình, ông Elon đã thuê người bảo hộ anh Bảnh, sau một thời gian trôi qua và ôn thi đại học, anh đã trở thành một tân sinh viên PTIT ngành CNTT và có crush 1 cô bạn ngành kế toán, một ngày nọ, anh Bảnh mời được cô bé về nhà mình chơi, nhưng khổ nỗi vì căn nhà anh mới mua bằng tiền ăn sáng đã lâu chưa ai ở nên đồ vật đã trở nên cũ kĩ, $N$ chiếc đèn ngoài sân nhà anh đã chập chờn và đã có $B$ chiếc bị hỏng, khiến sân nhà anh tối mịt, để không làm crush đợi, anh đã vận dụng kiến thức để cố sửa tạm thời sao cho có ít nhất một khu vực có $K$ chiếc đèn liên tiếp hoạt động, nhưng trong tù lâu nên anh chưa có tư duy logic để giải, các bạn hãy giúp anh Bảnh nhé.
Input:
- Dòng đầu tiên gồm 3 số nguyên dương $N$, $K$ và $B$ $(1 \le B, K \le N \le 100\,000)$.
- $B$ dòng tiếp theo, mỗi dòng chứa vị trí của một chiếc đèn bị hỏng.
Output: in ra số đèn cần sửa ít nhất sao cho có một khu vực có nhiều hơn hoặc bằng $K$ chiếc đèn hoạt động.
Subtask:
- Subtask 1: 30% số test đầu tiên có $N \le 100$.
- Subtask 2: 30% số test tiếp theo có $N \le 10\,000$.
- Subtask 3: 40% số test còn lại không có giới hạn gì thêm.
10 6 5
2
10
1
5
91Giải thích: có 10 đèn, các đèn hỏng ở vị trí 2, 10, 1, 5, 9. Chọn đoạn 6 đèn liên tiếp từ đèn 3 đến đèn 8 thì trong đó chỉ có đúng 1 đèn hỏng (đèn 5), sửa nó là xong, nên đáp án là 1.
Lời mở đầu
Bài này mình được một bạn học viên hỏi nên sẵn tiện mình viết bài giải chi tiết để nhiều bạn được tham khảo luôn. Hy vọng mang đến được giá trị cho các bạn 😇. Mình sẽ đi từ cách làm đơn giản nhất rồi tối ưu dần dần, để các bạn thấy được cái hay của việc liên tục nhìn ra cái dở của cách làm hiện tại và khắc phục nó.
Link này chỉ học viên đã tham gia tổ chức mới vào được. Học viên nên ưu tiên nộp ở đây vì sẽ được chấm nhanh hơn.
Nộp bài trên CLUE OJBạ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é. Chưa có tài khoản thì tạo tài khoản rồi đăng nhập nộp bài thử hen.
Nộp bài trên CodeforcesLộ trình lời giải, bấm vào từng phần để nhảy tới:
Ý tưởngXét mọi đoạn con K đèn liên tiếp
Nhìn vào bài này ta thấy ngay cách làm đơn giản nhất đó là xếp các đèn theo đúng thứ tự từ 1 đến $N$, rồi cứ thế ta xét tất cả các đoạn con có đủ $K$ phần tử liên tiếp nhau, và trong từng đoạn ta tính xem cần phải sửa bao nhiêu chiếc đèn bị hỏng. Ở mỗi đoạn con sau khi tính ra cần phải sửa bao nhiêu chiếc đèn bị hỏng thì ta lưu nó vào biến Min và liên tục cập nhật lại Min khi xét qua từng đoạn con. Sau cùng khi đã xét hết tất cả các đoạn con có $K$ phần tử liên tiếp thì ta có biến Min lưu giá trị số đèn ít nhất cần sửa để tồn tại ít nhất $K$ bóng đèn sáng liên tiếp nhau, và đó chính là đáp án của bài toán.
Ví dụ cụ thể giả sử ta có $N = 10$ chiếc đèn, và $K = 5$. Như thế ta cần xét các đoạn con có $K = 5$ phần tử liên tiếp là: 1 đến 5, 2 đến 6, 3 đến 7, 4 đến 8, 5 đến 9, 6 đến 10. Đến đây là hết rồi, nếu xét nữa thì sẽ thành 7 đến 11 mà ta chỉ đang có tổng cộng 10 chiếc đèn thôi nên không tính trường hợp này. Vậy tổng cộng có 6 đoạn con cần xét.
Các bạn cứ thử thế số $N$ và $K$ ở trường hợp ví dụ trên mình vừa đưa ra hoặc tự các bạn đưa ra thêm 1 số trường hợp khác để kiểm chứng tính đúng đắn của công thức này nhé.
Rồi thì với từng đoạn con ta duyệt vòng lặp xét qua từng phần tử trong đoạn con đó, với từng bóng đèn xét đến ta kiểm tra xem bóng nào bị hỏng thì tăng biến đếm lên, sau cùng khi xét hết đoạn con là ta có tổng số lượng bóng đèn bị hỏng trong đoạn con đó. So sánh kết quả đếm đó với biến Min, nếu đếm nhỏ hơn Min thì cập nhật lại Min = đếm.
Chạy tay ví dụ của đề
Ta có $N = 10$, $K = 6$, $B = 5$, tức là có 5 bóng đèn bị hư là các bóng ở các vị trí $\{2, 10, 1, 5, 9\}$. Với $K = 6$, $N = 10$ thì ta có $10 - 6 + 1 = 5$ đoạn con cần xét:
| Đoạn con | Đèn hỏng trong đoạn | Đếm | So với Min | Min |
|---|---|---|---|---|
| 1 đến 6 | 1, 2, 5 | 3 | đoạn đầu tiên nên Min = 3 | 3 |
| 2 đến 7 | 2, 5 | 2 | 2 < Min (đang là 3) → cập nhật Min = 2 | 2 |
| 3 đến 8 | 5 | 1 | 1 < Min (đang là 2) → cập nhật Min = 1 | 1 |
| 4 đến 9 | 5, 9 | 2 | 2 không nhỏ hơn Min = 1 → giữ nguyên | 1 |
| 5 đến 10 | 5, 9, 10 | 3 | 3 không nhỏ hơn Min = 1 → giữ nguyên | 1 |
Vậy đến đây đã hết các đoạn con cần xét, sau cùng ta có Min = 1 và đây là đáp án của bài toán. Các bạn nhập thử dữ liệu khác rồi bấm Tiếp để xem từng đoạn con được xét:
Vậy với quy trình xử lý ở trên, ta có thể phác hoạ cơ bản ra code (mã giả) sẽ thế này:
int Min = 100001;
for(int i = 1; i <= N - K + 1; ++i){
int cnt = 0;
for(int j = i; j <= K + i - 1; ++j){
/* Lúc này đây với mỗi giá trị j ta sẽ kiểm tra xem nếu nó có nằm trong
danh sách các bóng đèn bị hư mà đề bài đã cho thì tăng biến đếm lên */
if(j là bóng đèn bị hư){
cnt++;
}
}
Min = min(Min, cnt);
}
cout << Min; // in ra đáp án bài toán.Giải thích 1 số chỗ trong code ở trên:
- Ở code trên ta khởi tạo luôn ngay từ đầu
Min = 100001để nó là giá trị lớn nhất, đảm bảo mọi giá trị lần đầu tiên so sánh với nó sẽ luôn thoả nhỏ hơn nó mà cập nhật lạiMin= nó. Thay vì phải gánMin= giá trị đếm đầu tiên rồi thì phải tiếp tục làm riêng 1 vòng lặp xét tiếp thì dài dòng. Lý doMin = 100001($10^5 + 1$) là bởi vì đề cho phạm vi $N$, $B$, $K$ tối đa là $10^5$, thì cao lắm tất cả bóng đèn đều hỏng hết cũng chỉ là $10^5$ bóng, nên ta choMin$= 10^5 + 1$ để đảm bảo nó luôn lớn hơn tất cả. Min = min(Min, cnt);là viết gọn củaif(cnt < Min) { Min = cnt; }. Hàmmin(a, b)được hỗ trợ sẵn trong C++ sẽ trả về giá trị nhỏ nhất trong 2 giá trịa,b.
Cách 1Vét cạn – tìm tuần tự – O((N − K + 1)·K·B)
Câu lệnh if(j là bóng đèn bị hư) là mình viết mã giả như vậy, còn để cài đặt kiểm tra được xem bóng đèn $j$ có nằm trong danh sách các bóng đèn bị hư mà input đã cho hay không, thì bạn nào không biết thì có thể sẽ phải đi tìm tuần tự trong danh sách các bóng đèn bị hư, thì rất phức tạp: độ phức tạp cho mỗi thao tác tìm kiếm bóng đèn $j$ lúc này là $O(B)$ với $B$ là số lượng bóng đèn bị hư.
Vậy nếu làm như thế thì độ phức tạp tổng quát của bài này là:
- Vòng lặp
for icó số lần lặp là $N - K + 1$ theo như đầu bài mình đã phân tích. - Vòng lặp
for jcó số lần lặp là $K$ lần vì đang xét qua đoạn con có $K$ phần tử liên tiếp. - Bước kiểm tra bóng đèn $j$ có bị hư không? Tối đa có thể sẽ phải xét qua đủ $B$ lần lặp nếu trong tình huống bóng đèn $j$ đó không nằm trong danh sách bị hư.
Vì tụi nó đang lồng nhau nên cả thảy độ phức tạp về mặt thời gian nếu làm theo cách này sẽ là $O(N - K + 1) \cdot O(K) \cdot O(B)$.
Với giới hạn theo như đề bài đưa ra là $1 \le B, K \le N \le 10^5$, giả sử trường hợp $N = 10^5$, $B = K = \frac{10^5}{2} = 5 \cdot 10^4$. Vậy độ phức tạp lúc này sẽ là $(10^5 - 5 \cdot 10^4 + 1) \cdot 5 \cdot 10^4 \cdot 5 \cdot 10^4$. Coi như bỏ qua cái $+1$ thì $(10^5 - 5 \cdot 10^4)$ là $5 \cdot 10^4$. Vậy 3 lần của $5 \cdot 10^4$ nhân nhau: $(5 \cdot 10^4)^3 = 125 \cdot 10^{12}$ = 125 nghìn tỷ lần lặp. Quá kinh khủng! Thế này thì nó đã vượt quá xa ngưỡng giới hạn tiêu chuẩn của 1 giây là chỉ lặp tối đa $(3 \text{ đến } 5) \cdot 10^7$, tức là 30 triệu đến 50 triệu hay cao lắm là $10^8$ tức là 100 triệu. Ở đây 125 nghìn tỷ là vượt quá cả $125 \cdot 10^4$ lần rồi. Vậy nên cách làm này chắc chắn sẽ bị TLE.
Tuy nhiên hãy cứ cài đặt nó, để tuy nó chạy quá giới hạn thời gian nhưng ta sẽ dùng nó làm công cụ để đi kiểm tra tính chính xác cho cách làm tối ưu hơn sau này. Source code hoàn chỉnh nếu làm theo cách ở trên:
#include <bits/stdc++.h>
using namespace std;
int main(){
int n, k, b;
cin >> n >> k >> b;
int a[b];
for(int i = 0; i < b; ++i){
cin >> a[i];
}
int Min = 100001;
for(int i = 1; i <= n - k + 1; ++i){
int cnt = 0;
for(int j = i; j <= k + i - 1; ++j){
for(int c = 0; c < b; ++c){
if(a[c] == j){
cnt++;
break;
}
}
}
Min = min(Min, cnt);
}
cout << Min;
return 0;
}import sys
data = sys.stdin.read().split()
n, k, b = int(data[0]), int(data[1]), int(data[2])
a = [int(v) for v in data[3:3 + b]]
Min = 100001
for i in range(1, n - k + 2):
cnt = 0
for j in range(i, k + i):
for c in range(b): # tìm tuần tự j trong danh sách đèn hỏng
if a[c] == j:
cnt += 1
break
Min = min(Min, cnt)
print(Min)Cách 2Mảng đánh dấu – O((N − K + 1)·K)
Vậy ta hãy thử tối ưu giảm độ phức tạp xuống để không bị TLE nào. Ta có thể tối ưu bước kiểm tra xem $j$ có phải là bóng đèn bị hư hay không. Thay vì phải xét tuần tự qua từng bóng đèn trong danh sách để kiểm tra, ta có thể nhìn thấy cả thảy chỉ có tối đa $10^5$ bóng đèn, $10^5$ là giá trị hợp lý để ta có thể triển khai kỹ thuật mảng đánh dấu (triển khai được khi giá trị tối đa của phần tử $\le 10^7$).
Vậy từ đầu ta khởi tạo mảng đánh dấu check có $n + 1$ phần tử mang toàn bộ giá trị 0 (false). Sau đó khi đọc từng vị trí các bóng đèn bị hư từ input, giả sử đọc vào biến x thì gọi check[x] = 1 (true). Cứ thế xong quá trình đọc input là ta đã có mảng check lưu trữ tình trạng từng bóng đèn. Lúc này khi cần kiểm tra xem bóng đèn $j$ có bị hư hay không thì chỉ cần gọi check[j], nếu là giá trị 1 (true) tức là bóng đèn $j$ đó bị hư.
check là đủ.Ví dụ đề sau khi đọc xong 5 đèn hỏng $\{2, 10, 1, 5, 9\}$ thì mảng check (index 0 bỏ không dùng) sẽ là:
Source code để các bạn tham khảo nếu làm theo cách này:
#include <bits/stdc++.h>
using namespace std;
int main(){
int n, k, b;
cin >> n >> k >> b;
bool check[n + 1] = {false};
while(b--){
int x;
cin >> x;
check[x] = true;
}
int Min = 100001;
for(int i = 1; i <= n - k + 1; ++i){
int cnt = 0;
for(int j = i; j <= k + i - 1; ++j){
if(check[j] == true){
cnt++;
}
}
Min = min(Min, cnt);
}
cout << Min;
return 0;
}import sys
data = sys.stdin.read().split()
n, k, b = int(data[0]), int(data[1]), int(data[2])
check = [False] * (n + 1) # mảng đánh dấu
for x in data[3:3 + b]:
check[int(x)] = True
Min = 100001
for i in range(1, n - k + 2):
cnt = 0
for j in range(i, k + i):
if check[j]:
cnt += 1
Min = min(Min, cnt)
print(Min)Lưu ý: mảng đánh dấu check có số lượng phần tử là $n + 1$ bởi vị trí các bóng đèn tính từ 1, nên ta cho mảng $n + 1$ phần tử để tương ứng index từ 1 đến $n$, xem như bỏ qua không dùng index 0.
Lúc này độ phức tạp về mặt thời gian chỉ còn $O(N - K + 1) \cdot O(K)$. Tuy nhiên cũng vẫn với trường hợp như trên tức $N = 10^5$, $K = 5 \cdot 10^4$ thì lúc này vẫn sẽ là $5 \cdot 10^4 \cdot 5 \cdot 10^4 = 25 \cdot 10^8$, thì cũng vẫn lớn hơn ngưỡng tiêu chuẩn 1 giây rồi, tuy có tốt hơn cách làm trước đó nhưng vẫn sẽ bị TLE thôi. Phải tiếp tục tối ưu hơn nữa.
Cách 3Cửa sổ trượt (Sliding Window) – O(N)
Thì chúng ta hãy cứ liên tục nhìn ra những cái dở của cách làm hiện tại và suy nghĩ khắc phục được nó là sẽ ra được một cách tối ưu hơn. Như trước đó ta đã thấy cái dở của việc kiểm tra bóng đèn $j$ có bị hư hay không: thay vì đi tìm kiếm tuần tự hết $O(B)$ lần thì ta dùng kỹ thuật mảng đánh dấu chỉ cần $O(1)$ là ra ngay. Thì giờ hãy tiếp tục nhìn xem cách hiện tại còn cái dở nào không? Quan trọng quyết định là nhìn ra được cái dở hiện tại.
Thì ta có thể thấy cái dở hiện tại như sau: với ví dụ đề đưa ra $N = 10$, $K = 6$ thì các đoạn con có 6 phần tử liên tiếp cần xét sẽ là 1 đến 6, 2 đến 7, 3 đến 8, 4 đến 9, 5 đến 10.
- Có phải khi xét đoạn con 2 đến 7 thì bản chất ta đã phải xét trùng lại các giá trị 2, 3, 4, 5, 6 đã xét của đoạn con trước đó (đoạn con 1 đến 6) không? Tính ra đoạn con 2 đến 7 chỉ có giá trị mới là 7 thôi, còn các giá trị khác đều đã được xét qua với đoạn con trước đó.
- Có phải khi xét đoạn con 3 đến 8 thì bản chất ta đã phải xét trùng lại các giá trị 3, 4, 5, 6, 7 đã xét của đoạn con trước đó (đoạn con 2 đến 7) không? Tính ra đoạn con 3 đến 8 chỉ có giá trị mới là 8 thôi.
- Và cứ như thế…
Đến đây các bạn có nhìn thấy cái dở của cách làm trước đó rồi chứ? Nó cứ phải xét trùng rất nhiều giá trị, cứ xét đi xét lại. Trong khi đó, có phải sẽ tốt hơn nếu mỗi giá trị ta không cần cứ phải xét đi xét lại như vậy không?
Vậy một cách làm tốt hơn như sau. Quay lại ví dụ mẫu, đầu tiên xét đoạn con 1 đến 6, đếm xem có bao nhiêu bóng đèn bị hỏng bằng cách duyệt tuần tự từng phần tử rồi lưu giá trị đếm vào biến cnt, rồi cập nhật Min = cnt. Sau đó khi xét qua đoạn con 2 đến 7 thì nghĩa là:
- Ta chỉ xét riêng bóng đèn $2 - 1 = 1$ xem có phải là bóng đèn bị hỏng không? Nếu có thì giảm biến
cnt, vì lúc này đoạn con tính từ 2 đã không bao gồm bóng đèn 1 nữa. - Rồi xét riêng bóng đèn 7 có phải bóng đèn bị hư không? Nếu có thì tăng biến
cntlên 1 đơn vị, vì bây giờ đoạn con mới đã kết nạp thêm bóng đèn 7 vào.
Chỉ 2 lần xét như thế là ta đã có giá trị biến cnt là số lượng các bóng đèn bị hỏng trong đoạn 2 đến 7, ta không cần thiết phải đi xét lại các bóng 2, 3, 4, 5, 6. Sau đó so sánh cập nhật lại biến Min, và cứ quy trình ở trên lặp lại với các đoạn con tiếp theo. Tóm lại lúc này dù đoạn con $K$ phần tử liên tiếp có dài bao nhiêu đi nữa, dù có lên đến $10^5$, thì ta chỉ cần lặp xét đủ $K$ phần tử với đoạn con đầu tiên, còn các đoạn con sau đó dùng lại giá trị cnt của đoạn trước và chỉ xét thêm 2 lần xét nữa thôi.
Các bạn bấm Tiếp để xem cửa sổ trượt dần sang phải, và để ý ô "Số lần xét đèn" so với cách 2 nhé:
Source code để các bạn tham khảo hiểu rõ hơn ý tưởng xử lý mình mô tả ở trên:
#include <bits/stdc++.h>
using namespace std;
int main(){
int n, k, b;
cin >> n >> k >> b;
bool check[n + 1] = {false};
while(b--){
int x;
cin >> x;
check[x] = true;
}
int sz = n - k + 1;
int cnt = 0;
for(int i = 1; i <= k; ++i){
if(check[i] == true){
cnt++;
}
}
int Min = cnt;
for(int i = 2; i <= sz; ++i){
if(check[i - 1] == true){
cnt--;
}
if(check[k + i - 1] == true){
cnt++;
}
Min = min(Min, cnt);
}
cout << Min;
return 0;
}import sys
data = sys.stdin.buffer.read().split()
n, k, b = int(data[0]), int(data[1]), int(data[2])
check = [False] * (n + 1)
for x in data[3:3 + b]:
check[int(x)] = True
sz = n - k + 1
cnt = 0
for i in range(1, k + 1): # đoạn đầu tiên 1..k
if check[i]:
cnt += 1
Min = cnt
for i in range(2, sz + 1): # trượt cửa sổ sang đoạn i..k+i-1
if check[i - 1]:
cnt -= 1
if check[k + i - 1]:
cnt += 1
Min = min(Min, cnt)
print(Min)Đánh giá độ phức tạp
- Không gian: $O(N + 1)$ với $N$ là số lượng bóng đèn (mảng
check). - Thời gian: $O(N + 1)$ của bước khởi tạo mảng
checktoàn bộ mang giá trịfalse+ $O(B)$ của bước đọc dữ liệu từ input + $O(K)$ của bước xét qua đoạn con $K$ phần tử liên tiếp đầu tiên + $O(N - K)$ của bước xét qua các đoạn con tiếp theo. Theo quy tắc cộng Big-O sẽ lấy theo thành phần lớn nhất trong các phép cộng, nên độ phức tạp tổng quát sẽ là $O(\max(N + 1, B, N - K + 1))$, tức là $O(N)$.
Vậy với độ phức tạp tính ở trên, trong trường hợp xấu nhất khi $N = 10^5$, $B = 10^5$, $K = 1$ thì số lần lặp cả thảy sẽ là $10^5 + 10^5 + 10^5 = 3 \cdot 10^5$ (300 ngàn). Với số lần lặp này yên tâm sẽ thoả ngưỡng giới hạn tiêu chuẩn 1 giây là $(3 \text{ đến } 5) \cdot 10^7$, thì 300 ngàn ít hơn rất nhiều so với giới hạn này, vì thế ta không sợ bị TLE nhé.
Cũng nói thêm luôn là giải thuật mình vừa trình bày ở trên còn có tên gọi tiếng Anh là Sliding Window hay tên tiếng Việt là cửa sổ trượt. Bởi các bạn xem việc ta xét đoạn con 1 đến 6, sau đó xét qua đoạn con 2 đến 7, rồi 3 đến 8… có giống một cửa sổ trượt dần dần không? Với cạnh đầu tiên của cửa sổ ban đầu là giá trị 1, cạnh sau của cửa sổ ban đầu là giá trị 6, rồi cửa sổ trượt từ từ để mỗi vị trí 2 cạnh sẽ tăng dần đều nhau. Các bạn có thể theo từ khoá mình vừa nói này để Google search tìm hiểu thêm về kỹ thuật này nhé.
Đến đây các bạn đã thấy cái hay của giải thuật rồi chứ? Ta cứ tối ưu dần dần, từ đó sẽ có cách làm tốt nhất: từ cách làm vét cạn ban đầu, dùng thêm kỹ thuật mảng đánh dấu để được tốt hơn, rồi dùng thêm giải thuật Sliding Window để được tốt hơn nữa.
bool check[n + 1] = {false}; là mảng kích thước thay đổi (VLA), g++ chấp nhận nhưng không phải C++ chuẩn; nếu trình biên dịch của bạn báo lỗi thì đổi thành vector<bool> check(n + 1, false); là chạy y hệt.
Nhận xét
Đăng nhận xét