Grid Pattern Filling Algorithm

Problem Statement

Given an n×n grid containing '.' and '#' characters, determine if all '.' positions can be filled with cross-shaped patterns.

Solution Approach

Iterate through each cell and identify positions where cross patterns can be placed without overlapping.

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

int main() {
    int gridSize;
    cin >> gridSize;
    
    vector<string> grid(gridSize);
    for (auto &row : grid) cin >> row;
    
    const int dx[] = {1, -1, 0, 0};
    const int dy[] = {0, 0, 1, -1};
    
    for (int row = 0; row < gridSize; row++) {
        for (int col = 0; col < gridSize; col++) {
            if (grid[row][col] == '.') {
                int validDirections = 0;
                for (int dir = 0; dir < 4; dir++) {
                    int newRow = row + dx[dir];
                    int newCol = col + dy[dir];
                    if (newRow >= 0 && newRow < gridSize && 
                        newCol >= 0 && newCol < gridSize && 
                        grid[newRow][newCol] == '.') {
                        validDirections++;
                    }
                }
                if (validDirections == 4) {
                    grid[row][col] = '#';
                    for (int dir = 0; dir < 4; dir++) {
                        int newRow = row + dx[dir];
                        int newCol = col + dy[dir];
                        grid[newRow][newCol] = '#';
                    }
                }
            }
        }
    }
    
    for (int row = 0; row < gridSize; row++)
        for (int col = 0; col < gridSize; col++)
            if (grid[row][col] == '.') {
                cout << "NO\n";
                return 0;
            }
    
    cout << "YES\n";
    return 0;
}

Matrix Construction for Bitwise Operations

Problem Statement

Construct a matrix where the difference between path bitwise AND value and DP-calculated value equals a given constant k.

Solution Approach

Create a 3×3 matrix with specific values to manipulate bitwise operations and achieve the desired difference.

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

int main() {
    int k;
    cin >> k;
    
    int matrix[3][3] = {};
    matrix[2][0] = matrix[2][1] = matrix[0][0] = 262143;
    matrix[0][1] = matrix[1][1] = matrix[2][2] = k;
    
    int bitLength = log2(k) + 1;
    matrix[1][0] = (1 << bitLength);
    
    cout << "3 3\n";
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            cout << matrix[i][j];
            if (j < 2) cout << " ";
        }
        cout << "\n";
    }
    return 0;
}

Interactive Grid Game Strategy

Problem Statement

Implement a winning strategy for an interactive grid game where players alternate placing colored tokens with adjacency constraints.

Solution Approach

Use a checkerboard pattern to place tokens and maintain separation between same-colored tokens.

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

int main() {
    int n;
    cin >> n;
    
    vector<vector<int>> board(n+1, vector<int>(n+1, 0));
    int color1Count = 0, color2Count = 0;
    
    auto makeMove = [&](int forbiddenColor) -> tuple<int, int, int> {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (board[i][j]) continue;
                if (color1Count != (n*n+1)/2 && color2Count != n*n/2) {
                    if ((i+j) % 2 == 0 && forbiddenColor != 1) {
                        board[i][j] = 1;
                        color1Count++;
                        return {1, i, j};
                    }
                    if ((i+j) % 2 == 1 && forbiddenColor != 2) {
                        board[i][j] = 2;
                        color2Count++;
                        return {2, i, j};
                    }
                } else {
                    if (color1Count == (n*n+1)/2) {
                        int chosenColor = (forbiddenColor == 1) ? 2 : (forbiddenColor ^ 1 ^ 2);
                        board[i][j] = chosenColor;
                        return {chosenColor, i, j};
                    } else {
                        int chosenColor = (forbiddenColor == 2) ? 1 : (forbiddenColor ^ 1 ^ 2);
                        board[i][j] = chosenColor;
                        return {chosenColor, i, j};
                    }
                }
            }
        }
        return {0, 0, 0};
    };
    
    for (int move = 1; move <= n*n; move++) {
        int forbidden;
        cin >> forbidden;
        auto [color, x, y] = makeMove(forbidden);
        cout << color << " " << x << " " << y << endl;
    }
    return 0;
}

String Transformation Optimization

Problem Statement

Find the lexicographically smallest string achievable through specific pairwise character swaps.

Solution Approach

Track character positions and perform optimal swaps while maintaining transformation constraints.

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

int main() {
    int length;
    cin >> length;
    
    string str;
    cin >> str;
    
    map<char, vector<int>> positionMap;
    for (int idx = 0; idx < length; idx++) {
        positionMap[str[idx]].push_back(idx);
    }
    
    int rightBound = length - 1;
    for (int left = 0; left < length; left++) {
        for (char ch = 'a'; ch < str[left]; ch++) {
            while (!positionMap[ch].empty() && positionMap[ch].back() > rightBound)
                positionMap[ch].pop_back();
            if (!positionMap[ch].empty() && positionMap[ch].back() > left) {
                swap(str[left], str[positionMap[ch].back()]);
                rightBound = positionMap[ch].back();
                positionMap[ch].pop_back();
                break;
            }
        }
    }
    
    cout << str << "\n";
    return 0;
}

Array Operations with Segment Tree

Problem Statement

Process three types of array operasions: bulk assignment, elemant addition, and value querying.

Solution Approach

Implement a segment tree with lazy propagation to efficiently handle range and point updates.

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

struct SegmentNode {
    long long left, right, sum, lazy;
};

class SegmentTree {
private:
    vector<SegmentNode> tree;
    vector<long long> data;
    
    void pushDown(int node) {
        if (tree[node].lazy != 0) {
            tree[node*2].sum = (tree[node*2].right - tree[node*2].left + 1) * tree[node].lazy;
            tree[node*2+1].sum = (tree[node*2+1].right - tree[node*2+1].left + 1) * tree[node].lazy;
            tree[node*2].lazy = tree[node].lazy;
            tree[node*2+1].lazy = tree[node].lazy;
            tree[node].lazy = 0;
        }
    }
    
    void buildTree(int node, int left, int right) {
        tree[node].left = left;
        tree[node].right = right;
        tree[node].lazy = 0;
        if (left == right) {
            tree[node].sum = data[left];
            return;
        }
        int mid = (left + right) / 2;
        buildTree(node*2, left, mid);
        buildTree(node*2+1, mid+1, right);
        tree[node].sum = tree[node*2].sum + tree[node*2+1].sum;
    }
    
public:
    SegmentTree(vector<long long>& arr) : data(arr) {
        tree.resize(4 * arr.size());
        buildTree(1, 0, arr.size()-1);
    }
    
    void rangeUpdate(int node, int left, int right, long long value) {
        if (tree[node].left >= left && tree[node].right <= right) {
            tree[node].sum = (tree[node].right - tree[node].left + 1) * value;
            tree[node].lazy = value;
            return;
        }
        pushDown(node);
        int mid = (tree[node].left + tree[node].right) / 2;
        if (left <= mid) rangeUpdate(node*2, left, right, value);
        if (right > mid) rangeUpdate(node*2+1, left, right, value);
        tree[node].sum = tree[node*2].sum + tree[node*2+1].sum;
    }
    
    void pointUpdate(int node, int position, long long value) {
        if (tree[node].left == tree[node].right) {
            tree[node].sum += value;
            return;
        }
        pushDown(node);
        int mid = (tree[node].left + tree[node].right) / 2;
        if (position <= mid) pointUpdate(node*2, position, value);
        else pointUpdate(node*2+1, position, value);
        tree[node].sum = tree[node*2].sum + tree[node*2+1].sum;
    }
    
    long long pointQuery(int node, int position) {
        if (tree[node].left == tree[node].right) {
            return tree[node].sum;
        }
        pushDown(node);
        int mid = (tree[node].left + tree[node].right) / 2;
        if (position <= mid) return pointQuery(node*2, position);
        else return pointQuery(node*2+1, position);
    }
};

int main() {
    int n;
    cin >> n;
    vector<long long> arr(n);
    for (int i = 0; i < n; i++) cin >> arr[i];
    
    SegmentTree st(arr);
    
    int queries;
    cin >> queries;
    while (queries--) {
        int type, index, value;
        cin >> type;
        if (type == 1) {
            cin >> value;
            st.rangeUpdate(1, 0, n-1, value);
        } else if (type == 2) {
            cin >> index >> value;
            st.pointUpdate(1, index-1, value);
        } else {
            cin >> index;
            cout << st.pointQuery(1, index-1) << "\n";
        }
    }
    return 0;
}

Subset Counting with Dynamic Programming

Problem Statement

Count the number of subsets where the maximum element value is at least the sum of all elements in the subset.

Solution Approach

Use dynamic programming to track achievable sums while processing elements in sorted order.

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

const int MOD = 998244353;

int main() {
    int n;
    cin >> n;
    
    vector<pair<int, int>> elements(n);
    for (int i = 0; i < n; i++) cin >> elements[i].first;
    for (int i = 0; i < n; i++) cin >> elements[i].second;
    
    sort(elements.begin(), elements.end());
    
    vector<long long> dp(5001, 0);
    dp[0] = 1;
    long long result = 0;
    
    for (int i = 0; i < n; i++) {
        for (int sum = elements[i].second; sum <= elements[i].first; sum++) {
            result = (result + dp[sum - elements[i].second]) % MOD;
        }
        for (int sum = 5000; sum >= elements[i].second; sum--) {
            dp[sum] = (dp[sum] + dp[sum - elements[i].second]) % MOD;
        }
    }
    
    cout << result << "\n";
    return 0;
}

Grid Connectivity Analysis

Problem Statement

Determine the minimum number of additional marks needed to ensure automatic marking propagates throughout the entire grid.

Solution Approach

Model the problem as a graph connectivity problem and use union-find to count connected components.

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

class UnionFind {
private:
    vector<int> parent;
public:
    UnionFind(int size) {
        parent.resize(size);
        iota(parent.begin(), parent.end(), 0);
    }
    
    int find(int x) {
        return parent[x] == x ? x : parent[x] = find(parent[x]);
    }
    
    void unite(int x, int y) {
        x = find(x);
        y = find(y);
        if (x != y) parent[x] = y;
    }
};

int main() {
    int rows, cols, marks;
    cin >> rows >> cols >> marks;
    
    UnionFind uf(rows + cols + 1);
    
    for (int i = 0; i < marks; i++) {
        int row, col;
        cin >> row >> col;
        uf.unite(row, col + rows);
    }
    
    int components = 0;
    for (int i = 1; i <= rows + cols; i++) {
        if (uf.find(i) == i) components++;
    }
    
    cout << components - 1 << "\n";
    return 0;
}

Tree Path Verification

Problem Statement

Verify if there exists a root-to-leaf path where all given nodes are within distance 1 from the path.

Solution Approach

Use DFS to compute tree properties and verify path constraints using parent nodes and subtree checks.

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

struct Tree {
    vector<vector<int>> adjacency;
    vector<int> discovery, parent, size, depth;
    int timer = 0;
    
    Tree(int n) : adjacency(n+1), discovery(n+1), parent(n+1), size(n+1), depth(n+1) {}
    
    void dfs(int node, int prev) {
        discovery[node] = ++timer;
        parent[node] = prev;
        depth[node] = depth[prev] + 1;
        size[node] = 1;
        for (int neighbor : adjacency[node]) {
            if (neighbor == prev) continue;
            dfs(neighbor, node);
            size[node] += size[neighbor];
        }
    }
};

int main() {
    int n, m;
    cin >> n >> m;
    
    Tree tree(n);
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        tree.adjacency[u].push_back(v);
        tree.adjacency[v].push_back(u);
    }
    
    tree.dfs(1, 1);
    
    while (m--) {
        int k;
        cin >> k;
        vector<int> nodes(k);
        for (int &node : nodes) {
            cin >> node;
            node = tree.parent[node];
        }
        
        sort(nodes.begin(), nodes.end(), [&](int x, int y) {
            return tree.depth[x] < tree.depth[y];
        });
        
        bool valid = true;
        for (int i = 1; i < k; i++) {
            int prev = nodes[i-1], curr = nodes[i];
            if (tree.discovery[prev] <= tree.discovery[curr] && 
                tree.discovery[curr] < tree.discovery[prev] + tree.size[prev]) {
                continue;
            }
            valid = false;
            break;
        }
        
        cout << (valid ? "YES" : "NO") << "\n";
    }
    return 0;
}

Optimal Path Planning with Resource Management

Problem Statement

Find the minimum time to reach the bottom-right corner of a grid with movement costs and resource collection.

Solution Approach

Use dynamic programming to track optimal paths considering resource accumulation and movement constraints.

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

int main() {
    int n;
    cin >> n;
    
    vector<vector<long long>> reward(n+1, vector<long long>(n+1));
    vector<vector<long long>> rightCost(n+1, vector<long long>(n+1, LLONG_MAX/2));
    vector<vector<long long>> downCost(n+1, vector<long long>(n+1, LLONG_MAX/2));
    
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            cin >> reward[i][j];
    
    for (int i = 1; i <= n; i++)
        for (int j = 1; j < n; j++)
            cin >> rightCost[i][j];
    
    for (int i = 1; i < n; i++)
        for (int j = 1; j <= n; j++)
            cin >> downCost[i][j];
    
    vector<vector<pair<long long, long long>>> dp(n+1, 
        vector<pair<long long, long long>>(n+1, {LLONG_MAX/2, 0}));
    
    dp[1][1] = {0, 0};
    
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            vector<vector<long long>> distance(n+1, vector<long long>(n+1, LLONG_MAX/2));
            distance[i][j] = 0;
            
            for (int r = i; r <= n; r++) {
                for (int c = j; c <= n; c++) {
                    if (r > 1) distance[r][c] = min(distance[r][c], distance[r-1][c] + downCost[r-1][c]);
                    if (c > 1) distance[r][c] = min(distance[r][c], distance[r][c-1] + rightCost[r][c-1]);
                }
            }
            
            for (int r = i; r <= n; r++) {
                for (int c = j; c <= n; c++) {
                    if (r != n && c != n && reward[r][c] < reward[i][j]) continue;
                    
                    auto [steps, resources] = dp[i][j];
                    long long cost = max(0LL, (distance[r][c] - resources + reward[i][j] - 1) / reward[i][j]);
                    long long newResources = resources + cost * reward[i][j] - distance[r][c];
                    long long newSteps = steps + cost + (r - i + c - j);
                    
                    if (newSteps < dp[r][c].first || (newSteps == dp[r][c].first && newResources > dp[r][c].second)) {
                        dp[r][c] = {newSteps, newResources};
                    }
                }
            }
        }
    }
    
    cout << dp[n][n].first << "\n";
    return 0;
}