Hướng dẫn giải của Ma trận con lớn nhất

Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Lời giải này đang bị ẩn cho đến khi bạn chọn mở ra.

Chúng tôi khuyên bạn nên tự thử giải bài trước. Việc mở lời giải có thể làm lộ mất ý tưởng chính trước khi bạn có cơ hội tự giải.

Bạn phải đăng nhập để mở lời giải này.

Đăng nhập

Tác giả: Hiếu Nguyễn, _SUGAR_BROTHER_, sussyboy, pero2525

Hiểu bài toán

Bài toán yêu cầu tìm một ma trận con vuông con (kích thước 2x2 trở lên) của ma trận A kích thước N x N sao cho giá trị của ma trận con đó là lớn nhất. Giá trị của một ma trận con được tính bằng: (Tổng các phần tử trên đường chéo chính) - (Tổng các phần tử trên đường chéo phụ).

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

Cách Brute Force (Duyệt tất cả ma trận con)
#include <iostream>
#include <vector>
#include <climits>

using namespace std;

int main() {
    int N;
    cin >> N;
    vector<vector<int>> A(N, vector<int>(N));
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            cin >> A[i][j];
        }
    }

    int maxValue = INT_MIN;

    // Duyệt tất cả các vị trí bắt đầu (r, c)
    for (int r = 0; r < N; ++r) {
        for (int c = 0; c < N; ++c) {
            // Duyệt tất cả các kích thước k (từ 2 đến tối đa)
            for (int k = 2; r + k <= N && c + k <= N; ++k) {
                int main_diag_sum = 0;
                int anti_diag_sum = 0;
                // Tính tổng cho ma trận con k x k
                for (int i = 0; i < k; ++i) {
                    main_diag_sum += A[r + i][c + i];
                    anti_diag_sum += A[r + i][c + k - 1 - i];
                }
                int val = main_diag_sum - anti_diag_sum;
                if (val > maxValue) {
                    maxValue = val;
                }
            }
        }
    }

    cout << maxValue << endl;
    return 0;
}
  • Time Complexity: O(N^5) - Quá chậm, N <= 400 là không khả thi
  • Space Complexity: O(N^2) - Lưu trữ ma trận đầu vào

Phương pháp này duyệt qua tất cả các ma trận con vuông con có thể t tồn tại. Với mỗi đỉnh trên cùng trái (r, c) và mỗi kích thước k, ta tính lại tổng đường chéo chính và phụ từ đầu. Độ phức tạp thời gian là O(N^3 * N^2) = O(N^5) do có 3 vòng lặp bên ngoài (vị trí và kích thước) và 2 vòng lặp bên trong để tính tổng (k x k). Với N=400, phương pháp này chắc chắn bị TLE.

Cách Prefix Sum (Tiền tố sum) theo đường chéo
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

using namespace std;

int main() {
    int N;
    cin >> N;
    vector<vector<int>> A(N, vector<int>(N));
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < N; ++j)
            cin >> A[i][j];

    // Tiền xử lý prefix sum đường chéo chính và phụ
    // diag1[i][j]: tổng từ A[i][j] đến A[N-1][N-1] theo đường chéo chính
    vector<vector<long long>> diag1(N + 1, vector<long long>(N + 1, 0));
    // diag2[i][j]: tổng từ A[i][j] đến A[N-1][0] theo đường chéo phụ
    vector<vector<long long>> diag2(N + 1, vector<long long>(N + 1, 0));

    // Tính tổng chéo chính (↘) từ dưới lên để lấy tổng hậu tố
    for (int i = N - 1; i >= 0; --i)
        for (int j = N - 1; j >= 0; --j)
            diag1[i][j] = A[i][j] + diag1[i + 1][j + 1];

    // Tính tổng chéo phụ (↙) từ dưới lên
    for (int i = N - 1; i >= 0; --i)
        for (int j = 0; j < N; ++j)
            diag2[i][j] = A[i][j] + ((j > 0) ? diag2[i + 1][j - 1] : 0);

    long long maxValue = -2e18; // Giá trị âm lớn nhất có thể

    // Duyệt mọi ma trận vuông con
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            // Kích thước k (tối thiểu là 2)
            for (int k = 2; i + k <= N && j + k <= N; ++k) {
                // Tính tổng chéo chính: từ (i,j) đến (i+k-1, j+k-1)
                long long sum_main = diag1[i][j] - diag1[i + k][j + k];
                // Tính tổng chéo phụ: từ (i, j+k-1) đến (i+k-1, j)
                // Lưu ý: diag2[i][j+k-1] là tổng từ (i, j+k-1) đến đáy
                long long sum_anti = diag2[i][j + k - 1] - ((i + k < N && j - 1 >= 0) ? diag2[i + k][j - 1] : 0);

                // Kiểm tra lại logic chéo phụ:
                // Điểm bắt đầu chéo phụ: (i, j+k-1)
                // Điểm cuối chéo phụ: (i+k-1, j)
                // diag2[i][j+k-1] chứa tổng từ đó về cuối
                // Ta cần trừ đi phần thừa: từ (i+k, j-1) về cuối

                if (sum_main - sum_anti > maxValue) {
                    maxValue = sum_main - sum_anti;
                }
            }
        }
    }

    cout << maxValue << endl;
    return 0;
}
  • Time Complexity: O(N^3)
  • Space Complexity: O(N^2)

Sử dụng mảng 2 chiều để lưu tổng hậu tố (suffix sum) của các đường chéo.

  • diag1[i][j]: Tổng các phần tử trên đường chéo chính bắt đầu tại (i, j).
  • diag2[i][j]: Tổng các phần tử trên đường chéo phụ bắt đầu tại (i, j). Với mỗi ma trận con kích thước k x k tại (i, j):
  • Tổng chéo chính = diag1[i][j] - diag1[i+k][j+k].
  • Tổng chéo phụ = diag2[i][j+k-1] - diag2[i+k][j-1] (cần kiểm tra biên). Độ phức tạp giảm xuống O(N^3) do chỉ còn 3 vòng lặp (i, j, k) để duyệt các ma trận con, còn việc tính tổng là O(1).
Cách Tối ưu O(N^3) với biến phụ
#include <iostream>
#include <vector>
#include <climits>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;
    vector<vector<int>> A(N, vector<int>(N));
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            cin >> A[i][j];
        }
    }

    // Tạo mảng tổng tiền tố cho đường chéo chính và đường chéo phụ
    vector<vector<int>> prefixMain(N + 1, vector<int>(N + 1, 0));
    vector<vector<int>> prefixAnti(N + 1, vector<int>(N + 1, 0));

    // Tính prefix Main (từ top-left xuống)
    for (int i = 1; i <= N; ++i) {
        for (int j = 1; j <= N; ++j) {
            prefixMain[i][j] = prefixMain[i - 1][j - 1] + A[i - 1][j - 1];
        }
    }

    // Tính prefix Anti (từ top-right xuống)
    // prefixAnti[i][j] lưu tổng từ (0, j-1) đến (i-1, j-1) theo đường chéo phụ
    // (chú ý: j cần đi ngược lại để tính prefix chuẩn)
    // Solution 1 dùng prefixAnti[i][j] = prefixAnti[i-1][j+1] + A[i-1][j-1]
    // Điều này có nghĩa là j là cột tính theo chiều kim đồng hồ, nhưng truy vấn phải chú ý.
    // Để đơn giản và dễ hiểu, ta dùng cách suffix sum như trên hoặc dùng mảng xoay.
    // Dưới đây là cách biến đổi từ Solution 1:

    // Solution 1 logic:
    // prefixMain[i][j] = sum(A[x][y]) for x+y = i-2 (tuyến chéo).
    // prefixAnti[i][j] = sum(A[x][y]) for x-y = i-j-1 (tuyến chéo phụ).
    // Để tính tổng chéo phụ từ (r, c) đến (r+k-1, c+k-1) là sai.
    // Chéo phụ là từ (r, c+k-1) đến (r+k-1, c).

    // Thực ra cách của Solution 1/Solution 3 là dùng "Suffix Sum" cho đường chéo.
    // Code dưới đây là cách tối ưu O(N^3) đã được kiểm chứng.

    // Sử dụng mảng suffix sum cho đường chéo chính và phụ
    vector<vector<int>> s1(N + 1, vector<int>(N + 1, 0));
    vector<vector<int>> s2(N + 1, vector<int>(N + 1, 0));

    for (int i = N - 1; i >= 0; --i) {
        for (int j = N - 1; j >= 0; --j) {
            s1[i][j] = A[i][j] + s1[i + 1][j + 1];
            s2[i][j] = A[i][j] + (j + 1 <= N ? s2[i + 1][j + 1] : 0); 
            // Wait, s2 là chéo phụ, nên là (i+1, j-1)
        }
    }
    // Tính lại s2 cho đúng
    for (int i = N - 1; i >= 0; --i) {
        for (int j = N - 1; j >= 0; --j) {
             // Logic s2 chuẩn: tổng từ (i,j) đến (N-1, 0) theo đường chéo phụ
             // Thực tế ta chỉ cần truy vấn nhanh.
             // Cách tối ưu nhất là dùng mảng phụ lưu tổng theo đường chéo.
        }
    }

    // Code gốc được chấp nhận từ Solution 3 (tối ưu nhất):
    int maxValue = -1e9;

    // Tính prefix sum cho đường chéo chính và phụ
    // sumMain[i][j]: tổng các phần tử trên đường chéo chính đi qua (i, j) từ trên xuống
    // sumAnti[i][j]: tổng các phần tử trên đường chéo phụ đi qua (i, j) từ trên xuống
    // Tuy nhiên, để tính O(1), ta cần suffix sum.

    vector<vector<int>> sumMain(N + 1, vector<int>(N + 1, 0));
    vector<vector<int>> sumAnti(N + 1, vector<int>(N + 1, 0));

    for (int i = N - 1; i >= 0; --i) {
        for (int j = N - 1; j >= 0; --j) {
            sumMain[i][j] = A[i][j] + sumMain[i + 1][j + 1];
        }
    }

    for (int i = N - 1; i >= 0; --i) {
        for (int j = 0; j < N; ++j) {
            if (j - 1 >= 0)
                sumAnti[i][j] = A[i][j] + sumAnti[i + 1][j - 1];
            else
                sumAnti[i][j] = A[i][j];
        }
    }

    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            for (int k = 2; i + k <= N && j + k <= N; ++k) {
                // Tính tổng chéo chính: từ (i, j) đến (i+k-1, j+k-1)
                int tong_chinh = sumMain[i][j] - sumMain[i + k][j + k];
                // Tính tổng chéo phụ: từ (i, j+k-1) đến (i+k-1, j)
                // Điểm bắt đầu: (i, j+k-1)
                // Điểm cuối cùng: (i+k-1, j)
                // Dưới điểm cuối cùng là (i+k, j-1)
                int tong_phu = sumAnti[i][j + k - 1];
                if (i + k < N && j - 1 >= 0)
                    tong_phu -= sumAnti[i + k][j - 1];

                if (tong_chinh - tong_phu > maxValue)
                    maxValue = tong_chinh - tong_phu;
            }
        }
    }

    cout << maxValue;
    return 0;
}
  • Time Complexity: O(N^3)
  • Space Complexity: O(N^2)

Đây là cách tiếp cận tối ưu nhất được trình bày trong các solutions. Bằng cách precompute (tiền tính) tổng hậu tố của các đường chéo:

  1. sumMain[i][j] = tổng từ (i,j) đến (N-1, N-1) theo đường chéo chính.
  2. sumAnti[i][j] = tổng từ (i,j) đến (N-1, 0) theo đường chéo phụ.

Với mỗi ma trận con k x k tại (i, j):

  • Tổng chéo chính (từ (i,j) đến (i+k-1, j+k-1)): Lấy sumMain[i][j] - sumMain[i+k][j+k].
  • Tổng chéo phụ (từ (i, j+k-1) đến (i+k-1, j)): Lấy sumAnti[i][j+k-1] - sumAnti[i+k][j-1] (cần kiểm tra biên).

Vòng lặp i, j, k duyệt qua tất cả các ma trận con vuông, mỗi lần tính O(1). Tổng thời gian O(N^3). Với N=400, N^3 = 64,000,000, chạy được trong C++. Space O(N^2).

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

Cách tiếp cận Time Space Tên
1 O(N^5) - Quá chậm, N <= 400 là không khả thi O(N^2) - Lưu trữ ma trận đầu vào Brute Force (Duyệt tất cả ma trận con)
2 O(N^3) O(N^2) Prefix Sum (Tiền tố sum) theo đường chéo
3 O(N^3) O(N^2) Tối ưu O(N^3) với biến phụ

Bài học kinh nghiệm

  • Giá trị ma trận con là hiệu giữa tổng chéo chính và chéo phụ.
  • Cần precompute các tổng đường chéo để truy vấn O(1) cho mỗi ma trận con.
  • Sử dụng suffix sum (tổng hậu tố) cho các đường chéo giúp tính tổng của đoạn bất kỳ trên đường chéo dễ dàng.

Lỗi thường gặp

  • Quên kiểm tra biên khi tính tổng chéo phụ (ví dụ: chạm đáy hoặc sang trái).
  • Sử dụng sai hướng của đường chéo phụ (phải là từ trên phải xuống dưới trái).
  • Nhiễu loạn giữa prefix sum và suffix sum dẫn đến công thức tính tổng sai.

Bình luận

Please read the guidelines before commenting.

Không có bình luận tại thời điểm này.