Binary Number Decomposition

Given an integer n, decompose it into distinct powers of two. If n is odd, output -1.

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

int main() {
    long long n;
    cin >> n;
    
    if (n % 2 != 0) {
        cout << -1 << endl;
        return 0;
    }
    
    vector<long long> components;
    long long power = 1;
    while (power <= n) power <<= 1;
    power >>= 1;
    
    while (n > 0 && power > 0) {
        if (power <= n) {
            components.push_back(power);
            n -= power;
        }
        power >>= 1;
    }
    
    for (int i = 0; i < components.size(); i++) {
        if (i > 0) cout << " ";
        cout << components[i];
    }
    return 0;
}

Score Threshold Calcluation

Given n itnegers and a window w, compute the threshold score for each prefix such that at least max(1, i * w / 100) elements are included.

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

const int MAX_SCORE = 605;

int main() {
    int n, w;
    cin >> n >> w;
    int bucket[MAX_SCORE] = {0};
    
    for (int i = 1; i <= n; i++) {
        int score;
        cin >> score;
        bucket[score]++;
        
        int count = 0;
        int threshold = max(1, i * w / 100);
        
        for (int s = MAX_SCORE - 1; s >= 0; s--) {
            count += bucket[s];
            if (count >= threshold) {
                cout << s << " ";
                break;
            }
        }
    }
    return 0;
}

Boolean Experssion Evaluation with Query Handling

Parse a boolean expression string and build an evaluation tree. Handle queries to determine if flipping a leaf affects the root value.

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

const int MAX_NODES = 1000005;

char expr[MAX_NODES];
int value[MAX_NODES];
int children[MAX_NODES][2];
int flip[MAX_NODES];
int critical[MAX_NODES];
int node_count;

int evaluate(int node, int parent_flip) {
    value[node] ^= parent_flip;
    if (node <= node_count) return value[node];
    
    int left = evaluate(children[node][0], parent_flip ^ flip[children[node][0]]);
    int right = evaluate(children[node][1], parent_flip ^ flip[children[node][1]]);
    
    if (value[node] == 2) { // AND
        if (!left) critical[children[node][1]] = 1;
        if (!right) critical[children[node][0]] = 1;
        return left && right;
    } else { // OR
        if (left) critical[children[node][1]] = 1;
        if (right) critical[children[node][0]] = 1;
        return left || right;
    }
}

void propagate_critical(int node) {
    if (node <= node_count) return;
    critical[children[node][0]] |= critical[node];
    critical[children[node][1]] |= critical[node];
    propagate_critical(children[node][0]);
    propagate_critical(children[node][1]);
}

int main() {
    cin.getline(expr, MAX_NODES);
    cin >> node_count;
    int total_nodes = node_count;
    
    for (int i = 1; i <= node_count; i++) {
        cin >> value[i];
    }
    
    stack<int> st;
    for (int i = 0; expr[i]; i += 2) {
        if (expr[i] == 'x') {
            int idx = 0;
            i++;
            while (expr[i] && expr[i] != ' ') {
                idx = idx * 10 + (expr[i] - '0');
                i++;
            }
            i--;
            st.push(idx);
        } else if (expr[i] == '&') {
            int right = st.top(); st.pop();
            int left = st.top(); st.pop();
            st.push(++total_nodes);
            value[total_nodes] = 2;
            children[total_nodes][0] = left;
            children[total_nodes][1] = right;
        } else if (expr[i] == '|') {
            int right = st.top(); st.pop();
            int left = st.top(); st.pop();
            st.push(++total_nodes);
            value[total_nodes] = 3;
            children[total_nodes][0] = left;
            children[total_nodes][1] = right;
        } else if (expr[i] == '!') {
            flip[st.top()] ^= 1;
        }
    }
    
    int root_value = evaluate(total_nodes, flip[total_nodes]);
    propagate_critical(total_nodes);
    
    int queries;
    cin >> queries;
    while (queries--) {
        int leaf;
        cin >> leaf;
        cout << (critical[leaf] ? root_value : !root_value) << endl;
    }
    return 0;
}

Grid Path Maximization

Find the maximum sum path in an n x m grid moving right, up, or down from each cell.

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

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<long long>> grid(n + 1, vector<long long>(m + 1));
    vector<vector<long long>> dp(n + 1, vector<long long>(m + 1, -1e18));
    
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> grid[i][j];
        }
    }
    
    for (int i = 1; i <= n; i++) {
        dp[i][1] = dp[i - 1][1] + grid[i][1];
    }
    
    for (int j = 2; j <= m; j++) {
        vector<long long> left_pass(n + 2), right_pass(n + 2);
        
        left_pass[1] = dp[1][j - 1] + grid[1][j];
        for (int i = 2; i <= n; i++) {
            left_pass[i] = max(left_pass[i - 1], dp[i][j - 1]) + grid[i][j];
        }
        
        right_pass[n] = dp[n][j - 1] + grid[n][j];
        for (int i = n - 1; i >= 1; i--) {
            right_pass[i] = max(right_pass[i + 1], dp[i][j - 1]) + grid[i][j];
        }
        
        for (int i = 1; i <= n; i++) {
            dp[i][j] = max(left_pass[i], right_pass[i]);
        }
    }
    
    cout << dp[n][m] << endl;
    return 0;
}