Test Case Pass: 849/849

blog_gemini_2.5_pro_coding_leetcode_question_response.cpp

#include <vector>
#include <iostream>
#include <algorithm>
#include <climits> // For LLONG_MIN, LLONG_MAX
#include <cmath>   // For log2 (can be replaced with custom log table)
#include <set>     // For storing unique candidate cells efficiently
#include <vector>  // Explicit include for vector

using namespace std;

// 2D Range Maximum Query (RMQ) class using Sparse Table logic.
// Supports O(1) query time after O(M*N*logM*logN) precomputation.
class RMQ2D {
    // st[k][l][i][j] stores the maximum value in the rectangle starting at (i, j)
    // with dimensions (1<<k) x (1<<l). Uses long long for values.
    vector<vector<vector<vector<long long>>>> st;
    // Precomputed floor(log2(x)) values for efficient calculation of k and l in query.
    vector<int> log_table; 
    int M, N; // Dimensions of the board

public:
    // Constructor: Precomputes the sparse table.
    RMQ2D(const vector<vector<int>>& board) {
        M = board.size();
        N = board[0].size();

        // Constraints M, N >= 3 guarantee M, N > 0.

        // Precompute base-2 logarithms up to max(M, N).
        log_table.resize(max(M, N) + 1);
        log_table[0] = -1; // log2(0) is undefined, mark as invalid.
        log_table[1] = 0;  // log2(1) = 0.
        for (int i = 2; i <= max(M, N); ++i) {
            // Efficient computation: floor(log2(i)) = floor(log2(i/2)) + 1
            log_table[i] = log_table[i / 2] + 1; 
        }

        // Maximum powers of 2 needed for dimensions M and N.
        int kM = log_table[M]; // floor(log2(M))
        int kN = log_table[N]; // floor(log2(N))
        
        // Initialize the sparse table structure. Dimensions need +1 for powers 0..kM/kN.
        st.resize(kM + 1, vector<vector<vector<long long>>>(kN + 1, vector<vector<long long>>(M, vector<long long>(N))));

        // Fill the base layer st[0][0] with board values cast to long long.
        for (int i = 0; i < M; ++i) {
            for (int j = 0; j < N; ++j) {
                st[0][0][i][j] = (long long)board[i][j];
            }
        }

        // Fill st[k][0] for k > 0 (extending vertically, ranges of size (1<<k) x 1).
        for (int k = 1; k <= kM; ++k) {
             // Optimization: Check if current power of 2 exceeds board dimension.
             if (M < (1 << k)) break; 
            // Iterate up to the last possible starting row index.
            for (int i = 0; i <= M - (1 << k); ++i) {
                for (int j = 0; j < N; ++j) {
                    // Max of two vertically adjacent sub-rectangles of size (1<<(k-1)) x 1.
                    st[k][0][i][j] = max(st[k - 1][0][i][j], st[k - 1][0][i + (1 << (k - 1))][j]);
                }
            }
        }

        // Fill st[k][l] for l > 0 (extending horizontally, ranges of size (1<<k) x (1<<l)).
        for (int k = 0; k <= kM; ++k) {
             // Optimization: Skip if power k exceeds M.
             if (M < (1 << k)) continue; // Need continue to allow smaller k with larger l.
            for (int l = 1; l <= kN; ++l) {
                 // Optimization: Break inner loop if power l exceeds N.
                 if (N < (1 << l)) break; 
                 // Iterate up to last possible starting row and column indices.
                 for (int i = 0; i <= M - (1 << k); ++i) {
                    for (int j = 0; j <= N - (1 << l); ++j) {
                         // Max of two horizontally adjacent sub-rectangles of size (1<<k) x (1<<(l-1)).
                        st[k][l][i][j] = max(st[k][l - 1][i][j], st[k][l - 1][i][j + (1 << (l - 1))]);
                    }
                }
            }
        }
    }

    // Query: Returns the maximum value in the rectangle defined by top-left (r1, c1)
    // and bottom-right (r2, c2), inclusive. O(1) time complexity.
    long long query(int r1, int c1, int r2, int c2) {
        // Basic validation: Check if the range is logically valid or outside board bounds.
        if (r1 > r2 || c1 > c2 || r1 >= M || r2 < 0 || c1 >= N || c2 < 0) {
           return LLONG_MIN; // Return smallest possible long long for invalid/empty range.
        }
        // Clamp coordinates to be within the board dimensions [0, M-1] x [0, N-1].
        r1 = max(0, r1);
        r2 = min(M - 1, r2);
        c1 = max(0, c1);
        c2 = min(N - 1, c2);
        // After clamping, re-check if the range is still valid (non-empty).
        if (r1 > r2 || c1 > c2) {
            return LLONG_MIN;
        }
       
        // Calculate the largest power of 2 less than or equal to the dimensions (height, width).
        int k = log_table[r2 - r1 + 1]; // k = floor(log2(height))
        int l = log_table[c2 - c1 + 1]; // l = floor(log2(width))
        
        // The query range is covered by four overlapping rectangles of size (1<<k) x (1<<l).
        // Find the maximum value in each of these four rectangles.
        long long max1 = st[k][l][r1][c1]; // Top-left corner starts this block
        long long max2 = st[k][l][r2 - (1 << k) + 1][c1]; // Bottom-left corner starts this block
        long long max3 = st[k][l][r1][c2 - (1 << l) + 1]; // Top-right corner starts this block
        long long max4 = st[k][l][r2 - (1 << k) + 1][c2 - (1 << l) + 1]; // Bottom-right corner starts this block
        
        // The maximum value in the query rectangle is the maximum of these four values.
        return max({max1, max2, max3, max4});
    }
};


class Solution {
    // Helper function to find the maximum value on the board excluding two specified rows (r1, r2)
    // and two specified columns (c1, c2). Uses the precomputed RMQ structure.
    long long find_max_val_excluding_two(int r1, int c1, int r2, int c2, RMQ2D& rmq, int M, int N) {
        // Ensure r1 <= r2 and c1 <= c2 to simplify region definitions.
        if (r1 > r2) swap(r1, r2);
        if (c1 > c2) swap(c1, c2);

        long long max_val = LLONG_MIN; // Initialize max value found to smallest possible.

        // The board is divided into 9 rectangular regions by the excluded rows and columns.
        // Query the maximum value in each of these 9 regions.
        
        // Top band (rows 0 to r1-1)
        max_val = max(max_val, rmq.query(0, 0, r1 - 1, c1 - 1));           // Top-left region
        max_val = max(max_val, rmq.query(0, c1 + 1, r1 - 1, c2 - 1));       // Top-middle region
        max_val = max(max_val, rmq.query(0, c2 + 1, r1 - 1, N - 1));       // Top-right region
        
        // Middle band (rows r1+1 to r2-1)
        max_val = max(max_val, rmq.query(r1 + 1, 0, r2 - 1, c1 - 1));       // Middle-left region
        max_val = max(max_val, rmq.query(r1 + 1, c1 + 1, r2 - 1, c2 - 1)); // Middle-middle region
        max_val = max(max_val, rmq.query(r1 + 1, c2 + 1, r2 - 1, N - 1)); // Middle-right region

        // Bottom band (rows r2+1 to M-1)
        max_val = max(max_val, rmq.query(r2 + 1, 0, M - 1, c1 - 1));       // Bottom-left region
        max_val = max(max_val, rmq.query(r2 + 1, c1 + 1, M - 1, c2 - 1)); // Bottom-middle region
        max_val = max(max_val, rmq.query(r2 + 1, c2 + 1, M - 1, N - 1));   // Bottom-right region

        // Return the overall maximum found across the 9 regions.
        return max_val;
    }

public:
    // Main function to find the maximum sum of values for three non-attacking rooks.
    long long maximumValueSum(vector<vector<int>>& board) {
        int M = board.size();
        int N = board[0].size();

        // Step 1: Precompute the RMQ structure for O(1) max queries later.
        RMQ2D rmq(board);

        // Step 2: Identify a set of candidate cells (positions) likely to be part of the optimal solution.
        // Heuristic: Consider cells that are among the top X values in their respective row or column.
        set<pair<int, int>> candidate_cells_set; // Use a set to automatically handle duplicates.
        const int X = 3; // Consider top 3 values. Increasing X improves accuracy but increases K.

        // Find Top X candidates per row.
        for (int r = 0; r < M; ++r) {
            vector<pair<long long, int>> row_vals; // Store (value, column_index) pairs.
            for (int c = 0; c < N; ++c) {
                row_vals.push_back({(long long)board[r][c], c});
            }
            // Find the top X elements in this row using partial_sort (efficient).
             int count = min((int)row_vals.size(), X);
             // partial_sort places the 'count' largest elements (based on value) at the beginning.
             partial_sort(row_vals.begin(), row_vals.begin() + count, row_vals.end(), greater<pair<long long, int>>());
             // Add the positions ({r, c}) of these top X candidates to the set.
             for (int i = 0; i < count; ++i) {
                 candidate_cells_set.insert({r, row_vals[i].second});
             }
        }

        // Find Top X candidates per column.
        for (int c = 0; c < N; ++c) {
            vector<pair<long long, int>> col_vals; // Store (value, row_index) pairs.
            for (int r = 0; r < M; ++r) {
                col_vals.push_back({(long long)board[r][c], r});
            }
            // Find the top X elements in this column.
             int count = min((int)col_vals.size(), X);
             partial_sort(col_vals.begin(), col_vals.begin() + count, col_vals.end(), greater<pair<long long, int>>());
             // Add the positions ({r, c}) of these top X candidates to the set.
             for (int i = 0; i < count; ++i) {
                 candidate_cells_set.insert({col_vals[i].second, c});
             }
        }

        // Convert the set of unique candidate cells into a vector for easier indexed access.
        vector<pair<int, int>> S(candidate_cells_set.begin(), candidate_cells_set.end());
        int K = S.size(); // K is the total number of unique candidate cells. K <= X*M + X*N.

        // Initialize the maximum sum found so far to the smallest possible value.
        long long max_total_sum = LLONG_MIN;

        // Step 3: Check combinations involving candidate cells.

        // Phase 1: O(K^3) complexity check.
        // Iterate through all unique triplets of cells from the candidate set S.
        // Check if they form a non-attacking configuration.
        if (K >= 3) { // Need at least 3 candidates to form a triplet.
             for (int i = 0; i < K; ++i) {
                for (int j = i + 1; j < K; ++j) {
                    for (int k = j + 1; k < K; ++k) {
                        // Get the positions (row, col) of the three candidate cells.
                        int r1 = S[i].first, c1 = S[i].second;
                        int r2 = S[j].first, c2 = S[j].second;
                        int r3 = S[k].first, c3 = S[k].second;

                        // Check if the rows are distinct AND the columns are distinct (non-attacking).
                        if (r1 != r2 && r1 != r3 && r2 != r3 &&
                            c1 != c2 && c1 != c3 && c2 != c3) {
                            
                            // Calculate the sum of values for this valid configuration. Use long long.
                            long long current_sum = (long long)board[r1][c1] + (long long)board[r2][c2] + (long long)board[r3][c3];
                            // Update the overall maximum sum if this configuration is better.
                            max_total_sum = max(max_total_sum, current_sum);
                        }
                    }
                }
            }
        }

        // Phase 2: O(K^2) complexity check.
        // Iterate through all unique pairs of cells from the candidate set S.
        // For each non-attacking pair, find the best possible third rook anywhere on the board.
       if (K >= 2) { // Need at least 2 candidates to form a pair.
            for (int i = 0; i < K; ++i) {
                for (int j = i + 1; j < K; ++j) {
                    // Get the positions of the two candidate cells.
                    int r1 = S[i].first, c1 = S[i].second;
                    int r2 = S[j].first, c2 = S[j].second;

                    // Check if the pair is non-attacking (distinct row and distinct column).
                    if (r1 != r2 && c1 != c2) {
                        // Find the maximum value for a third rook, placed anywhere on the board
                        // such that it doesn't attack the first two rooks (i.e., excluding rows r1, r2 and columns c1, c2).
                        long long max3 = find_max_val_excluding_two(r1, c1, r2, c2, rmq, M, N);

                        // If a valid position for the third rook exists (max3 != LLONG_MIN),
                        // calculate the total sum for this configuration.
                        if (max3 != LLONG_MIN) {
                             // Calculate sum using long long.
                             long long current_sum = (long long)board[r1][c1] + (long long)board[r2][c2] + max3;
                             // Update the overall maximum sum.
                             max_total_sum = max(max_total_sum, current_sum);
                        }
                        // Note: If max3 is LLONG_MIN, it means no valid third position exists, or all valid positions
                        // have value LLONG_MIN. The sum involving LLONG_MIN will likely not update max_total_sum.
                    }
                }
            }
        }

        // Step 4: Return the result.
        // The heuristic approach (checking K^3 and K^2 combinations) is expected to find the maximum sum.
        // If max_total_sum remains LLONG_MIN, it implies either K was too small (unlikely for M,N>=3)
        // or the heuristic missed the optimal solution, or all possible sums are LLONG_MIN.
        // Returning 0 in this edge case is a common fallback in competitive programming.
        return (max_total_sum == LLONG_MIN) ? 0 : max_total_sum;
    }
};

Problem Link: https://leetcode.com/problems/maximum-value-sum-by-placing-three-rooks-i