Prefix Matching and Keyboard Layout Reconstruction

This problem involves identifying possible next characters based on a given prefix and mapping them to a specific $4 \times 8$ grid layout. The core task is to filter a list of strings that start with a specific sequence and mark the character that immediately follows that sequence.

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

bool is_available[26];

int main() {
    int count;
    cin >> count;
    vector<string> dictionary(count);
    for (int i = 0; i < count; ++i) cin >> dictionary[i];

    string prefix;
    cin >> prefix;

    for (const string& word : dictionary) {
        if (word.length() > prefix.length() && word.substr(0, prefix.length()) == prefix) {
            char next_char = word[prefix.length()];
            if (next_char >= 'A' && next_char <= 'Z') {
                is_available[next_char - 'A'] = true;
            }
        }
    }

    string layout = "***ABCDEFGHIJKLMNOPQRSTUVWXYZ***";
    for (int i = 0; i < 32; ++i) {
        if (layout[i] == '*') {
            cout << '*';
        } else {
            int idx = layout[i] - 'A';
            cout << (is_available[idx] ? layout[i] : '*');
        }
        if ((i + 1) % 8 == 0) cout << endl;
    }

    return 0;
}

Revenue Optimization via Greedy Pricing

Given a set of price points representing the maximum budget of different customers, the objective is to select a single price that maximizes total revenue. If a price $P$ is chosen, all customers with a budget $B \ge P$ will purchase the product.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int n;
    if (!(cin >> n)) return 0;
    vector<long long> budgets(n);
    for (int i = 0; i < n; ++i) cin >> budgets[i];

    sort(budgets.begin(), budgets.end());

    long long max_revenue = 0;
    for (int i = 0; i < n; ++i) {
        long long current_revenue = budgets[i] * (n - i);
        if (current_revenue > max_revenue) {
            max_revenue = current_revenue;
        }
    }

    cout << max_revenue << endl;
    return 0;
}

Iterative Matrix Expansion

The problem requires expanding a bit matrix through multiple iterations. In each step, every cell is replaced by a $2 \times 2$ block. If the original cell value is $V$, the top-left, top-right, and bottom-left cells of the new block are $V$, while the bottom-right cell is the logical NOT of $V$.

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int main() {
    int iterations, initial_val;
    cin >> iterations >> initial_val;

    vector<string> grid(1, to_string(initial_val));

    for (int k = 0; k < iterations; ++k) {
        int rows = grid.size();
        int cols = grid[0].size();
        vector<string> next_grid(rows * 2, string(cols * 2, '0'));

        for (int r = 0; r < rows; ++r) {
            for (int c = 0; c < cols; ++c) {
                char val = grid[r][c];
                char flipped = (val == '0' ? '1' : '0');
                next_grid[2 * r][2 * c] = val;
                next_grid[2 * r][2 * c + 1] = val;
                next_grid[2 * r + 1][2 * c] = val;
                next_grid[2 * r + 1][2 * c + 1] = flipped;
            }
        }
        grid = next_grid;
    }

    for (const string& row : grid) {
        cout << row << "\n";
    }

    return 0;
}

Dependency Traversal Using BFS

This problem models a system where tasks have specific weights and prerequisites. To complete a final goal (node $N$), all task reachable in the dependency graph (reversing the prerequisite direction) must be completed. We use Breadth-First Search (BFS) starting from the target node to sum the weights of all reqiured tasks.

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

struct Task {
    long long duration;
    vector<int> deps;
};

int main() {
    int n;
    cin >> n;
    vector<Task> tasks(n + 1);
    for (int i = 1; i <= n; ++i) {
        int dep_count;
        cin >> tasks[i].duration >> dep_count;
        for (int j = 0; j < dep_count; ++j) {
            int pre;
            cin >> pre;
            tasks[i].deps.push_back(pre);
        }
    }

    long long total_time = 0;
    queue<int> q;
    vector<bool> visited(n + 1, false);

    q.push(n);
    visited[n] = true;

    while (!q.empty()) {
        int curr = q.front();
        q.pop();
        total_time += tasks[curr].duration;

        for (int neighbor : tasks[curr].deps) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                q.push(neighbor);
            }
        }
    }

    cout << total_time << endl;
    return 0;
}

Minimum Operations for Palindromic Sequences

To transform an array into a palindrome with minimum replacements, elements at symmetric positions $(i, n-i+1)$ that differ must eventually be unified into the same value. This is solved by viewing each requiremetn as a union operation in a Disjoint Set Union (DSU) structure. The total operations needed equal the sum of (component size - 1) across all disjoint sets.

#include <iostream>
#include <vector>
#include <numeric>
#include <map>

using namespace std;

struct DSU {
    map<int, int> parent;
    int find(int i) {
        if (parent.find(i) == parent.end()) return parent[i] = i;
        if (parent[i] == i) return i;
        return parent[i] = find(parent[i]);
    }
    bool unite(int i, int j) {
        int root_i = find(i);
        int root_j = find(j);
        if (root_i != root_j) {
            parent[root_i] = root_j;
            return true;
        }
        return false;
    }
};

int main() {
    int n;
    cin >> n;
    vector<int> arr(n);
    DSU dsu;
    for (int i = 0; i < n; ++i) cin >> arr[i];

    int operations = 0;
    for (int i = 0; i < n / 2; ++i) {
        if (arr[i] != arr[n - 1 - i]) {
            if (dsu.unite(arr[i], arr[n - 1 - i])) {
                operations++;
            }
        }
    }

    cout << operations << endl;
    return 0;
}