Ma trận con có tổng lớn nhất
Đề bài
Cho mảng 2 chiều số nguyên $A$ gồm $n$ hàng, $m$ cột. Tìm ma trận con (một hình chữ nhật gồm các ô liên tiếp, có ít nhất 1 ô) có tổng lớn nhất.
Input:
- Dòng đầu gồm 2 số nguyên $n, m$.
- Mỗi dòng trong $n$ dòng tiếp theo gồm $m$ số nguyên $A_{i,j}$.
Output: một số nguyên là tổng lớn nhất tìm được.
Điều kiện: $1 \le n, m \le 500$; $|A_{i,j}| \le 10^9$.
Subtask:
- Subtask 1: 30% điểm đầu tiên có $n, m \le 20$.
- Subtask 2: 30% điểm tiếp theo có $n, m \le 100$.
- Subtask 3: 40% điểm còn lại có $n, m \le 500$.
2 3
1 -4 3
2 2 -34Lời mở đầu
Đây là phiên bản "2 chiều" của bài toán kinh điển dãy con liên tiếp có tổng lớn nhất. Bài có 3 subtask rất rõ ràng, nên mình sẽ đi đúng 3 bậc thang: vét cạn → mảng cộng dồn 2 chiều → nén hàng + thuật toán Kadane. Mỗi cách mình đều chạy thật trên bộ test của CLUE OJ để các bạn thấy rõ cách nào ăn được bao nhiêu điểm.
Ở ví dụ của đề, ma trận con tốt nhất là hàng 2, cột 1–2: $2 + 2 = 4$. Lấy thêm ô nào khác cũng làm tổng giảm (thử lấy cả 2 hàng, cột 1–2 thì $1 - 4 + 2 + 2 = 1$).
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 OJLộ trình lời giải, bấm vào từng phần để nhảy tới:
Bộ testBộ test chính thức có gì?
Bộ test có 100 test, chia đúng theo 3 subtask của đề:
| Test | Số test | $n$ lớn nhất | $m$ lớn nhất | $|A_{i,j}|$ lớn nhất | Đáp án lớn nhất |
|---|---|---|---|---|---|
| 1 – 30 | 30 | 20 | 20 | 10 | 714 |
| 31 – 60 | 30 | 100 | 100 | 999.969.430 | 263.844.878.430 |
| 61 – 100 | 40 | 500 | 500 | 999.994.192 | 5.816.427.024.228 |
- Test 1 – 30 là các ma trận nhỏ ($n, m \le 20$), giá trị chỉ trong khoảng $[-10, 10]$.
- Test 31 – 60 có $n, m \le 100$ (15 test đầy đủ $100 \times 100$), giá trị lên tới $\pm 10^9$.
- Test 61 – 100 có $n, m \le 500$, trong đó 20 test cuối (81 – 100) đều là $500 \times 500$.
- Khoảng 1/3 số ô là số âm. Đáp án lớn nhất lên tới khoảng $5{,}8 \cdot 10^{12}$ – vượt xa
int, bắt buộc dùnglong long. Về lý thuyết tổng lớn nhất có thể tới $500 \cdot 500 \cdot 10^9 = 2{,}5 \cdot 10^{14}$, vẫn vừalong long.
Kết quả chạy thật của 3 cách giải bên dưới trên từng subtask (giới hạn 1 giây):
| Subtask | Điểm | Điều kiện | Test | Cách 1 $O(n^3m^3)$ | Cách 2 $O(n^2m^2)$ | Cách 3 $O(n^2m)$ |
|---|---|---|---|---|---|---|
| Subtask 1 | 30% | $n, m \le 20$ | 1 – 30 | ✔ | ✔ | ✔ |
| Subtask 2 | 30% | $n, m \le 100$ | 31 – 60 | ✘ đúng 12/30 | ✔ | ✔ |
| Subtask 3 | 40% | $n, m \le 500$ | 61 – 100 | ✘ đúng 2/40 | ✘ đúng 17/40 | ✔ |
Ý tưởngÉp ma trận thành mảng 1 chiều
Một ma trận con được xác định bởi hàng trên $top$, hàng dưới $bot$, cột trái $l$ và cột phải $r$. Mấu chốt của cách tốt nhất là: nếu ta cố định cặp hàng $(top, bot)$, rồi "ép" mỗi cột lại thành 1 số
thì tổng của ma trận con $(top, bot, l, r)$ chính là $col[l] + col[l+1]$ $+ \dots + col[r]$. Bài toán 2 chiều biến thành bài 1 chiều quen thuộc: tìm đoạn con liên tiếp có tổng lớn nhất của mảng col – giải bằng Kadane trong $O(m)$:
cur = tổng lớn nhất của đoạn kết thúc tại cột j. Khi sang cột $j$: hoặc nối tiếp đoạn cũ ($cur + col[j]$), hoặc bỏ hết đoạn cũ làm lại từ $col[j]$ – chọn cái lớn hơn: cur = max(cur + col[j], col[j]). Đáp án là giá trị lớn nhất mà cur từng đạt.Thử hết $\frac{n(n+1)}{2}$ cặp hàng, mỗi cặp tốn $O(m)$ để cập nhật col và $O(m)$ để chạy Kadane, tổng cộng $O(n^2 m)$. Em nhập ma trận (các hàng cách nhau bởi dấu ;) rồi bấm Tiếp để xem từng bước:
Phần tô tím là dải hàng $top..bot$ đang xét, phần vàng là đoạn cột mà Kadane đang giữ (cur), khung xanh lá là ma trận con tốt nhất tìm được đến lúc đó. Trước khi tới cách này, mình đi từ cách dễ nhất nhé.
Cách 1Vét cạn: thử mọi ma trận con, cộng tay
Chọn góc trên trái $(x_1, y_1)$ và góc dưới phải $(x_2, y_2)$ bằng 4 vòng lặp lồng nhau, rồi dùng thêm 2 vòng lặp nữa để cộng tất cả các ô bên trong. Số ma trận con khoảng $\frac{n^2 m^2}{4}$, mỗi cái cộng tối đa $nm$ ô nên độ phức tạp là $O(n^3 m^3)$.
anskhởi tạo bằngLLONG_MIN(âm vô cùng) chứ không phải 0: nếu mọi số đều âm thì đáp án là số âm lớn nhất, khởi tạo 0 sẽ sai.- Biến tổng
svà mảngađều làlong longvì tổng có thể tới $2{,}5 \cdot 10^{14}$.
Kết quả chạy thật: đúng 44/100 test, 56 test còn lại bị quá thời gian (TLE); test chậm nhất trong số test đúng chạy 0.52 giây. Cách này ăn trọn Subtask 1 (30% điểm), và "ăn ké" thêm các test nhỏ của Subtask 2 (như $34 \times 36$, $91 \times 34$) cùng 2 test rất "dẹt" $11 \times 112$, $16 \times 164$ của Subtask 3: số phép cộng thật ra chỉ khoảng $\frac{n^3 m^3}{36}$. Bản Python: đúng 32/100 test (các test còn lại quá thời gian), test đúng chậm nhất 0.36 giây.
Cách 2Mảng cộng dồn 2 chiều: tính tổng mỗi ma trận con trong O(1)
Hai vòng lặp cộng tay ở cách 1 rất lãng phí. Ta dựng mảng cộng dồn 2 chiều $p[i][j]$ = tổng hình chữ nhật từ ô $(1, 1)$ tới ô $(i, j)$:
(cộng phần trên và phần trái thì phần chéo $p[i-1][j-1]$ bị cộng 2 lần nên trừ đi 1 lần). Khi đó tổng của ma trận con $(x_1, y_1) \to (x_2, y_2)$ là:
Lấy hình lớn, bỏ dải phía trên, bỏ dải bên trái, rồi cộng trả lại góc trên trái vì nó bị bỏ 2 lần. Giờ mỗi ma trận con chỉ tốn $O(1)$, cả thuật toán còn $O(n^2 m^2)$.
- Mảng
pđánh số từ 1, hàng 0 và cột 0 bằng 0 (biến toàn cục) nên công thức không bao giờ truy cập chỉ số âm. - Không cần lưu mảng
a: đọc tới đâu tínhptới đó.
Kết quả chạy thật: đúng 77/100 test, 23 test còn lại bị quá thời gian (TLE); test chậm nhất trong số test đúng chạy 0.49 giây. Ăn trọn Subtask 1 + 2 (60% điểm) và cả những test của Subtask 3 có $n \cdot m$ chưa quá lớn (ví dụ $260 \times 38$, $71 \times 495$), vì số phép tính thật ra là $\frac{n^2 m^2}{4}$. Các test bị TLE là những test có $n \cdot m$ lớn nhất (từ $174 \times 380$ trở lên, và toàn bộ 20 test $500 \times 500$ – cỡ $1{,}5 \cdot 10^{10}$ phép tính). Bản Python: đúng 44/100 test (các test còn lại quá thời gian), test đúng chậm nhất 0.83 giây.
Cách 3Nén hàng + Kadane – O(n²·m)
Đây là cài đặt của ý tưởng ở trên. Với mỗi hàng trên top, ta cho hàng dưới bot chạy dần xuống; mỗi lần bot tăng 1 thì chỉ cần cộng thêm hàng bot vào mảng col (không phải cộng lại từ đầu). Sau đó chạy Kadane trên col.
col[j] += a[bot][j]: nhờ cập nhật nối tiếp, mảngcolluôn là tổng cột $j$ từ hàngtoptớibotmà chỉ tốn $O(m)$.- Trong Kadane,
cur = max(cur + col[j], col[j]): nếucurtrước đó âm thì nó chỉ làm hại, ta bỏ đi và bắt đầu đoạn mới tại cột $j$. ans = max(ans, cur)được làm sau mỗi cột, nên kể cả khi mọi số đều âm, đáp án vẫn là số âm lớn nhất (đoạn chỉ có 1 ô).- Với $n = m = 500$: khoảng $\frac{500 \cdot 501}{2} \cdot 500 \cdot 2$ $\approx 1{,}25 \cdot 10^8$ phép tính đơn giản – chạy dưới 0,2 giây. Nếu $n > m$ thì có thể đổi vai hàng/cột để nhanh hơn nữa, nhưng ở bài này không cần.
Kết quả chạy thật: đúng 100/100 test; test chậm nhất trong số test đúng chạy 0.16 giây. Full 100 điểm. Bản Python: đúng 73/100 test (các test còn lại quá thời gian), test đúng chậm nhất 0.55 giây.
Nhận xét
Đăng nhận xét