Mái Che (COVER)
Đề bài
COVER – Mái che
BGH nhà trường đang có kế hoạch làm mái che sân trường để có điều kiện thời tiết thuận lợi tổ chức các chương trình ngoài sân trường. Sân trường là một hình chữ nhật kích thước $m \times n$ được chia thành lưới ô vuông $m$ hàng, $n$ cột. Một số ô trên sân trường có đang trồng cây (mỗi ô nếu có cây thì chỉ có một cây). BGH muốn làm một mái che là một hình chữ nhật con nằm trong sân trường có các cạnh song song với các cạnh sân trường và có diện tích bằng đúng $k$ ô vuông. Mong muốn của BGH là số lượng cây nằm dưới mái che là ít nhất có thể. Em hãy giúp BGH tính số lượng ít nhất các cây nằm dưới mái che.
Dữ liệu vào:
- Dòng đầu chứa ba số nguyên dương $m, n, k$ được ghi cách nhau bởi dấu cách;
- $m$ dòng sau, mỗi dòng chứa một xâu ký tự độ dài $n$ chỉ gồm các ký tự
0,1mô tả một hàng của sân trường (ký tự0tương ứng với không có cây, ký tự1tương ứng với có cây).
Dữ liệu ra: Một số nguyên duy nhất là số lượng ít nhất các cây nằm dưới mái che. Nếu không thể làm được mái che với diện tích đúng bằng $k$ thì ghi ra $-1$.
Giới hạn: Trong tất cả các test: $1 \le m, n \le 500$; $k \le m \times n$. Trong đó:
- Subtask #1: 40% số điểm có $m, n \le 20$;
- Subtask #2: 30% số điểm có $m, n \le 50$;
- Subtask #3: 30% số điểm còn lại không có ràng buộc gì thêm.
Giới hạn thời gian: 1 giây.
3 4 6
0110
1000
10011Gợi ý của đề: Làm mái che là hình chữ nhật $2 \times 3$ có ô trên trái là $(2, 2)$, dưới phải là $(3, 4)$, có diện tích bằng $6$ và chỉ chứa duy nhất một cây ở ô $(3, 4)$ (như hình dưới).
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 😇.
Trước khi đi vào vấn đề chính của bài thì mình muốn các bạn phải đảm bảo biết qua điều này để về sau các bạn xem mới hiểu: với các hệ thống chấm bài giới hạn thời gian 1 giây thì các bạn rất dễ bị lỗi TLE (Time Limit Exceeded – chạy quá thời gian cho phép). Như mình đã nói rất nhiều lần, muốn không bị TLE thì tối đa số phép toán trên toàn bài chỉ nên ở ngưỡng $(3 \div 5) \cdot 10^7$ là an toàn với phần lớn hệ thống chấm, hệ thống mạnh hơn thì có thể nâng lên $10^8$ nhưng cũng hên xui nhé. Ta không cần đếm chi tiết từng phép toán mà cứ canh theo số lần vòng lặp chạy. Ngưỡng này là với C/C++, còn Python, Java, C#... chạy chậm hơn thì ngưỡng phải thấp hơn. Đề cho 2 giây thì nhân 2 ngưỡng lên, 100 ms thì chia 10, cứ thế thôi.
Mình giải thích ví dụ mẫu để bạn nào chưa hiểu đề sẽ hiểu rõ. Sân $3 \times 4$, cần mái che diện tích $k = 6$. Hai số nhân nhau ra $6$ chỉ có các trường hợp $1 \times 6$, $2 \times 3$, $3 \times 2$, $6 \times 1$ – tức là một số là ước của $k$, số còn lại là $k$ chia cho ước đó. Ở đây mình quy ước chiều dài = số cột, chiều rộng = số dòng của mái che:
- $1 \times 6$ (6 dòng, 1 cột): 6 dòng vượt quá 3 dòng của sân ⇒ loại.
- $6 \times 1$ (1 dòng, 6 cột): 6 cột vượt quá 4 cột của sân ⇒ loại.
- $2 \times 3$ (2 dòng, 3 cột) và $3 \times 2$ (3 dòng, 2 cột): nằm gọn trong sân ⇒ lấy được.
Mình đánh số ô kiểu "11 là dòng 1 cột 1, 12 là dòng 1 cột 2..." cho dễ hình dung:
Các mái che 2 dòng × 3 cột có 4 vị trí, các mái che 3 dòng × 2 cột có 3 vị trí:
Tổng cộng 7 hình chữ nhật con. Đếm số cây (số 1) trong từng hình rồi lấy nhỏ nhất: hình thứ 4 (từ ô 22 đến ô 34) chỉ có 1 cây, nên đáp án là $1$. Còn nếu không có hình chữ nhật con nào hợp lệ thì in $-1$.
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:
Cách 1Vét cạn tất cả hình chữ nhật con diện tích k – O(d · m · n · k)
Mình luôn khuyên các bạn: với mọi bài, nếu chưa nghĩ ra cách tối ưu (hoặc nghĩ ra rồi mà chưa chắc đúng) thì hãy giải bằng vét cạn trước. Vét cạn thường rất dễ làm và luôn cho kết quả đúng, chỉ bị chạy lâu thôi. Nhờ vậy ta dùng nó để kiểm tra tính chính xác cho cách tối ưu làm sau; nhìn vào chỗ dở của nó ta cũng có tiền đề để tối ưu; còn nếu sau cùng vẫn không nghĩ ra cách tốt hơn thì nó giúp ta vét được bao nhiêu điểm thì vét (thi chấm kiểu IOI đúng test nào có điểm test đó).
Vét cạn ở bài này là: xét TẤT CẢ các hình chữ nhật con có diện tích bằng $k$, với mỗi hình đi vào bên trong đếm có bao nhiêu số 1, cập nhật vào biến Min. Sau cùng Min chính là đáp án.
Cách làm này lại gây khó cho những bạn chưa vững xử lý mảng 2 chiều, cụ thể là liệt kê ra từng hình chữ nhật con. Các bạn nhìn bản chất của tụi nó thế này: hình chữ nhật con đầu tiên kích thước height dòng × width cột sẽ có góc trên trái trùng góc trên trái của sân (ô 11). Ta dùng 4 biến:
start_row = 1, finish_row = height, start_col = 1, finish_col = width.Hình chữ nhật con "trượt" giống thứ tự duyệt mảng 2 chiều: từ trái qua phải (
start_col++, finish_col++), khi đã chạm biên phải (finish_col == colum) thì quay về cột 1 và lùi xuống 1 dòng (start_col = 1, finish_col = width, start_row++, finish_row++). Lặp lại trong khi finish_col <= colum và finish_row <= row.Ví dụ với hình 2 × 3 trong sân 3 × 4: đầu tiên là (cột 1→3, dòng 1→2); tăng cột thành (cột 2→4, dòng 1→2), lúc này finish_col = 4 đã chạm biên phải; nên quay về cột 1→3 và xuống dòng 2→3; rồi qua phải thành cột 2→4, dòng 2→3. Tiếp tục thì finish_row = 4 > 3 ⇒ vượt biên, xét xong hết các hình 2 × 3.
Để liệt kê kích thước, thay vì đi tìm mọi ước của $k$, mình cho width chạy từ 1 đến colum (như thế width luôn nằm trong số cột của sân), nếu k % width == 0 thì height = k / width, chỉ cần kiểm tra thêm height <= row. Mỗi khi tìm được một kích thước hợp lệ thì bật cờ hiệu check = true, để cuối cùng nếu check vẫn là false (không có hình nào hợp lệ) thì in $-1$.
- 3 dòng
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);giúp nhập xuất của C++ nhanh lên rất nhiều. Bài này sân có thể tới $500 \times 500 = 250\,000$ ô phải đọc nên các bạn code C++ nhớ thêm 3 dòng này vào đầu hàmmainnhé. - Mình quen đánh chỉ số từ 1 nên khai báo mảng
row + 1dòng,colum + 1cột, bỏ không dùng chỉ số 0 cho đỡ rối. Minkhởi tạo làINT_MAX(giá trị lớn nhất củaint) để phần tử đầu tiên so sánh luôn nhỏ hơn nó.
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 main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int row, colum, k;
cin >> row >> colum >> k;
char a[row + 1][colum + 1];
for(int i = 1; i <= row; ++i){
for(int j = 1; j <= colum; ++j){
cin >> a[i][j];
}
}
int Min = INT_MAX;
bool check = false;
for(int width = 1; width <= colum; ++width){
if(k % width == 0){
int height = k / width;
if(height <= row){
check = true;
int start_row = 1, start_col = 1;
int finish_col = width, finish_row = height;
while(finish_col <= colum && finish_row <= row){
int cnt = 0;
for(int i = start_row; i <= finish_row; ++i){
for(int j = start_col; j <= finish_col; ++j){
if(a[i][j] == '1'){
cnt++;
}
}
}
Min = min(Min, cnt);
if(finish_col == colum){
start_col = 1;
finish_col = width;
start_row++;
finish_row++;
}
else{
start_col++;
finish_col++;
}
}
}
}
}
cout << (check == true ? Min : -1);
return 0;
}import sys
def main():
data = sys.stdin.read().split()
row, colum, k = int(data[0]), int(data[1]), int(data[2])
a = [""] + [" " + data[3 + i] for i in range(row)] # đánh chỉ số từ 1
Min = float("inf")
check = False
for width in range(1, colum + 1):
if k % width == 0:
height = k // width
if height <= row:
check = True
start_row, start_col = 1, 1
finish_col, finish_row = width, height
while finish_col <= colum and finish_row <= row:
cnt = 0
for i in range(start_row, finish_row + 1):
for j in range(start_col, finish_col + 1):
if a[i][j] == '1':
cnt += 1
Min = min(Min, cnt)
if finish_col == colum:
start_col = 1
finish_col = width
start_row += 1
finish_row += 1
else:
start_col += 1
finish_col += 1
print(Min if check else -1)
main()Đánh giá độ phức tạp của cách làm này:
- Không gian: mảng ký tự $m \times n$ ⇒ $O(m \cdot n)$.
- Thời gian: với mỗi kích thước hợp lệ (gọi $d$ là số kích thước, tối đa bằng số ước của $k$) có tới $(m - height + 1)(n - width + 1)$ vị trí, mỗi vị trí phải đếm đủ $k$ ô ⇒ cỡ $O(d \cdot m \cdot n \cdot k)$.
Cách 2Cửa sổ trượt + mảng cộng dồn – O(d · m · n)
Muốn tối ưu thì trước tiên phải nhìn ra cách vét cạn đang dở ở đâu đã.
Ý 1: Trượt sang phải thì chỉ bỏ 1 cột, thêm 1 cột
Giả sử sân $100 \times 100$, hình chữ nhật con $50 \times 50$. Hình đầu tiên từ ô $(1, 1)$ đến ô $(50, 50)$, ta đếm hết $2\,500$ ô. Trượt sang phải thành $(1, 2)$ đến $(50, 51)$ thì có cần đếm lại cả $2\,500$ ô không? Bản chất nó chỉ là bỏ đi cột 1 (các ô $(1, 1), (2, 1), \ldots, (50, 1)$) và nhận thêm cột 51 (các ô $(1, 51), \ldots, (50, 51)$). Có sẵn cnt của hình cũ thì lấy cnt trừ số cây trên cột bị bỏ, cộng số cây trên cột mới là xong: chỉ xét $50 + 50 = 100$ ô thay vì $2\,500$ ô.
Tương tự khi chạm biên phải, quay về cột 1 và xuống 1 dòng: hình mới $(2, 1)$ đến $(51, 50)$ so với hình đầu dòng trước $(1, 1)$ đến $(50, 50)$ chỉ là bỏ dòng 1, thêm dòng 51. Chỉ cần lưu lại số cây của hình đầu dòng trước là được.
Ý 2: Mảng cộng dồn để đếm cả một dòng / một cột chỉ bằng 1 phép trừ
Kể cả trượt như trên vẫn còn chỗ dở: mỗi lần trượt vẫn phải đi qua hết các ô của cột (dòng) bị bỏ và cột (dòng) mới. Với sân $100 \times 100$, hình $50 \times 50$: mỗi dòng trượt sang phải 50 lần × 100 ô = $5\,000$ ô, xuống dòng 50 lần nữa ⇒ $250\,000$ ô, cộng thêm $50 \times 100 = 5\,000$ ô khi trượt xuống, tổng $255\,000$ ô phải xét thêm. Rồi với $k = 1000$ thì có tới 6 kích thước hợp lệ ($10 \times 100$, $20 \times 50$, $25 \times 40$, $40 \times 25$, $50 \times 20$, $100 \times 10$), kích thước nào hình đầu tiên cũng phải đếm đủ $1000$ ô.
Ở đây có một kỹ thuật rất hay là Prefix Sum (mảng cộng dồn). Gọi a[i][j] = số cây trên dòng $i$ từ cột 1 đến cột $j$ (cột 0 khởi tạo bằng 0). Ví dụ với sân $10 \times 10$ dưới đây (trái), mảng cộng dồn theo dòng a sẽ là (phải):
Hình chữ nhật con $8 \times 8$ đầu tiên (từ $(1, 1)$ đến $(8, 8)$) có bao nhiêu cây? Không cần đếm $64$ ô, chỉ cần $8$ phép cộng: $a[1][8] + a[2][8] + \ldots + a[8][8] = 4 + 2 + 6 + 5 + 4 + 4 + 4 + 4 = 33$.
Không chỉ từ cột 1, ta tính được trên một đoạn bất kỳ. Ví dụ dòng 1, từ cột 3 đến cột 9 có bao nhiêu cây? Là $a[1][9] - a[1][2] = 4 - 1 = 3$. Vì sao trừ $a[1][2]$ mà không phải $a[1][3]$? Kẻ trục số ra: đoạn $[1, 9]$ trừ đi đoạn $[1, 2]$ thì còn lại đúng đoạn $[3, 9]$; còn nếu trừ $[1, 3]$ thì chỉ còn $[4, 9]$, mất cột 3.
Làm tương tự một mảng
b cộng dồn theo cột từ trên xuống: b[i][j] = số cây trên cột $j$ từ dòng 1 đến dòng $i$. Khi đó số cây trên cột $j$, từ dòng $u$ đến dòng $v$ $= b[v][j] - b[u - 1][j]$.Kết hợp 2 ý lại:
- Hình đầu tiên của mỗi kích thước: cộng
a[i][finish_col] - a[i][start_col - 1]cho từng dòng $i$ ⇒ chỉheightphép tính. Lưu tổng vàosum2(tổng của hình đang nằm ở đầu dòng, cột 1). - Xuống dòng (quay về cột 1):
sum = sum2, trừ số cây của dòngstart_row - 1(dòng vừa bị bỏ), cộng số cây của dòngfinish_row(dòng mới), mỗi cái chỉ 1 phép trừ trên mảnga. Nhớ cập nhật lạisum2cho lần xuống dòng sau. - Trượt sang phải: trừ số cây cột
start_col - 1(cột vừa bỏ), cộng số cây cộtfinish_col(cột mới), mỗi cái 1 phép trừ trên mảngb.
Mảng a mình tính luôn trong lúc đọc dữ liệu: đọc ký tự c là '0' hay '1', trừ 48 (mã ASCII của '0') để ra số 0 hay 1 rồi cộng với a[i][j - 1]. Mảng b thì cần giá trị gốc tại ô $(i, j)$, mà gốc chính là a[i][j] - a[i][j - 1] (số cây từ cột $j$ đến cột $j$, tức là chính nó). Các bạn ngẫm 1 chút là hiểu chỗ này thôi ^^
a[i][0] = 0, b[0][j] = 0). Ví dụ khi start_row = 1 thì b[start_row - 1][...] là b[0][...], nếu không khởi tạo nó sẽ mang giá trị rác và phép trừ bị sai ngay.Minh hoạ cửa sổ trượt
Em nhập sân và $k$ rồi bấm Tiếp để xem mái che trượt qua từng vị trí, mỗi bước bỏ đi phần nào (đỏ), thêm phần nào (xanh lá):
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 main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int row, colum, k;
cin >> row >> colum >> k;
int a[row + 1][colum + 1], b[row + 1][colum + 1];
for(int i = 1; i <= row; ++i){
a[i][0] = 0;
for(int j = 1; j <= colum; ++j){
char c;
cin >> c;
a[i][j] = a[i][j - 1] + c - 48;
}
}
for(int j = 1; j <= colum; ++j){
b[0][j] = 0;
for(int i = 1; i <= row; ++i){
b[i][j] = b[i - 1][j] + (a[i][j] - a[i][j - 1]);
}
}
int Min = INT_MAX;
bool check = false;
for(int width = 1; width <= colum; ++width){
if(k % width == 0){
int height = k / width;
if(height <= row){
check = true;
int start_row = 1, start_col = 1;
int finish_col = width;
int finish_row = height;
int sum = 0, sum2 = 0;
while(finish_col <= colum && finish_row <= row){
if(start_col == 1){
if(sum2 == 0){
sum = 0;
for(int i = start_row; i <= finish_row; ++i){
sum += a[i][finish_col] - a[i][start_col - 1];
}
Min = min(Min, sum);
sum2 = sum;
}
else{
sum = sum2;
sum -= (a[start_row - 1][finish_col] - a[start_row - 1][start_col - 1]);
sum += (a[finish_row][finish_col] - a[finish_row][start_col - 1]);
sum2 = sum;
Min = min(Min, sum);
}
}
else{
sum -= (b[finish_row][start_col - 1] - b[start_row - 1][start_col - 1]);
sum += (b[finish_row][finish_col] - b[start_row - 1][finish_col]);
Min = min(Min, sum);
}
if(finish_col == colum){
start_col = 1;
finish_col = width;
start_row++;
finish_row++;
}
else{
start_col++;
finish_col++;
}
}
}
}
}
cout << (check == true ? Min : -1);
return 0;
}import sys
def main():
data = sys.stdin.read().split()
row, colum, k = int(data[0]), int(data[1]), int(data[2])
# a[i][j]: số cây trên dòng i từ cột 1 đến cột j (cộng dồn theo dòng)
a = [[0] * (colum + 1) for _ in range(row + 1)]
for i in range(1, row + 1):
s = data[2 + i]
for j in range(1, colum + 1):
a[i][j] = a[i][j - 1] + ord(s[j - 1]) - 48
# b[i][j]: số cây trên cột j từ dòng 1 đến dòng i (cộng dồn theo cột)
b = [[0] * (colum + 1) for _ in range(row + 1)]
for j in range(1, colum + 1):
for i in range(1, row + 1):
b[i][j] = b[i - 1][j] + (a[i][j] - a[i][j - 1])
Min = float("inf")
check = False
for width in range(1, colum + 1):
if k % width == 0:
height = k // width
if height <= row:
check = True
start_row, start_col = 1, 1
finish_col, finish_row = width, height
sum1, sum2 = 0, 0
while finish_col <= colum and finish_row <= row:
if start_col == 1:
if sum2 == 0:
sum1 = 0
for i in range(start_row, finish_row + 1):
sum1 += a[i][finish_col] - a[i][start_col - 1]
Min = min(Min, sum1)
sum2 = sum1
else:
sum1 = sum2
sum1 -= a[start_row - 1][finish_col] - a[start_row - 1][start_col - 1]
sum1 += a[finish_row][finish_col] - a[finish_row][start_col - 1]
sum2 = sum1
Min = min(Min, sum1)
else:
sum1 -= b[finish_row][start_col - 1] - b[start_row - 1][start_col - 1]
sum1 += b[finish_row][finish_col] - b[start_row - 1][finish_col]
Min = min(Min, sum1)
if finish_col == colum:
start_col = 1
finish_col = width
start_row += 1
finish_row += 1
else:
start_col += 1
finish_col += 1
print(Min if check else -1)
main()sum = 0;sum2 == 0 được dùng để nhận biết "đây là hình đầu tiên, phải đếm toàn bộ". Nhưng nếu hình đầu dòng nào đó có đúng 0 cây thì sum2 cũng bằng 0, sang dòng sau code sẽ đếm lại toàn bộ mà sum lúc đó vẫn còn giá trị cũ của hình cuối dòng trước, nên các tổng phía sau bị cộng dư. Đáp án vẫn đúng vì lúc đó Min đã bằng 0 rồi (không thể nhỏ hơn được nữa), nhưng mình thêm dòng sum = 0; trước khi đếm lại để mọi giá trị sum luôn chính xác, các bạn có sửa bài thành tìm Max hay đếm gì khác cũng không bị dính lỗi.Bấm Tiếp để chạy tay từng dòng code C++ ở trên (em sửa dữ liệu thoải mái, sân nhỏ thôi nhé):
Đánh giá độ phức tạp của cách làm này:
- Không gian: 2 mảng cộng dồn $a$, $b$ kích thước $(m + 1) \times (n + 1)$ ⇒ $O(m \cdot n)$.
- Thời gian: tạo 2 mảng cộng dồn mất $O(m \cdot n)$. Với mỗi kích thước hợp lệ, mỗi vị trí của mái che chỉ tốn $O(1)$ (trừ hình đầu tiên tốn $O(height)$) ⇒ $O(m \cdot n)$ cho mỗi kích thước. Tổng cộng $O(d \cdot m \cdot n)$ với $d$ là số kích thước hợp lệ. Mình tính thử với $m = n = 500$, trường hợp xấu nhất ($k = 2520$) tổng số vị trí cũng chỉ khoảng $6 \cdot 10^6$, quá thoải mái.
Với code này thời điểm mình nộp đã AC full 20/20 test, test chạy lâu nhất chỉ 56 ms, trong khi code vét cạn chạy tới 2000 ms: nhanh hơn cả 40 lần, mà code chỉ dài thêm có 30 dòng và tốn thêm bộ nhớ cho mảng b. Các bạn đã thấy cái hay của giải thuật chưa hehe 😎.
Tóm lại để tối ưu thì dùng 2 kỹ thuật là Sliding Window (cửa sổ trượt) và Prefix Sum (mảng cộng dồn) là ta giải quyết ngon lành cho bài này. Nếu bạn nào không hiểu chỗ nào và đã cố gắng đọc kỹ, suy nghĩ mà vẫn chưa hiểu thì cứ comment hỏi, mình sẽ tranh thủ khi rảnh trả lời cho các bạn.
- 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