Hiểu bài toán

Bài toán yêu cầu tìm các phần tử 'yên ngựa' (saddle point) trong một ma trận có kích thước m hàng và n cột. Một phần tử được coi là yên ngựa nếu nó đồng thời là giá trị lớn nhất trong hàng của nó và là giá trị nhỏ nhất trong cột của nó (hoặc ngược lại, tùy theo định nghĩa cụ thể của đề bài). Tuy nhiên, dựa trên các giải pháp được cung cấp, có vẻ như định nghĩa đang được sử dụng là: một phần tử a[i][j] là yên ngựa nếu nó đồng thời là phần tử lớn nhất trong hàng i và là phần tử lớn nhất trong cột j. (Lưu ý: Các giải pháp có sự mâu thuẫn về điều kiện 'lớn nhất' hay 'nhỏ nhất', nhưng Solution 3 và Solution 2 đều kiểm tra điều kiện 'max hàng và max cột' hoặc 'min hàng và max cột'. Solution 3 kiểm tra (a[i][j]==minH[i] && a[i][j]==maxC[j]) || (a[i][j]==maxH[i] && a[i][j]==minC[j]) - tức là (min hàng & max cột) hoặc (max hàng & min cột). Solution 2 kiểm tra a[i][j]==h[i] && a[i][j]==HH[j] (max hàng & max cột) và một điều kiện khác. Do sự mơ hồ, chúng ta sẽ tập trung vào logic chung: so sánh giá trị phần tử hiện tại với giá trị tối thiểu/tối đa của hàng và cột tương ứng. Bài toán này về cơ bản là đếm số lượng phần tử thỏa mãn một trong các điều kiện đặc biệt liên quan đến giá trị lớn nhất/nhỏ nhất của hàng và cột chứa nó.

Các cách tiếp cận

Cách Tối ưu hóa Duyệt (Precomputation)

#include <bits/stdc++.h>
using namespace std;

int m, n, a[1005][1005];
int minH[1005], maxH[1005]; // Min, Max của hàng i
int minC[1005], maxC[1005]; // Min, Max của cột j

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    if(fopen("bai1.inp","r")) {
        freopen("bai1.inp","r",stdin);
        freopen("bai1.out","w",stdout);
    }

    cin >> m >> n;
    // Khởi tạo giá trị cho min/max
    // Do các giải pháp dùng mảng toàn cục nên mặc định là 0, nhưng để an toàn nên gán giá trị极端
    // Solution 3 dùng a[1][1] để khởi tạo, rất tốt.

    for(int i = 1; i <= m; i++) {
        minH[i] = a[i][1];
        maxH[i] = a[i][1];
        for(int j = 2; j <= n; j++) {
            minH[i] = min(minH[i], a[i][j]);
            maxH[i] = max(maxH[i], a[i][j]);
        }
    }

    for(int j = 1; j <= n; j++) {
        minC[j] = a[1][j];
        maxC[j] = a[1][j];
        for(int i = 2; i <= m; i++) {
            minC[j] = min(minC[j], a[i][j]);
            maxC[j] = max(maxC[j], a[i][j]);
        }
    }

    int count = 0;
    for(int i = 1; i <= m; i++) {
        for(int j = 1; j <= n; j++) {
            // Logic từ Solution 3: (minHang && maxCot) || (maxHang && minCot)
            if ((a[i][j] == minH[i] && a[i][j] == maxC[j]) || 
                (a[i][j] == maxH[i] && a[i][j] == minC[j])) {
                count++;
            }
        }
    }
    cout << count;
    return 0;
}

• Time Complexity: O(m * n)
• Space Complexity: O(m + n)

Approach này là cách tiếp cận chuẩn và hiệu quả nhất cho bài toán này. Thay vì với mỗi phần tử lại duyệt lại toàn bộ hàng và cột để tìm max/min (O(mn) cho mỗi phần tử -> Tổng O(mn(m+n))), ta chỉ cần duyệt qua ma trận 2 lần. Lần 1 để tính toán và lưu trữ giá trị lớn nhất/nhỏ nhất của mỗi hàng vào mảng maxH/minH. Lần 2 để tính toán và lưu trữ giá trị lớn nhất/nhỏ nhất của mỗi cột vào mảng maxC/minC. Sau đó, duyệt qua từng phần tử a[i][j] một lần nữa, so sánh giá trị của nó với các giá trị đã lưu để kiểm tra điều kiện yên ngựa. Độ phức tạp thời gian là O(mn), không gian O(m+n).

Cách Brute Force (Duyệt lồng nhau)

// Pseudocode cho Brute Force
#include <iostream>
using namespace std;

int main() {
    // Giả sử ma trận a đã được nhập
    int count = 0;
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            int val = a[i][j];
            // Tìm max/min trong hàng i
            int minRow = a[i][1], maxRow = a[i][1];
            for (int k = 2; k <= n; k++) {
                if (a[i][k] < minRow) minRow = a[i][k];
                if (a[i][k] > maxRow) maxRow = a[i][k];
            }
            // Tìm max/min trong cột j
            int minCol = a[1][j], maxCol = a[1][j];
            for (int k = 2; k <= m; k++) {
                if (a[k][j] < minCol) minCol = a[k][j];
                if (a[k][j] > maxCol) maxCol = a[k][j];
            }
            // Kiểm tra điều kiện
            if ((val == minRow && val == maxCol) || (val == maxRow && val == minCol)) {
                count++;
            }
        }
    }
    return 0;
}

• Time Complexity: O(m * n * (m + n))
• Space Complexity: O(1)

Đây là cách giải quyết trực tiếp nhất, mô phỏng lại định nghĩa của bài toán. Với mỗi phần tử tại vị trí (i, j), ta duyệt qua toàn bộ hàng thứ i để tìm giá trị lớn nhất và nhỏ nhất, và duyệt qua toàn bộ cột thứ j để tìm giá trị lớn nhất và nhỏ nhất. Sau đó ta kiểm tra xem phần tử hiện tại có phải là phần tử yên ngựa hay không. Cách này rất dễ hiểu nhưng không hiệu quả về mặt thời gian执行do lặp lại nhiều thao tác.

Cách Đọc và xử lý đồng thời (Stream Processing)

// Phù hợp với Solution 1 và Solution 2
// Chỉ cần 1 vòng lặp duy nhất
// Tuy nhiên, để kiểm tra điều kiện yên ngựa, ta vẫn cần so sánh với hàng/cột hiện tại.
// Vì vậy, cách này thường chỉ tối ưu được bộ nhớ nếu không lưu ma trận, nhưng ở đây ta vẫn cần ma trận để kiểm tra điều kiện.
// Solution 1 thực chất vẫn lưu ma trận (a[105][105]).
// Logic của Solution 2:
// 1. Duyệt hàng -> Tính maxHang, minHang.
// 2. Duyệt cột -> Tính maxCot, minCot.
// 3. Kiểm tra.
// => Cấu trúc tương tự Approach 1.

• Time Complexity: O(m * n)
• Space Complexity: O(m * n)

Thực chất, các solution được cung cấp đều tuân theo cấu trúc Approach 1 (Precomputation). Solution 1 dùng mảng toàn cục và memset bằng INF, Solution 2 dùng 1e18 để tránh tràn số. Không có cách tiếp cận Brute Force đúng nghĩa nào được chấp nhận và Optimal trong các giải pháp đã cho, tất cả đều đã tối ưu hóa bằng cách precompute.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Cần phân biệt rõ định nghĩa 'yên ngựa' của bài toán. Trong các code mẫu, có vẻ tác giả đang đếm các phần tử cùng là max của hàng và min của cột, hoặc max hàng và max cột.
• Tách biệt việc tính toán giá trị tối đa/tối thiểu của hàng và cột khỏi việc kiểm tra điều kiện giúp giảm độ phức tạp từ O((m+n)mn) xuống O(m*n).
• Sử dụng các giá trị khởi tạo cẩn thận (ví dụ: a[i][1] như Solution 3 hoặc 1e18 như Solution 2) để tránh lỗi logic với các số âm hoặc dương lớn.

Lỗi thường gặp

• Lỗi truy cập ngoài mảng: Khi duyệt cột, cần đảm bảo chỉ số hàng không vượt quá m.
• Sai lệch định nghĩa: Code của Solution 3 kiểm tra (minH[i] && maxC[j]) || (maxH[i] && minC[j]) (kết hợp 2 trường hợp), trong khi một số bài khác chỉ kiểm tra một trường hợp. Cần đọc kỹ đề bài.
• Kiểu dữ liệu: Dùng int có thể bị tràn số nếu giá trị phần tử lớn, các Solution đều dùng long long hoặc int với khoảng giá trị vừa đủ.