Problem 1: Counting Isosceles Triangles (Easy Variant)

Description

Given a grid containing characters, determine the total number of isosceles triangles that can be formed by connected asterisk (*) symbols.

Solution Strategy

Iterate through every cell that contains an asterisk, treating it as the potential apex of a triangle. Expand vertically downwards. At each subsequent level, use a precomputed row prefix sum array to instantly verify whether the horizontal segment representing the base consists entirely of asterisks. If both the diagonal legs and the horizontal base are valid, increment the counter.

Implementation

#include <iostream>
#include <vector>
using namespace std;

using ll = long long;

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

    ll grid_rows, grid_cols;
    if (!(cin >> grid_rows >> grid_cols)) return 0;

    vector<string> matrix(grid_rows);
    vector<vector<int>> cell_value(grid_rows, vector<int>(grid_cols, 0));

    // Read input and map asterisks to 1
    for (ll i = 0; i < grid_rows; ++i) {
        cin >> matrix[i];
        for (ll j = 0; j < grid_cols; ++j) {
            if (matrix[i][j] == '*') cell_value[i][j] = 1;
        }
    }

    // Compute horizontal prefix sums
    vector<vector<int>> row_prefix_sum(grid_rows, vector<int>(grid_cols, 0));
    for (ll i = 0; i < grid_rows; ++i) {
        for (ll j = 0; j < grid_cols; ++j) {
            row_prefix_sum[i][j] = cell_value[i][j] + (j > 0 ? row_prefix_sum[i][j - 1] : 0);
        }
    }

    ll triangle_count = 0;
    // Iterate through potential apexes
    for (ll apex_row = 0; apex_row < grid_rows; ++apex_row) {
        for (ll apex_col = 0; apex_col < grid_cols; ++apex_col) {
            if (matrix[apex_row][apex_col] != '*') continue;

            ll bottom_row = apex_row + 1;
            ll left_col = apex_col - 1;
            ll right_col = apex_col + 1;

            // Expand downwards while staying within bounds and maintaining leg continuity
            while (bottom_row < grid_rows && left_col >= 0 && right_col < grid_cols) {
                if (matrix[bottom_row][left_col] != '*' || matrix[bottom_row][right_col] != '*') break;

                // Check if the base is solid using prefix sums
                int base_ones = row_prefix_sum[bottom_row][right_col] - (left_col > 0 ? row_prefix_sum[bottom_row][left_col - 1] : 0);
                int required_len = right_col - left_col;
                if (base_ones == required_len) triangle_count++;

                bottom_row++;
                left_col--;
                right_col++;
            }
        }
    }

    cout << triangle_count << "\n";
    return 0;
}

Problem 2: Counting Isosceles Triangles (Hard Variant)

Description

This is the extended version of the previous problem. The grid dimensions now scale up to $3000 \times 3000$, necessitating an optimized time complexity approach.

Solution Strategy

A valid isosceles triangle is uniquely determined by its apex and the midpoint of its base, which must share the same column index. We process the grid column by column. Within each column, we iterate from the bottom row upwards. To efficiently count valid bases, we employ a Binary Indexed Tree (Fenwick Tree). We also precompute four auxiliary arrays for every cell:

1. max_leg_down_left: Maximum possible length of the left leg extending daigonally down-left.
2. max_leg_down_right: Maximum possible length of the right leg extending diagonally down-right.
3. consecutive_left: Number of consecutive asterisks to the left (inclusive) in the current row.
4. consecutive_right: Number of consecutive asterisks to the right (inclusive) in the current row. As we traverse upwards, the current row can act as either a apex or a base midpoint. We use the BIT to sum valid base contributions within the allowable height determined by the minimum of the left and right leg lengths. A deferred deletion mechanism ensures that base contributions are removed once they exceed the maximum viable distence for higher apexes.

Implementation

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

using ll = int; // Using int to prevent Memory Limit Exceeded on large inputs

const int MAX_DIM = 3005;
char grid[MAX_DIM][MAX_DIM];
ll max_leg_down_left[MAX_DIM][MAX_DIM];
ll max_leg_down_right[MAX_DIM][MAX_DIM];
ll consec_left[MAX_DIM][MAX_DIM];
ll consec_right[MAX_DIM][MAX_DIM];

// Fenwick Tree structure
struct FenwickTree {
    vector<ll> tree;
    int size;
    FenwickTree(int n) : size(n), tree(n + 1, 0) {}
    void update(int idx, ll delta) {
        for (; idx <= size; idx += idx & -idx) tree[idx] += delta;
    }
    ll query(int idx) {
        ll sum = 0;
        for (; idx > 0; idx -= idx & -idx) sum += tree[idx];
        return sum;
    }
};

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

    int n, m;
    if (!(cin >> n >> m)) return 0;

    for (int i = 1; i <= n; ++i) {
        string row;
        cin >> row;
        for (int j = 1; j <= m; ++j) {
            grid[i][j] = row[j - 1];
        }
    }

    // Precompute consecutive horizontal asterisks
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            consec_left[i][j] = (grid[i][j] == '*') ? consec_left[i][j - 1] + 1 : 0;
        }
        for (int j = m; j >= 1; --j) {
            consec_right[i][j] = (grid[i][j] == '*') ? consec_right[i][j + 1] + 1 : 0;
        }
    }

    // Precompute maximum diagonal leg lengths from bottom-up
    for (int i = n; i >= 1; --i) {
        for (int j = 1; j <= m; ++j) {
            if (grid[i][j] == '*') {
                max_leg_down_left[i][j] = max_leg_down_left[i + 1][j - 1] + 1;
                max_leg_down_right[i][j] = max_leg_down_right[i + 1][j + 1] + 1;
            } else {
                max_leg_down_left[i][j] = 0;
                max_leg_down_right[i][j] = 0;
            }
        }
    }

    long long total_triangles = 0;

    // Process each column independently
    for (int col = 1; col <= m; ++col) {
        FenwickTree bit(n);
        vector<vector<ll>> removal_schedule(n + 1);

        for (int row = n; row >= 1; --row) {
            if (grid[row][col] == '.') {
                for (ll target_row : removal_schedule[row]) {
                    bit.update(target_row, -1);
                }
                continue;
            }

            // Current cell acts as an apex
            ll min_height = min(max_leg_down_left[row][col], max_leg_down_right[row][col]);
            ll max_valid_base = row + min_height - 1;
            total_triangles += bit.query(max_valid_base) - bit.query(row);

            // Register current row as a potential base midpoint for higher rows
            bit.update(row, 1);

            // Calculate the highest row that can use 'row' as a base midpoint
            ll max_height_for_apex = min(consec_left[row][col], consec_right[row][col]);
            ll highest_apex_row = row - max_height_for_apex + 1;
            highest_apex_row = max(1LL, highest_apex_row);

            removal_schedule[highest_apex_row].push_back(row);

            // Execute removals for the current level
            for (ll target_row : removal_schedule[row]) {
                bit.update(target_row, -1);
            }
        }
    }

    cout << total_triangles << "\n";
    return 0;
}

Problem 3: Optimized Number Selection via Interval Dynamic Programming

Description

Select a subset of numbers from a given sequence following specific operational constraints to achieve the highest possible final score.

Solution Strategy

The problem is solved using Interval Dynamic Programming. Because the allowed operations include both subtractionn and multiplication, the sign of intermediate results can flip (e.g., multiplying two negative numbers yields a positive). Consequently, the DP state must track both the maximum and minimum achievable values for selecting exactly $k$ elements within any subarray range $[i, j]$. After populating the DP tables for all sub-intervals, we perform a secondary pass to merge disjoint intervals and determine the global maximum score.

Implmeentation

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

using ll = long long;
const ll INF = 1e18;

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

    int sequence_len;
    if (!(cin >> sequence_len)) return 0;

    vector<ll> values(sequence_len + 1);
    for (int i = 1; i <= sequence_len; ++i) cin >> values[i];

    // dp_min[i][j][k] and dp_max[i][j][k] store the min/max value
    // for the subarray from i to j when exactly k numbers are selected.
    vector<vector<vector<ll>>> dp_min(sequence_len + 1, vector<vector<ll>>(sequence_len + 1, vector<ll>(7, INF)));
    vector<vector<vector<ll>>> dp_max(sequence_len + 1, vector<vector<ll>>(sequence_len + 1, vector<ll>(7, -INF)));

    // Initialize base cases and run interval DP
    for (int right = 1; right <= sequence_len; ++right) {
        for (int left = right; left >= 1; --left) {
            ll current_val = values[right];
            
            // k = 1
            dp_max[left][right][1] = max(current_val, left < right ? dp_max[left][right - 1][1] : -INF);
            dp_min[left][right][1] = min(current_val, left < right ? dp_min[left][right - 1][1] : INF);
            if (left == right) {
                dp_max[left][right][1] = current_val;
                dp_min[left][right][1] = current_val;
            }

            int segment_len = right - left + 1;
            if (segment_len >= 2) {
                // k = 2 (Subtraction)
                dp_max[left][right][2] = max(dp_max[left][right - 1][2], dp_max[left][right - 1][1] - current_val);
                dp_min[left][right][2] = min(dp_min[left][right - 1][2], dp_min[left][right - 1][1] - current_val);
            }
            if (segment_len >= 3) {
                // k = 3 (Multiplication)
                dp_max[left][right][3] = max({dp_max[left][right - 1][3],
                                              dp_max[left][right - 1][2] * current_val,
                                              dp_min[left][right - 1][2] * current_val});
                dp_min[left][right][3] = min({dp_min[left][right - 1][3],
                                              dp_min[left][right - 1][2] * current_val,
                                              dp_max[left][right - 1][2] * current_val});
            }
            if (segment_len >= 4) {
                // k = 4 (Subtraction)
                dp_max[left][right][4] = max(dp_max[left][right - 1][4], dp_max[left][right - 1][3] - current_val);
                dp_min[left][right][4] = min(dp_min[left][right - 1][4], dp_min[left][right - 1][3] - current_val);
            }
            if (segment_len >= 5) {
                // k = 5 (Multiplication)
                dp_max[left][right][5] = max({dp_max[left][right - 1][5],
                                              dp_max[left][right - 1][4] * current_val,
                                              dp_min[left][right - 1][4] * current_val});
                dp_min[left][right][5] = min({dp_min[left][right - 1][5],
                                              dp_min[left][right - 1][4] * current_val,
                                              dp_max[left][right - 1][4] * current_val});
            }
            if (segment_len >= 6) {
                // k = 6 (Subtraction)
                dp_max[left][right][6] = max(dp_max[left][right - 1][6], dp_max[left][right - 1][5] - current_val);
                dp_min[left][right][6] = min(dp_min[left][right - 1][6], dp_min[left][right - 1][5] - current_val);
            }
        }
    }

    // Merge intervals to find the absolute maximum score
    vector<ll> global_best(sequence_len + 1, 0);
    for (int i = 1; i <= sequence_len; ++i) {
        for (int j = 0; j < i; ++j) {
            if (i - j >= 6) {
                global_best[i] = max(global_best[i], global_best[j] + dp_max[j + 1][i][6]);
            } else {
                global_best[i] = max(global_best[i], global_best[j]);
            }
        }
    }

    cout << global_best[sequence_len] << "\n";
    return 0;
}