Problem Set Overview

This article presents solutions to five algorithmic problems from Meituan's 2024 Spring campus recruitment online assessment for software engineering positions. Each problem requires specific algorithmic techniques ranging from prefix sum optimization to union-find data structures.

Problem 1: Balanced Submatrix Count

Problem Description Given an n×n binary matrix, count the number of square submatrices where exactly half of the cells contain the value 1. Output results for all even-sized squares.

Solution Approach This problem leverages a 2D prefix sum to efficiently count 1s in any rectangular region. After preprocessing the prefix sum array in O(n²), we iterate through all possible square sizes. For each size, we check every valid position using O(1) range queries, achieving an overall complexity of O(n³).

Implementation

#include <bits/stdc++.h>

int main() {
    int n;
    std::cin >> n;

    std::vector<std::string> grid(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> grid[i];
    }

    std::vector<std::vector<int>> prefix(n + 1, std::vector<int>(n + 1, 0));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            prefix[i + 1][j + 1] = prefix[i + 1][j] + prefix[i][j + 1] - prefix[i][j];
            prefix[i + 1][j + 1] += (grid[i][j] == '1') ? 1 : 0;
        }
    }

    auto query = [&](int top, int left, int bottom, int right) -> int {
        return prefix[bottom][right] - prefix[top - 1][right] 
             - prefix[bottom][left - 1] + prefix[top - 1][left - 1];
    };

    auto evaluate = [&](int side) -> int {
        int count = 0;
        for (int row = 1; row <= n; ++row) {
            for (int col = 1; col <= n; ++col) {
                if (row + side - 1 <= n && col + side - 1 <= n) {
                    int ones = query(row, col, row + side - 1, col + side - 1);
                    if (ones == (side * side) / 2) {
                        ++count;
                    }
                }
            }
        }
        return count;
    };

    for (int side = 1; side <= n; ++side) {
        if (side % 2 == 1) {
            std::cout << 0 << "\n";
        } else {
            std::cout << evaluate(side) << "\n";
        }
    }
    return 0;
}

Problem 2: Array Range Query

Problem Description Given an array with n integers and m queries. Each query provides indices l and r. For each query, output the sum of all elements from 1 to l and from 1 to r respectively.

Solution Approach Simply compute the total sum of the array and count zero elements. For each query, the result is the total sum plus the count of zeros multiplied by the query index. This runs in O(n + m) time.

Implementation

#include <bits/stdc++.h>

using i64 = long long;

int main() {
    int n, q;
    std::cin >> n >> q;

    i64 total = 0;
    i64 zeroCount = 0;
    
    for (int i = 0; i < n; ++i) {
        int val;
        std::cin >> val;
        total += val;
        zeroCount += (val == 0) ? 1 : 0;
    }

    while (q--) {
        int l, r;
        std::cin >> l >> r;
        std::cout << (total + l * zeroCount) << " " 
                  << (total + r * zeroCount) << "\n";
    }
    return 0;
}

Problem 3: Character Frequency Count

Problem Description Given a string of length n, count how many positions contain either 'M' or 'T', with the additional constraint that you can skip exactly one character during the count.

Solution Approach A straightforward iteration through the string. Maintain a counter for allowed skips and increment the answer whenever encountering 'M' or 'T', or when skips remain available.

Implementation

#include <bits/stdc++.h>

using i64 = long long;

int main() {
    int n, skip;
    std::cin >> n >> skip;

    std::string str;
    std::cin >> str;

    int result = 0;
    for (int i = 0; i < n; ++i) {
        if (str[i] == 'M' || str[i] == 'T' || skip-- > 0) {
            ++result;
        }
    }

    std::cout << result << "\n";
    return 0;
}

Problem 4: Friend Connectivity

Problem Descripsion There are n users with m undirected edges representing friendships. Initially all edges exist, but q operations are performed: type 1 deletes an edge, and type 2 queries whether two users are in the same connected component. Process these operations efficiently.

Solution Approach Instead of simulating edge deletions (which is complex), process operations in reverse. Initially, only edges that are never deleted are added to the union-find structure. Then process queries backward: type 2 queries become connectivity checks, while type 1 operations (which were deletions forward) become edge additions when processing backward. The key insight is that an edge should only be added back when processing its last deletion operation.

Since node values can be up to 10⁹, coordinate comprestion is necessary. Time complexity: O((m + q) log m α(n)).

Implementation

#include <bits/stdc++.h>

using i64 = long long;

struct DSU {
    std::vector<int> parent;
    DSU(int size) : parent(size) {
        std::iota(parent.begin(), parent.end(), 0);
    }
    
    int find(int x) {
        return parent[x] == x ? x : parent[x] = find(parent[x]);
    }
    
    void unite(int a, int b) {
        a = find(a);
        b = find(b);
        if (a != b) parent[a] = b;
    }
};

int main() {
    int n, m, q;
    std::cin >> n >> m >> q;

    DSU dsu(m);
    std::map<std::array<int, 2>, int> edgeStatus;
    std::map<int, int> coordMap;
    int coordCount = 0;

    for (int i = 0; i < m; ++i) {
        int u, v;
        std::cin >> u >> v;
        if (u > v) std::swap(u, v);
        edgeStatus[{u, v}]++;
        if (!coordMap.count(u)) coordMap[u] = coordCount++;
        if (!coordMap.count(v)) coordMap[v] = coordCount++;
    }

    struct Operation { int type, x, y; };
    std::vector<Operation> queries(q);
    for (int i = 0; i < q; ++i) {
        std::cin >> queries[i].type >> queries[i].x >> queries[i].y;
        if (queries[i].type == 1) {
            int x = queries[i].x, y = queries[i].y;
            if (x > y) std::swap(x, y);
            if (coordMap.count(x) && coordMap.count(y)) {
                edgeStatus[{x, y}]--;
            }
        }
    }

    for (auto& [edge, cnt] : edgeStatus) {
        if (cnt > 0) {
            int u = dsu.find(coordMap[edge[0]]);
            int v = dsu.find(coordMap[edge[1]]);
            dsu.parent[u] = v;
        }
    }

    std::vector<bool> answer(q);
    for (int i = q - 1; i >= 0; --i) {
        int type = queries[i].type;
        int x = queries[i].x;
        int y = queries[i].y;
        
        if (!coordMap.count(x) || !coordMap.count(y)) continue;
        
        if (type == 2) {
            answer[i] = dsu.find(coordMap[x]) == dsu.find(coordMap[y]);
        } else {
            if (x > y) std::swap(x, y);
            if (edgeStatus.count({x, y})) {
                edgeStatus[{x, y}]++;
                if (edgeStatus[{x, y}] > 0) {
                    int u = dsu.find(coordMap[x]);
                    int v = dsu.find(coordMap[y]);
                    dsu.parent[u] = v;
                }
            }
        }
    }

    for (int i = 0; i < q; ++i) {
        if (queries[i].type == 2) {
            std::cout << (answer[i] ? "Yes" : "No") << "\n";
        }
    }
    return 0;
}

Problem 5: Interval Removal for Valid Sequence

Problem Description Given an array of n integers and an integer k, find the total count of valid intervals [l, r] such that after removing this interval, the remaining array's trailing zeros (minimum of total factors 2 and 5) is at least k.

Solution Approach The number of trailing zeros in a product equals min(total powers of 2, total powers of 5). Precompute prefix and suffix arrays storing cumulative counts of factors 2 and 5. For each starting position l, binary search the maximum r such that removing [l, r] satisfies the condition. All intervals starting at l with ending position ≤ r are valid.

Implementation

#include <bits/stdc++.h>

using i64 = long long;

int main() {
    int n, k;
    std::cin >> n >> k;

    std::vector<int> arr(n);
    std::vector<std::array<int, 2>> prefix(n + 1, {0, 0});
    std::vector<std::array<int, 2>> suffix(n + 2, {0, 0});

    for (int i = 0; i < n; ++i) {
        std::cin >> arr[i];
        prefix[i + 1] = prefix[i];
        int val = arr[i];
        while (val % 2 == 0) {
            val /= 2;
            prefix[i + 1][0]++;
        }
        while (val % 5 == 0) {
            val /= 5;
            prefix[i + 1][1]++;
        }
    }

    for (int i = n - 1; i >= 0; --i) {
        suffix[i] = suffix[i + 1];
        int val = arr[i];
        while (val % 2 == 0) {
            val /= 2;
            suffix[i][0]++;
        }
        while (val % 5 == 0) {
            val /= 5;
            suffix[i][1]++;
        }
    }

    i64 result = 0;
    for (int start = 1; start <= n; ++start) {
        int left = start - 1;
        int right = n;
        
        while (left < right) {
            int mid = (left + right + 1) / 2;
            std::array<int, 2> factors = {0, 0};
            
            if (start > 1) {
                factors = prefix[start - 1];
            }
            if (mid < n) {
                factors[0] += suffix[mid + 1][0];
                factors[1] += suffix[mid + 1][1];
            }
            
            if (std::min(factors[0], factors[1]) >= k) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        
        if (left >= start) {
            result += (left - start + 1);
        }
    }

    std::cout << result << "\n";
    return 0;
}

Summary

These five problems cover essential algorithmic techniques commonly tested in technical interviews: prefix sum optimization, binary search with prefix-suffix preprocessing, union-find with offline processing, and careful handling of edge cases in data structure operations. Efficient implementation with proper time complexity analysis is crucial for passing online assessment time limits.