Given an integer x, construct a y < x such that gcd(x, y) = x ⊕ y (bitwise XOR).

The solution is to take y = x - lowestSetBit(x). If x is a power of 2, then no solution exists.

#include<iostream>
#include<cmath>

using namespace std;

using ll = long long;

void solve() {
    ll x;
    cin >> x;
    
    ll lowest_bit = x & -x;
    ll y = x - lowest_bit;
    
    if (y == 0) {
        cout << "-1\n";
    } else {
        cout << y << "\n";
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int test_cases;
    cin >> test_cases;
    
    while (test_cases--) {
        solve();
    }
    
    return 0;
}

C-Red Walking on Grid

Given a 2×n grid with some blocked cells, find the longest path starting from any cell, visiting each cell at most once.

We use dynamic programming. Traverse from left to right, maintaining DP states for both rows. When both cells in a column are accessible, we can transition between them.

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

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    
    string grid[2];
    cin >> grid[0] >> grid[1];
    
    int dp[2] = {0, 0};
    int result = 0;
    
    for (int i = 0; i < n; ++i) {
        if (grid[0][i] == 'R') {
            dp[0]++;
        } else {
            dp[0] = 0;
        }
        
        if (grid[1][i] == 'R') {
            dp[1]++;
        } else {
            dp[1] = 0;
        }
        
        if (grid[0][i] == 'R' && grid[1][i] == 'R') {
            int temp0 = max(dp[0], dp[1] + 1);
            int temp1 = max(dp[1], dp[0] + 1);
            dp[0] = temp0;
            dp[1] = temp1;
        }
        
        result = max({result, dp[0], dp[1]});
    }
    
    result = max(result - 1, 0);
    cout << result << "\n";
    
    return 0;
}

H-Instructions Substring

Given a sequence of moves (up, down, left, right) and a target point (x, y), count the number of substrings that pass through the target point.

We use prefix sums to track positions and reverse enumeration to efficiently count valid substrings.

#include<iostream>
#include<vector>
#include<map>
#include<array>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, x, y;
    cin >> n >> x >> y;
    
    string moves;
    cin >> moves;
    
    vector<array<int, 2>> prefix(n + 1);
    prefix[0] = {0, 0};
    
    for (int i = 0; i < n; ++i) {
        prefix[i + 1] = prefix[i];
        if (moves[i] == 'W') {
            prefix[i + 1][1]++;
        } else if (moves[i] == 'S') {
            prefix[i + 1][1]--;
        } else if (moves[i] == 'A') {
            prefix[i + 1][0]--;
        } else {
            prefix[i + 1][0]++;
        }
    }
    
    int count = 0;
    map<array<int, 2>, int> last_occurrence;
    
    for (int i = n; i >= 0; --i) {
        last_occurrence[prefix[i]] = i;
        
        array<int, 2> target = {prefix[i][0] + x, prefix[i][1] + y};
        if (last_occurrence.count(target)) {
            int j = last_occurrence[target];
            j = max(j, i + 1);
            count += n - j + 1;
        }
    }
    
    cout << count << "\n";
    
    return 0;
}

B-MST

Given a weighted undirected graph, answer multiple queries about the minimum spanning tree of subsets of vertices.

We use sqrt decomposition. For small subsets, we enumerate all pairs of vertices. For large subsets, we enumerate all edges from each vertex in the subset.

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

using namespace std;

using ll = long long;

struct DSU {
    vector<int> parent;
    
    DSU(int n) : parent(n + 1) {
        for (int i = 0; i <= n; ++i) {
            parent[i] = i;
        }
    }
    
    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }
    
    void unite(int x, int y) {
        parent[find(x)] = find(y);
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, m, q;
    cin >> n >> m >> q;
    
    vector<map<int, int>> graph(n + 1);
    vector<array<int, 3>> edges;
    
    for (int i = 0; i < m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        graph[u][v] = w;
        graph[v][u] = w;
    }
    
    const int threshold = sqrt(n);
    vector<int> subset;
    vector<int> visited(n + 1, 0);
    
    while (q--) {
        int k;
        cin >> k;
        subset.resize(k);
        
        for (int i = 0; i < k; ++i) {
            cin >> subset[i];
            visited[subset[i]] = 1;
        }
        
        int edge_count = 0;
        if (k <= threshold) {
            for (int i = 0; i < k; ++i) {
                for (int j = i + 1; j < k; ++j) {
                    if (graph[subset[i]].count(subset[j])) {
                        edges[edge_count++] = {graph[subset[i]][subset[j]], subset[i], subset[j]};
                    }
                }
            }
        } else {
            for (int i = 0; i < k; ++i) {
                int u = subset[i];
                for (auto& [v, w] : graph[u]) {
                    if (visited[v]) {
                        edges[edge_count++] = {w, u, v};
                    }
                }
            }
        }
        
        sort(edges.begin(), edges.begin() + edge_count);
        
        DSU dsu(n);
        ll mst_weight = 0;
        int edges_used = 0;
        
        for (int i = 0; i < edge_count; ++i) {
            auto& [w, u, v] = edges[i];
            if (dsu.find(u) != dsu.find(v)) {
                dsu.unite(u, v);
                mst_weight += w;
                edges_used++;
                if (edges_used == k - 1) break;
            }
        }
        
        for (int i = 0; i < k; ++i) {
            visited[subset[i]] = 0;
        }
        
        if (edges_used != k - 1) {
            cout << "-1\n";
        } else {
            cout << mst_weight << "\n";
        }
    }
    
    return 0;
}

I-Red Playing Cards

Given an array of length 2n where each number from 1 to n appears exactly twice, maximize the score by removing subarrays with matching endpoints.

We process intervals for each number and use dynamic programming to calcultae maximum scores.

#include<iostream>
#include<vector>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    n++;
    
    vector<int> arr(2 * n);
    for (int i = 1; i < 2 * n - 1; ++i) {
        cin >> arr[i];
    }
    
    vector<int> left(n, -1), right(n);
    for (int i = 0; i < 2 * n; ++i) {
        cin >> arr[i];
        if (left[arr[i]] == -1) {
            left[arr[i]] = i;
        } else {
            right[arr[i]] = i;
        }
    }
    
    vector<int> scores(n);
    for (int num = n - 1; num >= 0; --num) {
        vector<int> dp(2 * n + 1);
        for (int i = left[num] + 1; i < right[num]; ++i) {
            if (dp[i + 1] < dp[i] + num) {
                dp[i + 1] = dp[i] + num;
            }
            if (i == left[arr[i]] && right[arr[i]] < right[num]) {
                if (dp[right[arr[i]] + 1] < dp[i] + scores[arr[i]]) {
                    dp[right[arr[i]] + 1] = dp[i] + scores[arr[i]];
                }
            }
        }
        scores[num] = 2 * num + dp[right[num]];
    }
    
    cout << scores[0] << "\n";
    
    return 0;
}

G-The Set of Squares

Given a multiset of numbers, find the sum of weights of all subsets whose product is a perfect square.

We use prime factorization and dynamic programming with bitmasking for small primes and grouping for large primes.

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

using namespace std;

using ll = long long;

constexpr ll MOD = 1e9 + 7;
const int SMALL_PRIMES = 11;
int primes[SMALL_PRIMES] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    
    int max_val = 0;
    map<int, vector<pair<int, int>>> groups;
    
    for (int i = 0; i < n; ++i) {
        int x;
        cin >> x;
        max_val = max(max_val, x);
        
        int mask = 0, value = 1;
        for (int j = 0; j < SMALL_PRIMES; ++j) {
            while (x % primes[j] == 0) {
                x /= primes[j];
                mask ^= 1 << j;
                if (!(mask >> j & 1)) {
                    value = (ll)value * primes[j] % MOD;
                }
            }
        }
        groups[x].push_back({mask, value});
    }
    
    vector<ll> dp(1 << SMALL_PRIMES);
    dp[0] = 1;
    
    for (int i = 1; i <= max_val; ++i) {
        if (i * i <= 1000 && i != 1) continue;
        if (groups[i].empty()) continue;
        
        primes[SMALL_PRIMES] = i;
        for (auto& [state, val] : groups[i]) {
            auto new_dp = dp;
            
            if (i != 1) state |= 1 << SMALL_PRIMES;
            
            for (int j = 0; j < (1 << (SMALL_PRIMES + 1)); ++j) {
                int combined = j & state;
                ll new_val = val;
                for (int k = 0; k <= SMALL_PRIMES; ++k) {
                    if (combined >> k & 1) {
                        new_val = (ll)new_val * primes[k] % MOD;
                    }
                }
                new_dp[j ^ state] = (new_dp[j ^ state] + dp[j] * new_val) % MOD;
            }
            dp = move(new_dp);
        }
        
        for (int j = 1 << SMALL_PRIMES; j < (1 << (SMALL_PRIMES + 1)); ++j) {
            dp[j] = 0;
        }
    }
    
    cout << (dp[0] - 1 + MOD) % MOD << "\n";
    
    return 0;
}