Xóa Phần Tử Trong Ma Trận (TABLEDEL)

Nguồn: LuyenCode Độ khó: Dễ Mảng đánh dấu Ma trận Đếm

Đề bài

Cho một bảng ô vuông gồm $n$ dòng và $m$ cột. Các dòng được đánh số từ $1$ đến $n$, các cột được đánh số từ $1$ đến $m$. Ô nằm ở dòng $i$ và cột $j$ được gọi là ô $(i, j)$. Có $k$ ô màu đen trên bảng, ô đen thứ $i$ nằm ở vị trí $(x_i, y_i)$. Các ô còn lại trong bảng đều có màu trắng.

Bạn có thể thực hiện một trong hai loại thao tác sau (mỗi thao tác có thể được thực hiện nhiều lần hoặc không lần nào):

• Chọn một dòng chỉ gồm các ô màu trắng, và xóa dòng đó khỏi bảng.
• Chọn một cột chỉ gồm các ô màu trắng, và xóa cột đó khỏi bảng.

Hãy tìm cách thực hiện các loại thao tác trên, sao cho số ô còn lại trong bảng là nhỏ nhất có thể.

Dữ liệu vào:

• Dòng đầu tiên gồm ba số nguyên $n, m, k$ $(1 \le n, m, k \le 10^5)$ – số dòng, số cột của bảng và số ô đen.
• $k$ dòng tiếp theo, dòng thứ $i$ gồm hai số nguyên $x_i, y_i$ $(1 \le x_i \le n,\ 1 \le y_i \le m)$ – vị trí của ô đen thứ $i$. Dữ liệu vào đảm bảo không có hai ô đen nào ở cùng vị trí.

Dữ liệu ra: In ra số ô còn lại nhỏ nhất có thể sau khi thực hiện hai loại thao tác trên.

Giới hạn: 1 giây, 256 MB.

Ví dụ 1 – input

3 4 3
2 1
2 4
3 3

Ví dụ 1 – output

6

Ví dụ 2 – input

4 4 4
2 1
3 4
4 1
4 4

Ví dụ 2 – output

6

Gợi ý (của đề):

Bảng lúc ban đầu trong ví dụ thứ nhất, và ta có thể thực hiện thao tác biến đổi bảng như sau (các ô màu đỏ tương ứng với dòng hoặc cột được xóa):

Ví dụ 1: xóa dòng 1 (đỏ) → xóa cột 2 (đỏ) → còn $2 \times 3 = 6$ ô.

Bảng lúc ban đầu trong ví dụ thứ hai, và ta có thể thực hiện thao tác biến đổi bảng như sau:

Ví dụ 2: xóa cột 2 → xóa cột 3 cũ → xóa dòng 1 → còn $3 \times 2 = 6$ ô.

Lời mở đầu

Bài này nhìn đề có vẻ "ma trận", "xóa dòng xóa cột" nghe rất hoành tráng, nhưng thực ra chỉ cần một nhận xét nhỏ cùng kỹ thuật mảng đánh dấu là xử lý gọn gàng. Cái bẫy lớn nhất của bài lại nằm ngay ở cách làm "ngây thơ" đúng như đề mô tả – mình sẽ phân tích kỹ vì sao nó "toang" ngay từ bước đầu tiên nhé 😇.

Bạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì link bài đây nhé:

Mình giải thích ví dụ mẫu để bạn nào chưa hiểu đề sẽ hiểu rõ. Ở ví dụ 1, bảng có 3 dòng × 4 cột = 12 ô, ô đen nằm ở $(2,1)$, $(2,4)$, $(3,3)$. Dòng 1 không có ô đen nào nên xóa được (mất 4 ô). Còn lại 2 dòng; cột 2 không có ô đen nào nên xóa được (mất thêm 2 ô). Các dòng, cột còn lại đều có ô đen nên không xóa được nữa ⇒ còn $12 - 4 - 2 = 6$ ô.

Ở ví dụ 2, bảng 4 × 4 = 16 ô. Dòng 1 trắng hoàn toàn, cột 2 và cột 3 cũng trắng hoàn toàn. Xóa hết 1 dòng và 2 cột đó thì còn lại bảng 3 dòng × 2 cột = 6 ô.

Nhận xét quan trọng

Xóa một dòng/cột trắng không bao giờ làm thay đổi việc một dòng/cột khác có ô đen hay không (ta chỉ bỏ đi ô trắng). Vì vậy thứ tự xóa không quan trọng: cứ xóa hết các dòng trắng và hết các cột trắng là được số ô ít nhất. Đáp án = (số dòng có ô đen) × (số cột có ô đen).

Link nộp bài

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 OJ

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Cách 1Tạo cả ma trận N × M · MLE/TLECách 2Mảng đánh dấu dòng/cột · O(N + M + K)

Cách 1Làm đúng y như đề mô tả – không ổn!

Nếu bạn nào làm theo đúng cách đề bài mô tả, tức là tạo ra ma trận có $N$ dòng $M$ cột, ví dụ ma trận kiểu bool (true/false), rồi đánh dấu tọa độ các ô đen trên ma trận là false; sau đó duyệt ma trận xét dòng nào toàn true (ô trắng) thì xóa dòng đó đi; xóa hết các dòng rồi thì xét qua các cột, cột nào toàn true thì xóa cột đó; sau cùng đếm số ô còn lại là kết quả.

Thì nếu làm như vậy các bạn đã "toang" ngay từ bước khởi đầu rồi, tức là bước tạo ra ma trận $N$ dòng, $M$ cột. Giả sử ma trận kiểu bool, mỗi phần tử chỉ chiếm 1 byte, thì ma trận cần $N \cdot M$ byte. Mà $N, M$ tối đa tới $10^5$ ⇒ $N \cdot M$ có thể lên tới $10^{10}$ (10 tỷ) phần tử, tức là 10 tỷ byte. Thử làm phép tính nhé:

10,000,000,000 / 1024 = 9,765,625 KB
9,765,625 / 1024 ≈ 9,536.743 MB

Trong khi giới hạn bộ nhớ chỉ có 256 MB, tức là ta gấp cỡ 37 lần giới hạn ⇒ chắc chắn bị MLE (Memory Limit Exceeded). Thậm chí giả sử bộ nhớ cho phép đi nữa (thực tế không bao giờ được) thì việc duyệt hết $10^{10}$ phần tử cũng bị TLE (Time Limit Exceeded), vì 1 giây chỉ chạy được cỡ $10^8$ phép tính – $10^{10}$ là vượt cả 100 lần rồi.

Nhìn giới hạn trước khi code

Cách làm ở trên không ổn, và ta có thể thấy rõ ngay từ đầu chỉ bằng cách nhân giới hạn $N \cdot M$ – để khỏi mất công cài đặt nha các bạn. Vì vậy mình không đưa code cho cách này.

Cách 2Mảng đánh dấu dòng và cột – O(N + M + K)

Vẫn dựa theo một phần tư tưởng xử lý như đề mô tả, nhưng ta không cần đánh dấu từng ô trong ma trận, mà chỉ đánh dấu cả dòng, cả cột: dòng nào, cột nào có sự xuất hiện của ô đen. Đó chính là kỹ thuật mảng đánh dấu.

Lấy ví dụ 1: ma trận 3 dòng × 4 cột. Ta tạo mảng đánh dấu a có $3 + 1 = 4$ phần tử (index 0..3, bỏ qua index 0, chỉ dùng 1..3 ứng với số thứ tự dòng), khởi tạo tất cả là false. Tương tự tạo mảng b có $4 + 1 = 5$ phần tử cho các cột, cũng khởi tạo false.

Với mỗi ô đen $(i, j)$ đọc vào, ta đánh dấu a[i] = true; b[j] = true;. Sau khi đọc xong ví dụ 1 ta có:

Dòng	a[1]	a[2]	a[3]	–
	false	true	true	–
Cột	b[1]	b[2]	b[3]	b[4]
	true	false	true	true

Giờ duyệt mảng a xem có bao nhiêu dòng trắng: dòng nào còn false nghĩa là chưa có ô đen nào – dòng trắng. Ở đây chỉ có a[1] là false ⇒ 1 dòng trắng. Mỗi dòng có $M$ ô nên số ô bỏ đi $= 1 \cdot M = 1 \cdot 4 = 4$.

Tiếp tục xét mảng b: chỉ có cột 2 trắng. Số ô trên một cột chính là số dòng của ma trận, nhưng nhớ là trước đó ta đã bỏ 1 dòng rồi, nên lúc này ma trận chỉ còn 2 dòng ⇒ số ô bỏ đi trên cột 2 là $1 \cdot 2 = 2$.

Cả thảy bỏ đi $4 + 2 = 6$ ô ⇒ còn lại $N \cdot M - 6 = 12 - 6 = 6$ ô. Đáp án in ra 6 ✅.

Thử với ví dụ 2: a = [false, true, true, true] (dòng 1..4), b = [true, false, false, true] (cột 1..4).

• Xóa 1 dòng (dòng 1) ⇒ số ô bị xóa $= 1 \cdot 4 = 4$.
• Xóa 2 cột (cột 2, 3), lúc này còn 3 dòng ⇒ số ô bị xóa $= 2 \cdot 3 = 6$.
• Tổng số ô bị xóa $= 4 + 6 = 10$ ⇒ còn lại $16 - 10 = 6$. Đáp án in ra 6 ✅.

Công thức

Gọi temp_n = số dòng còn lại (dòng có ô đen). Số ô bị xóa: $cnt = (n - temp\_n) \cdot m + (\text{số cột trắng}) \cdot temp\_n$. Đáp án: $n \cdot m - cnt$.

Minh hoạ đánh dấu và xóa

Em nhập kích thước bảng và các ô đen (mỗi ô là cặp x y, cách nhau bởi dấu ;), rồi bấm Tiếp để xem từng ô đen "nhuộm" dòng/cột của nó, sau đó các dòng/cột trắng bị tô đỏ và xóa:

n m ô đen

Ví dụ nhanh:

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(0);
    cin.tie(0);
    long long n, m, k;
    cin >> n >> m >> k;
    bool a[n + 1] = {false}, b[m + 1] = {false};
    while(k--){
        int x, y;
        cin >> x >> y;
        a[x] = true;
        b[y] = true;
    }
    long long temp_n = n;
    for(int i = 1; i <= n; ++i){
        if(a[i] == false){
            temp_n--;
        }
    }
    long long cnt = (n - temp_n) * m;
    for(int i = 1; i <= m; ++i){
        if(b[i] == false){
            cnt += temp_n;
        }
    }
    cout << (n * m) - cnt;
    return 0;
}

import sys

def main():
    data = sys.stdin.buffer.read().split()
    n, m, k = int(data[0]), int(data[1]), int(data[2])
    a = [False] * (n + 1)
    b = [False] * (m + 1)
    p = 3
    for _ in range(k):
        x, y = int(data[p]), int(data[p + 1])
        p += 2
        a[x] = True
        b[y] = True
    temp_n = n
    for i in range(1, n + 1):
        if a[i] == False:
            temp_n -= 1
    cnt = (n - temp_n) * m
    for i in range(1, m + 1):
        if b[i] == False:
            cnt += temp_n
    print(n * m - cnt)

main()

C++▶ Chạy tay từng dòng codeĐánh dấu dòng/cột có ô đen, đếm số ô bị xóa rồi lấy n × m trừ đi.

Dữ liệu vào (stdin) – sửa thoải mái3 4 3 2 1 2 4 3 3

Dữ liệu mẫu:

1#include <bits/stdc++.h>

2using namespace std;

3

4int main(){

5 ios::sync_with_stdio(0);

6 cin.tie(0);

7 long long n, m, k;

8 cin >> n >> m >> k;

9 bool a[n + 1] = {false}, b[m + 1] = {false};

10 while(k--){

11 int x, y;

12 cin >> x >> y;

13 a[x] = true;

14 b[y] = true;

15 }

16 long long temp_n = n;

17 for(int i = 1; i <= n; ++i){

18 if(a[i] == false){

19 temp_n--;

20 }

21 }

22 long long cnt = (n - temp_n) * m;

23 for(int i = 1; i <= m; ++i){

24 if(b[i] == false){

25 cnt += temp_n;

26 }

27 }

28 cout << (n * m) - cnt;

29 return 0;

30}

ChậmVừaNhanhRất nhanh

Giải thích một số chỗ trong code:

1. bool a[n + 1] = {false}; nghĩa là khởi tạo mảng a có $n + 1$ phần tử, tất cả đều là false (trong lập trình 0 ⇔ false, 1 ⇔ true). Nói rõ hơn thì chỗ này chỉ gán giá trị cho ô đầu tiên a[0] là 0 thôi, nhưng nguyên tắc khi khởi tạo mảng bằng danh sách {...} thì toàn bộ các ô còn lại không được liệt kê sẽ mặc định là 0. Nên toàn bộ mảng đều là 0 hết.
2. Biến temp_n lưu số dòng còn lại sau khi xóa dòng. Biến cnt đếm số ô đã bị xóa. Sau khi xóa dòng, số ô bị xóa = (số dòng bị xóa) × (số cột), mà số dòng bị xóa $= n - temp\_n$, nên mới có cnt = (n - temp_n) * m;. Rồi cứ thấy cột nào bị xóa thì cộng thêm số dòng còn lại: cnt += temp_n;. Đáp án là (n * m) - cnt.
3. Phải khai báo n, m, temp_n, cnt kiểu long long (8 byte) để tránh tràn số. Nếu n, m là int thì phép n * m được tính trong vùng nhớ tạm kiểu int, mà khi $n = m = 10^5$ thì $n \cdot m = 10^{10}$ – int không chứa nổi ⇒ tràn số và sai. Cứ để hết long long cho chắc nha các bạn.

Lưu ý nhỏ về kích thước mảng b

Trong bản code gốc mình đăng trên Facebook có chỗ khai báo b[n + 1], đúng ra mảng cột phải là b[m + 1]. Khi $m \gt n$ (vd: $n = 1$, $m = 10^5$) thì b[y] sẽ ghi ra ngoài mảng – có thể vẫn "lọt" test nhưng là lỗi tiềm ẩn. Code ở trên đã sửa thành b[m + 1].

Về mảng khai báo kiểu bool a[n + 1]

Đây là mảng có kích thước thay đổi (VLA) – g++ cho phép, và với $n, m \le 10^5$ thì chỉ tốn cỡ 0.2 MB trên stack nên vẫn an toàn. Nếu muốn chuẩn C++ hơn thì các bạn có thể dùng vector<bool> a(n + 1, false), logic y hệt.

Đánh giá độ phức tạp của cách làm này:

• Không gian: $O(N)$ cho mảng a + $O(M)$ cho mảng b, tức $O(N + M)$ – theo quy tắc cộng Big-O có thể viết $O(\max(N, M))$. Tính chính xác với trường hợp xấu nhất $N = M = 10^5$: $2 \cdot 10^5$ byte ≈ 195.3 KB ≈ 0.2 MB. Giới hạn cho tới 256 MB mà ta dùng có 0.2 MB thôi hehe.
• Thời gian: $O(N)$ khởi tạo mảng a + $O(M)$ khởi tạo mảng b + $O(K)$ đọc tọa độ các ô đen + $O(N)$ duyệt mảng a + $O(M)$ duyệt mảng b ⇒ $O(N + M + K)$, hay $O(\max(N, M, K))$. Trường hợp xấu nhất $N = M = K = 10^5$ thì tổng cỡ $5 \cdot 10^5$ lần lặp – ít hơn cả trăm lần so với ngưỡng 1 giây (cỡ $10^8$), yên tâm không TLE.

Không gian$O(N + M)$

Thời gian$O(N + M + K)$

Ghi chú của mình: code C++ và Python ở trên đã được kiểm tra với 500 bộ test ngẫu nhiên nhỏ ($n, m \le 7$), so với code vét cạn mô phỏng xóa từng dòng/cột trên ma trận thật – khớp hết. Với $n = m = k = 10^5$, bản C++ chạy khoảng 0.2 giây và bản Python khoảng 0.8 giây trên máy mình (thời gian thực, đã tính cả khởi động và đọc dữ liệu); các trường hợp biên như $n = 1, m = 10^5$ hay $n = m = 10^5, k = 1$ (đáp án 1) cũng đúng.

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇