Hình Chữ Nhật 2
Đề bài
Cho một hình chữ nhật gồm $N$ dòng và $M$ cột. Các dòng được đánh số từ 1 đến $N$, từ trên xuống dưới. Các cột được đánh số từ 1 đến $M$, từ trái sang phải. Ô ở dòng thứ $i$ và cột thứ $j$ được gọi là ô $(i, j)$ và có diện tích là 1 đơn vị. Có một số ô đã được điền sẵn kí tự 'X'.
Yêu cầu: tìm hình chữ nhật con có diện tích lớn nhất chỉ chứa duy nhất một kí tự 'X'.
Dữ liệu vào
- Dòng đầu tiên gồm ba số nguyên dương $N, M, K$ ($N, M \le 10^4$; $K \le 10^3$) mô tả kích thước của hình chữ nhật và số lượng kí tự 'X' có trong hình chữ nhật;
- $K$ dòng sau, mỗi dòng gồm hai số nguyên dương $d$ và $c$ là chỉ số dòng và cột của ô điền kí tự 'X' ($d \le N$; $c \le M$).
Kết quả: ghi ra diện tích của hình chữ nhật lớn nhất thoả mãn yêu cầu đề bài.
Ràng buộc
- Có 50% số test tương ứng với 50% số điểm thoả mãn: $N, M \le 50$;
- 30% số test khác tương ứng với 30% số điểm thoả mãn: $N, M \le 500$;
- 20% số test còn lại tương ứng với 20% số điểm không có ràng buộc gì thêm.
4 5 4
2 3
2 5
3 1
4 49
Vùng tô xám là hình chữ nhật từ ô $(1, 2)$ đến ô $(3, 4)$, gồm $3 \times 3 = 9$ ô và chỉ chứa đúng 1 chữ X ở ô $(2, 3)$.
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 😇.
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:
50%Subtask 1: duyệt mọi hình chữ nhật + mảng cộng dồn 2 chiều
Ta sẽ duyệt qua ô góc dưới cùng bên phải và ô góc trên cùng bên trái của hình chữ nhật con. Nếu hình chữ nhật đó có đúng 1 dấu X thì sẽ cập nhật diện tích của hình chữ nhật lớn nhất. Bài toán chuyển về đếm số lượng dấu X trong mỗi hình chữ nhật cho trước.
Ta có thể duyệt qua hết các ô của hình chữ nhật con được chọn (độ phức tạp thuật toán sẽ là $O(n^3 m^3)$), tuy nhiên ta có thể tối ưu bằng mảng tổng dồn 2 chiều để đếm số dấu X trong 1 hình chữ nhật bất kỳ chỉ trong $O(1)$, khi đó độ phức tạp còn $O(n^2 m^2)$.
a[i][j] là số dấu X trong hình chữ nhật từ ô $(1, 1)$ đến ô $(i, j)$:a[i][j] += a[i-1][j] + a[i][j-1] - a[i-1][j-1]Khi đó số dấu X trong hình chữ nhật từ $(r1, c1)$ đến $(r2, c2)$ là:
a[r2][c2] - a[r2][c1-1] - a[r1-1][c2] + a[r1-1][c1-1]Với $N, M \le 50$ thì $n^2 m^2 / 4 \approx 1.5$ triệu phép tính, chạy rất nhanh.
Xem code subtask 1
#include<bits/stdc++.h>
using namespace std;
int n, m, k;
vector<pair<int, int>> X(1005);
namespace sub1{
int a[1005][1005];
int sum(int r1, int c1, int r2, int c2){
return a[r2][c2] - a[r2][c1-1] - a[r1-1][c2] + a[r1-1][c1-1];
}
int solve(){
for(int i = 0; i < k; i++){
a[X[i].first][X[i].second]++;
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++)
a[i][j] += a[i-1][j] + a[i][j-1] - a[i-1][j-1];
}
int ans = 0;
for(int r2 = 1; r2 <= n; r2++){
for(int c2 = 1; c2 <= m; c2++){
for(int r1 = 1; r1 <= r2; r1++){
for(int c1 = 1; c1 <= c2; c1++) if(sum(r1, c1, r2, c2) == 1){
ans = max(ans, (r2-r1+1) * (c2-c1+1));
}
}
}
}
return ans;
}
};
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m >> k;
for(int i = 0; i < k; i++) cin>>X[i].first>>X[i].second;
cout << sub1::solve() << endl;
}import sys
input = sys.stdin.readline
n, m, k = map(int, input().split())
X = [tuple(map(int, input().split())) for _ in range(k)]
class sub1:
a = [[0] * 1005 for _ in range(1005)]
@staticmethod
def sum(r1, c1, r2, c2):
return (sub1.a[r2][c2]
- sub1.a[r2][c1 - 1]
- sub1.a[r1 - 1][c2]
+ sub1.a[r1 - 1][c1 - 1])
@staticmethod
def solve():
for x, y in X:
sub1.a[x][y] += 1
for i in range(1, n + 1):
for j in range(1, m + 1):
sub1.a[i][j] += sub1.a[i - 1][j] + sub1.a[i][j - 1] - sub1.a[i - 1][j - 1]
ans = 0
for r2 in range(1, n + 1):
for c2 in range(1, m + 1):
for r1 in range(1, r2 + 1):
for c1 in range(1, c2 + 1):
if sub1.sum(r1, c1, r2, c2) == 1:
ans = max(ans, (r2 - r1 + 1) * (c2 - c1 + 1))
return ans
print(sub1.solve())+30%Subtask 2: giảm xuống 3 vòng for – O(n² · m)
Ta định nghĩa một hình chữ nhật trên bảng con bằng góc trái trên và góc phải dưới của nó. Giả sử ta có góc trái trên là $(r, c)$ và góc phải dưới là $(u, v)$. Dựa trên công thức của mảng tổng dồn hai chiều, ta có tổng số dấu X trong đó sẽ là sum[u][v] - sum[u][c - 1] - sum[r - 1][v] + sum[r - 1][c - 1]. Một bảng con thoả mãn điều kiện khi:
Ta sẽ giảm xuống 3 vòng for bằng cách chỉ chạy duyệt $u$, $r$, $v$. Khi này, ta đã biết trước được sum[u][v], sum[r - 1][v] và ta cần tìm vị trí $c$ sao cho:
Nhận xét rằng nếu ta for $u$ và $r$ trước, sau đó lặp tiếp $v$, thì ta có thể lưu lại các giá trị sum[u][c - 1] - sum[r - 1][c - 1] có thể có sau mỗi lần tăng $v$. Khi này ta chỉ cần dùng mảng đánh dấu vị trí $c$ nhỏ nhất có thể đạt được giá trị đó (vì $c$ càng nhỏ thì hình chữ nhật càng rộng) để tối ưu hoá kết quả.
Trong code, mảng luu[giá trị + k] lưu cột $c$ nhỏ nhất ứng với mỗi giá trị (cộng thêm $k$ để chỉ số không bị âm). Với mỗi $c2$, trước tiên ta ghi nhận giá trị của cột $c2 - 1$ (ứng với $c = c2$), rồi tra xem có $c$ nào cho đúng 1 dấu X hay không.
Độ phức tạp: $O(n \cdot n \cdot m)$.
Xem code subtask 2
#include<bits/stdc++.h>
using namespace std;
int n, m, k;
vector<pair<int, int>> X(1005);
namespace sub2{
int a[1005][1005];
int luu[2005];
int sum(int r1, int c1, int r2, int c2){
return a[r2][c2] - a[r2][c1-1] - a[r1-1][c2] + a[r1-1][c1-1];
}
int solve(){
for(int i = 0; i < k; i++){
a[X[i].first][X[i].second]++;
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++)
a[i][j] += a[i-1][j] + a[i][j-1] - a[i-1][j-1];
}
int ans = 0;
for(int r2 = 1; r2 <= n; r2++){
for(int r1 = 1; r1 <= r2; r1++){
for (int j = 0; j <= 2 * k; j ++) luu[j] = -1e9;
for(int c2 = 1; c2 <= m; c2++){
if (luu[a[r2][c2 - 1] - a[r1 - 1][c2 - 1] + k] < 0)
luu[a[r2][c2 - 1] - a[r1 - 1][c2 - 1] + k] = c2;
int pos = luu[a[r2][c2] - a[r1 - 1][c2] - 1 + k];
if (pos > 0) ans = max(ans, (r2-r1+1) * (c2-pos+1));
}
}
}
return ans;
}
};
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m >> k;
for(int i = 0; i < k; i++) cin>>X[i].first>>X[i].second;
cout << sub2::solve() << endl;
}import sys
input = sys.stdin.readline
n, m, k = map(int, input().split())
X = [tuple(map(int, input().split())) for _ in range(k)]
class sub2:
a = [[0] * 1005 for _ in range(1005)]
luu = [0] * 2005
@staticmethod
def sum(r1, c1, r2, c2):
return (sub2.a[r2][c2]
- sub2.a[r2][c1 - 1]
- sub2.a[r1 - 1][c2]
+ sub2.a[r1 - 1][c1 - 1])
@staticmethod
def solve():
for x, y in X:
sub2.a[x][y] += 1
for i in range(1, n + 1):
for j in range(1, m + 1):
sub2.a[i][j] += sub2.a[i - 1][j] + sub2.a[i][j - 1] - sub2.a[i - 1][j - 1]
ans = 0
for r2 in range(1, n + 1):
for r1 in range(1, r2 + 1):
for j in range(0, 2 * k + 1):
sub2.luu[j] = -10**9
for c2 in range(1, m + 1):
idx = sub2.a[r2][c2 - 1] - sub2.a[r1 - 1][c2 - 1] + k
if sub2.luu[idx] < 0:
sub2.luu[idx] = c2
pos = sub2.luu[sub2.a[r2][c2] - sub2.a[r1 - 1][c2] - 1 + k]
if pos > 0:
ans = max(ans, (r2 - r1 + 1) * (c2 - pos + 1))
return ans
print(sub2.solve())100%Subtask 3: chỉ xét các cột trái "đáng quan tâm" + danh sách liên kết – O(m · k)
Việc duyệt qua tất cả các hình chữ nhật con của bảng chắc chắn sẽ không đủ nhanh, vì số hình chữ nhật là vô cùng lớn. Vậy nên chúng ta nghĩ đến hướng tối ưu khác.
Ta sẽ định nghĩa 1 hình chữ nhật con bởi cột trái $c_1$, cột phải $c_2$ ($c_1 \le c_2$) và dòng trên, dòng dưới. Để cho đơn giản, ở đây ta sẽ chỉ nói về lời giải khi không có 2 chữ X cùng dòng. Nếu có 2 chữ X cùng dòng ta có thể giải tương tự (trong code là các điều kiện kiểm tra h[...] != h[...]).
Ta sẽ duyệt qua các giá trị $c_1$ và $c_2$ để cố gắng tìm ra một hình chữ nhật lớn nhất thoả mãn. Gọi $x_1 \lt x_2 \lt \ldots \lt x_s$ là các dòng có chứa chữ X nằm trong dải cột từ $c_1$ đến $c_2$. Khi này hình chữ nhật lớn nhất ta có thể tạo được sẽ có chiều rộng là $c_2 - c_1 + 1$ và chiều cao là:
Nghĩa là: muốn chứa đúng chữ X ở dòng $x_t$ thì hình chữ nhật được kéo dài từ ngay dưới $x_{t-1}$ đến ngay trên $x_{t+1}$ (coi $x_0 = 0$ và $x_{s+1} = n + 1$ là 2 "lính canh" ở 2 đầu). Bài toán chuyển về việc duy trì độ cao này một cách hiệu quả.
Đến đây chúng ta có thể làm như sau: với mỗi giá trị $c_1$, ta sẽ duyệt $c_2$ giảm dần từ $m$. Ta sẽ coi mỗi giá trị $x_1, x_2, \ldots, x_s$ như một đỉnh trong danh sách liên kết (linked list) (mảng before, after trong code), và khi giảm $c_2$, các chữ X ở cột $c_2$ không còn nằm trong dải nữa nên ta xoá dần các đỉnh tương ứng và cập nhật lại kết quả: xoá 1 đỉnh thì chỉ có 2 đỉnh hàng xóm của nó bị thay đổi khoảng cách, nên chỉ cần tính lại chiều cao cho 2 đỉnh đó. Chiều cao lớn nhất chỉ có thể tăng lên khi xoá bớt đỉnh, nên ta chỉ cần lấy max. Việc dựng linked list ban đầu và việc xoá 1 node trong linked list có thể dễ dàng thực hiện được trong độ phức tạp lần lượt là $O(k)$ và $O(1)$. Độ phức tạp là $O(m^2 + km)$, vẫn chưa đủ nhanh để giải quyết bài toán này.
- $c_1 = 1$;
- Trong cột $c_1 - 1$ có ít nhất 1 chữ X.
Ta có thể dễ dàng chứng minh được: giả sử nếu tồn tại 1 hình chữ nhật tối ưu mà $c_1$ không thoả mãn điều kiện trên, tức là cột $c_1 - 1$ hoàn toàn trống, ta có thể giảm $c_1$ đi 1 và sẽ được 1 hình chữ nhật lớn hơn vẫn thoả mãn điều kiện đề bài (vì không thêm chữ X nào). Do chỉ có $k$ chữ X nên chỉ có tối đa $k + 1$ giá trị $c_1$ ta cần phải quan tâm (trong code là dòng if(i > 1 && contain[i-1].size() == 0) continue;). Từ đó ta có thể giảm độ phức tạp của thuật toán xuống $O(mk)$, đủ để giải quyết bài toán.
Em nhập kích thước bảng và các chữ X (mỗi chữ X là cặp "dòng cột") rồi bấm Tiếp để xem với từng dải cột $[c_1, c_2]$, chiều cao lớn nhất được tính từ các dòng có X như thế nào:
#include<bits/stdc++.h>
using namespace std;
int n, m, k;
vector<pair<int, int>> X(1005);
namespace sub3{
int before[1005], after[1005], h[1005];
vector<int> contain[10005];
int solve(){
sort(X.begin(), X.begin() + k);
for(int i = 0; i < k; i++){
contain[X[i].second].push_back(i+1);
h[i+1] = X[i].first;
}
int ans = 0;
h[0] = 0; h[k+1] = n+1;
set<int> st;
for(int i = m; i >= 1; i--){
for(int j : contain[i]) st.insert(j);
if(i > 1 && contain[i-1].size() == 0) continue;
int last = 0, maximum = 0;
for(int j : st){
after[last] = j; before[j] = last;
last = j;
}
before[k+1] = last; after[k+1] = k+1; after[last] = k+1;
for(int j : st) if(h[after[j]] != h[j] && h[before[j]] != h[j]){
maximum = max(maximum, h[after[j]] - h[before[j]] - 1);
}
for(int j = m; j >= i; j--){
if(after[0] != k+1) ans = max(ans, maximum * (j-i+1));
for(int j2 = 0; j2 < contain[j].size(); ){
int u = contain[j][j2], ub = before[u], ua = u;
int nj2 = j2;
int reua = ua;
while(nj2 < contain[j].size() && ua == contain[j][nj2]){
nj2++; ua = after[ua];
}
j2 = nj2;
before[ua] = ub; after[ub] = ua;
if(h[after[ua]] != h[ua] && h[before[ua]] != h[ua]){
maximum = max(maximum, h[after[ua]] - h[before[ua]] - 1);
}
if(h[after[ub]] != h[ub] && h[before[ub]] != h[ub]){
maximum = max(maximum, h[after[ub]] - h[before[ub]] - 1);
}
}
}
}
return ans;
}
};
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m >> k;
for(int i = 0; i < k; i++) cin>>X[i].first>>X[i].second;
cout << sub3::solve() << endl;
}import sys
input = sys.stdin.readline
n, m, k = map(int, input().split())
X = [tuple(map(int, input().split())) for _ in range(k)]
class sub3:
before = [0] * 1005
after = [0] * 1005
h = [0] * 1005
contain = [[] for _ in range(10005)]
@staticmethod
def solve():
X_sorted = sorted(X[:k])
for i, (x, y) in enumerate(X_sorted):
sub3.contain[y].append(i + 1)
sub3.h[i + 1] = x
ans = 0
sub3.h[0] = 0
sub3.h[k + 1] = n + 1
st = set()
for i in range(m, 0, -1):
for j in sub3.contain[i]:
st.add(j)
if i > 1 and len(sub3.contain[i - 1]) == 0:
continue
last = 0
maximum = 0
for j in sorted(st):
sub3.after[last] = j
sub3.before[j] = last
last = j
sub3.before[k + 1] = last
sub3.after[k + 1] = k + 1
sub3.after[last] = k + 1
for j in st:
if sub3.h[sub3.after[j]] != sub3.h[j] and sub3.h[sub3.before[j]] != sub3.h[j]:
maximum = max(maximum, sub3.h[sub3.after[j]] - sub3.h[sub3.before[j]] - 1)
for j in range(m, i - 1, -1):
if sub3.after[0] != k + 1:
ans = max(ans, maximum * (j - i + 1))
j2 = 0
while j2 < len(sub3.contain[j]):
u = sub3.contain[j][j2]
ub = sub3.before[u]
ua = u
nj2 = j2
while nj2 < len(sub3.contain[j]) and ua == sub3.contain[j][nj2]:
nj2 += 1
ua = sub3.after[ua]
j2 = nj2
sub3.before[ua] = ub
sub3.after[ub] = ua
if sub3.h[sub3.after[ua]] != sub3.h[ua] and sub3.h[sub3.before[ua]] != sub3.h[ua]:
maximum = max(maximum, sub3.h[sub3.after[ua]] - sub3.h[sub3.before[ua]] - 1)
if sub3.h[sub3.after[ub]] != sub3.h[ub] and sub3.h[sub3.before[ub]] != sub3.h[ub]:
maximum = max(maximum, sub3.h[sub3.after[ub]] - sub3.h[sub3.before[ub]] - 1)
return ans
print(sub3.solve())Mình đã kiểm tra cả 3 bản code với 400 bảng ngẫu nhiên (có cả trường hợp nhiều chữ X cùng dòng, cùng cột) so với cách duyệt trâu, đều cho cùng kết quả. Với $N = M = 10^4$, $K = 1000$ thì bản C++ subtask 3 chỉ chạy khoảng 0.02 giây, bản Python khoảng 1.4 giây. Riêng bản Python của subtask 2 với $N = M = 500$ chạy mất gần 30 giây, nên nếu dùng Python thì các bạn nộp thẳng bản subtask 3 nhé.