Editorial — CC Wing Selection Contest 2026

The input is irrelevant. The required output is fixed and must be printed exactly as given.

This is a direct output problem.

We are given a single string as input, but regardless of what the input contains, we must print the four Terms and Conditions exactly as specified in the statement.

Since the required output is constant, there is no need to process the input.

Just print:

You confirm that you are a IIIT Allahabad Batch 2029 student. You understand that providing false information, copying code may result in removal from the wing. You accept that parties will be scheduled according to the alignment of the stars. You have double checked that you are screen — recording.

Time Complexity: $$$O(1)$$$

Space Complexity: $$$O(1)$$$

#include <bits/stdc++.h> 
using namespace std;

int main(){
cout<<"1. You confirm that you are a IIIT Allahabad Batch 2029 student.\n";
cout<<"2. You understand that providing false information, copying code may result in removal from the wing.\n";
cout<<"3. You accept that parties will be scheduled according to the alignment of the stars.\n";
cout<<"4. You have double checked that you are screen &mdash; recording.";
}

Try to determine $$$p_1, p_2, p_3, p_4$$$ first using a handful of queries on triples chosen from $$${1,2,3,4}$$$, then use $$$p_1, p_2$$$ as "anchors" to find the rest.

If you query the sum of each triple obtained by leaving out exactly one of $$${1,2,3,4}$$$ at a time, the four query results together encode $$$p_1+p_2+p_3+p_4$$$ redundantly — figure out how to invert this to recover each individual $$$p_i$$$.

We first determine $$$p_1,p_2,p_3,p_4$$$ using $$$4$$$ queries:

• query 1: indices $$$2,3,4 \Rightarrow q_1 = p_2+p_3+p_4$$$
• query 2: indices $$$1,3,4 \Rightarrow q_2 = p_1+p_3+p_4$$$
• query 3: indices $$$1,2,4 \Rightarrow q_3 = p_1+p_2+p_4$$$
• query 4: indices $$$1,2,3 \Rightarrow q_4 = p_1+p_2+p_3$$$

Adding all four queries, every $$$p_i$$$ ($$$1 \le i \le 4$$$) is counted exactly $$$3$$$ times:

So $$$\dfrac{q_1+q_2+q_3+q_4}{3} = p_1+p_2+p_3+p_4$$$.

Now for each $$$i \in {1,2,3,4}$$$, $$$q_i$$$ is exactly the sum of the other three values, i.e. $$$q_i = (p_1+p_2+p_3+p_4) - p_i$$$. Rearranging:

This recovers $$$p_1,p_2,p_3,p_4$$$ using just $$$4$$$ queries.

Once $$$p_1$$$ and $$$p_2$$$ are known, every remaining index $$$i$$$ ($$$5 \le i \le n$$$) can be found with a single query on indices $$$1,2,i$$$:

Total queries: $$$4 + (n-4) = n$$$, well within the interactive limit.

Time Complexity: $$$O(n)$$$ queries per test Space Complexity: $$$O(n)$$$

#include<bits/stdc++.h>
using namespace std;

int query(int i,int j,int k){
    int x;
    cout << "? " << i << ' ' << j << ' ' << k << flush << endl;
    cin >> x;
    return x;
}

int main(){
    int t;
    cin >> t;
    while(t--){
        int n;
        cin >> n;
        vector<int> p(n+1);
        int q[5];
        q[1] = query(2,3,4);
        q[2] = query(1,3,4);
        q[3] = query(1,2,4);
        q[4] = query(1,2,3);
        for(int i=1;i<=4;i++) p[i] = (q[1]+q[2]+q[3]+q[4])/3 &mdash; q[i];
        for(int i=5;i<=n;i++) p[i] = query(1,2,i) &mdash; p[1] &mdash; p[2];
        cout << "! ";
        for(int i=1;i<=n;i++) cout << p[i] << ' ';
        cout << flush << endl;
    }
    return 0;
}

Recall the identity that relates addition to bitwise operations: $$$a+b$$$ can be decomposed in terms of $$$a \oplus b$$$ (the "sum without carry") and $$$a & b$$$ (the "carry bits").

Specifically, $$$a+b = (a \oplus b) + 2\cdot(a & b)$$$. You are given $$$a+b$$$ and $$$a&b$$$ directly — can you isolate $$$a \oplus b$$$?

For any two integers $$$a,b$$$, consider adding them bit by bit. At each bit position, $$$a \oplus b$$$ gives the sum of that bit ignoring carry, while $$$a & b$$$ gives exactly the positions where a carry is generated, and that carry gets shifted one position left when added. This gives the identity:

We are given $$$S = a+b$$$ and $$$C = a&b$$$. Rearranging:

Since the input guarantees $$$a,b$$$ are valid non-negative integers consistent with the given $$$S$$$ and $$$C$$$, this value is guaranteed to be non-negative, so no extra validation is needed.

Time Complexity: $$$O(1)$$$ per test Space Complexity: $$$O(1)$$$

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    ll sum, andVal;
    cin >> sum >> andVal;
    cout << (sum - 2 * andVal) << '\n';
    return 0;
}

The maximum strength of a connection between two chambers depends only on the maximum GCD achievable between one element from each chamber. You do not need to consider all possible pairs.

A chamber can participate in an edge of weight g if it contains at least one number divisible by g. Use this to group chambers by divisors instead of building all possible edges.

To maximize the total strength, process the groups in descending order of GCD and connect chambers greedily using a Disjoint Set Union (DSU) structure, similar to Kruskal's algorithm for Maximum Spanning Trees.

We want to connect all psychic chambers into a single network with maximum total strength. Since the network must be connected and acyclic, this is a Maximum Spanning Tree problem.

For any two chambers, the best edge between them is the maximum GCD achievable between their elements. We do not need to explicitly build all edges.

Approach:

• For every value v, store all chambers that contain v.
• Iterate over all possible GCD values g from largest to smallest.
• For a fixed g, iterate over all multiples of g and collect all chambers that contain those values.
• Any two such chambers can be connected with an edge of weight at least g.
• Use Disjoint Set Union (DSU) to greedily connect these chambers. Each successful merge adds g to the total answer.

Processing GCDs in descending order ensures that the first time two components are connected, they are connected using their maximum possible GCD. DSU guarantees no cycles and exactly N-1 edges.

This greedy procedure is equivalent to Kruskal's algorithm for Maximum Spanning Tree and produces the optimal result.

Time Complexity: Enumerating multiples follows a harmonic series, giving O(M log M), where M = 2 * 10^5.

Space Complexity: O(N + sum(k_i))

#include <bits/stdc++.h>
using namespace std;
 
// Disjoint Set Union structure for maintaining connected components
struct DSU {
    vector<int> p, sz;
    DSU(int n) : p(n), sz(n,1) {
        iota(p.begin(), p.end(), 0);
    }
    int find(int x){
        return p[x] == x ? x : p[x] = find(p[x]); // path compression
    }
    bool unite(int a, int b){
        a = find(a);
        b = find(b);
        if(a == b) return false; // already connected
        if(sz[a] < sz[b]) swap(a,b); // union by size
        p[b] = a;
        sz[a] += sz[b];
        return true;
    }
};
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int T;
    cin >> T;
    while(T--){
        int N;
        cin >> N;
 
        const int MAXV = 200000;
        vector<vector<int>> pos(MAXV + 1); // pos[x] = list of chambers containing value x
 
        // Read chambers and store positions for each value
        for(int i = 0; i < N; i++){
            int k;
            cin >> k;
            while(k--){
                int x;
                cin >> x;
                pos[x].push_back(i);
            }
        }
 
        DSU dsu(N);
        long long ans = 0;
 
        vector<int> nodes;
        // Process all possible gcd values from largest to smallest
        for(int g = MAXV; g >= 1; g--){
            nodes.clear();
            // Gather all chambers containing multiples of g
            for(int m = g; m <= MAXV; m += g){
                for(int v : pos[m]){
                    nodes.push_back(v);
                }
            }
            if(nodes.empty()) continue;
 
            // Connect all gathered chambers with edges of weight g
            int root = nodes[0];
            for(int i = 1; i < (int)nodes.size(); i++){
                if(dsu.unite(root, nodes[i])){
                    ans += g; // add edge weight to total
                }
            }
        }
 
        cout << ans << "\n";
    }
 
    return 0;
}
 

Fix a split point $$$i$$$ and write out the condition $$$a_1+\cdots+a_i = a_{i+1}+\cdots+a_n$$$ in terms of the prefix sum of $$$b$$$, $$$n$$$, $$$i$$$, and $$$x$$$. You'll get a linear equation in $$$x$$$ — solve for $$$x$$$.

For each fixed $$$i$$$, the equation gives $$$x = \dfrac{2\cdot\text{prefix}_i - \text{total}}{n-2i}$$$. Watch out for two edge cases: the denominator $$$n-2i$$$ can be zero, and $$$x$$$ must be a non-negative integer, not just any real number. Try every $$$i$$$ from $$$1$$$ to $$$n-1$$$ and take the minimum valid $$$x$$$.

Let $$$S_i = b_1+b_2+\cdots+b_i$$$ be the prefix sum of $$$b$$$, and let $$$T = S_n$$$ be the total sum.

For a fixed split index $$$i$$$ ($$$1 \le i \lt n$$$), the condition $$$a_1+\cdots+a_i = a_{i+1}+\cdots+a_n$$$ becomes:

Rearranging:

So for each $$$i$$$ we get a linear equation in $$$x$$$:

• If $$$n-2i = 0$$$: the equation only has a solution when $$$2S_i - T = 0$$$, in which case any $$$x$$$ works, so the minimal choice is $$$x=0$$$.
• If $$$n-2i \ne 0$$$: $$$x = \dfrac{2S_i - T}{n-2i}$$$. This is only a valid candidate if it divides evenly and the resulting $$$x$$$ is a non-negative integer.

We iterate $$$i$$$ from $$$1$$$ to $$$n-1$$$, compute $$$S_i$$$ using a running prefix sum, check divisibility and non-negativity, and take the minimum valid $$$x$$$ over all $$$i$$$. If no $$$i$$$ yields a valid $$$x$$$, output $$$-1$$$.

All quantities ($$$S_i$$$, $$$T$$$, numerator) fit comfortably in a 64-bit integer since $$$n \le 2\cdot10^5$$$ and $$$|b_i|\le 10^9$$$, and the problem guarantees any valid answer is $$$\le 10^{18}$$$, which also fits in a signed 64-bit integer.

Time Complexity: $$$O(n)$$$ per test Space Complexity: $$$O(1)$$$ extra (besides input array)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while(t--){
        int n;
        cin >> n;
        vector<ll> b(n+1);
        for(int i=1;i<=n;i++) cin >> b[i];

        vector<ll> pre(n+1,0);
        for(int i=1;i<=n;i++) pre[i] = pre[i-1] + b[i];
        ll total = pre[n];

        bool found = false;
        ll best = LLONG_MAX;

        for(int i=1;i<n;i++){
            ll numerator = 2*pre[i] - total;
            ll denom = (ll)n - 2*i;
            if(denom == 0){
                if(numerator == 0){
                    found = true;
                    best = min(best, 0LL);
                }
            } else {
                if(numerator % denom == 0){
                    ll x = numerator / denom;
                    if(x >= 0){
                        found = true;
                        best = min(best, x);
                    }
                }
            }
        }

        if(found) cout << best << '\n';
        else cout << -1 << '\n';
    }
    return 0;
}

We consider a train route (1, v) as an undirected deletable edge (1, v).

Let dist(u) be the shortest path between 1 and u. We add all of the edges (u, v) weighted w where dist(u) + w = dist(v) into a new directed graph.

A deletable edge (1, v) can be deleted only if it isn't in the new graph or the in-degree of v in the new graph is more than 1, because the connectivity of the new graph won't be changed after deleting these edges. Notice that you should subtract one from the in-degree of v after you delete an edge (1, v).

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF (int)1e18

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
int n, m, k;
const int maxn = 1e5 + 69;
vector <pair<int, int>> adj[maxn];
int in[maxn];
int d[maxn];
vector <pair<int, int>> e;
vector <pair<pair<int, int> , int>> eg;

void build()
{
    d[1] = 0;
    for (int i=2; i<=n; i++)d[i] = 1e18;
    priority_queue <pair<int, int>> pq;
    pq.push({0, 1});
    while (!pq.empty()){
        auto p = pq.top();
        pq.pop();
        int u = p.second;
        int dist = -p.first;
        if (d[u] != dist) continue;
        for (auto v: adj[u]){
            if (d[v.first] > v.second + dist){
                d[v.first] = v.second + dist;
                pq.push({-d[v.first], v.first});
            }
        }
    }
}

void Solve() 
{
    cin>>n>>m>>k;
    
    for (int i=1; i<=m; i++){
        int u, v, w;
        cin>>u>>v>>w;
        
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
        eg.push_back({{u, v}, w});
    }
    
    for (int i=1; i<=k; i++){
        int s, y;
        cin>>s>>y;
        adj[1].push_back({s, y});
        adj[s].push_back({1, y});
        e.push_back({s, y});
    }
    
    build();
    
    int ans = 0;
    for (auto x: eg){
        int u = x.first.first;
        int v = x.first.second;
        int w = x.second;
        if (d[u] == d[v] + w){
            in[u]++;
        } else if (d[v] == d[u] + w){
            in[v]++;
        }
    }
    
    for (auto x: e){
        int s = x.first;
        int y = x.second;
        if (d[s] != y) {
            ans ++;
            continue;
        }
        if (in[s]>0)
        ans++;
        else 
        in[s]++;
    }
    
    cout<<ans;
}

int32_t main() 
{
    auto begin = std::chrono::high_resolution_clock::now();
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
    //cin >> t;
    for(int i = 1; i <= t; i++) 
    {
        //cout << "Case #" << i << ": ";
        Solve();
    }
    auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
    return 0;
}

To start with make the following observation: if two rings i and j have equal outer radiuses bi = bj they can be merged in one ring of the same outer radius, inner radius equal to min(ai, aj) and height equal to hi + hj.

Using the observation we transform our problem to the one with distinct outer radiuses. Sort ring by this radius in descending order. From this point we consider bi < bj for all i > j. For each ring we want to compute value ans(i) — maximum height of the tower that ends with the ring i. This dynamic programming can be computed in O(n2) time using the following formula: .

There are two different ways to speed up the calculation of this dp:

Keep rings sorted by inner radius in a separate array. For each ring j < i store its value of ans(j) there and 0 for others. To get max ans(j) we have to query maximum on some suffix of this array: from the one hand only rings with original index j < i will be non-zero, from the other hand this will suffice the condition bi > aj. This can be done using segment tree or binary indexed tree. Note that if i < j < k and it's possible to place ring k on ring j and ring k on ring i, then it's possible to place ring j on ring i. Indeed, from ai < bk and bk < bj follows ai < bj. That means we only need to compute for each i maximum value j such that aj < bi. This can be done using data structures listed above or just with a single pass over array with a stack. Go from left to right and keep indexes of all valid positions in increasing order. Pop elements while they do not suffice condition aj < ai and then put i on the top. For clarifications, check the following code:

stack <int> opt;
for (int i = 0; i < n; i++) {
     while (!opt.empty() && r[opt.back()].inner >= r[i].outer)
         opt.pop();
     if (!opt.empty())
         ans[i] = ans[opt.back()];
     ans[i] += r[i].height;
     opt.push(i);
}

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

using namespace std;

// Structure to represent a ring
struct Ring {
    long long inner;
    long long outer;
    long long height;
};

// Custom comparator to sort rings descending by outer radius
bool compareRings(const Ring& a, const Ring& b) {
    return a.outer > b.outer;
}

int main() {
    // Fast I/O
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    if (!(cin >> n)) return 0;

    vector<Ring> r(n);
    for (int i = 0; i < n; i++) {
        cin >> r[i].inner >> r[i].outer >> r[i].height;
    }

    // Sort by outer radius in descending order
    sort(r.begin(), r.end(), compareRings);

    // Observation 1: Merge rings with identical outer radii
    vector<Ring> merged_rings;
    for (int i = 0; i < n; i++) {
        if (merged_rings.empty() || merged_rings.back().outer != r[i].outer) {
            merged_rings.push_back(r[i]);
        } else {
            // Merge into a single ring: min inner radius and sum of heights
            merged_rings.back().inner = min(merged_rings.back().inner, r[i].inner);
            merged_rings.back().height += r[i].height;
        }
    }

    int m = merged_rings.size();
    vector<long long> ans(m, 0); // ans[i] stores the max tower height ending with merged_rings[i]
    vector<int> opt;             // Vector acting as the monotonic stack
    long long max_total_height = 0;

    // Observation 2: DP optimization using a stack
    for (int i = 0; i < m; i++) {
        // Pop elements while they don't satisfy the condition aj < bi (or inner >= outer)
        while (!opt.empty() && merged_rings[opt.back()].inner >= merged_rings[i].outer) {
            opt.pop_back();
        }
        
        // If stack is not empty, the top of the stack is the best valid base
        if (!opt.empty()) {
            ans[i] = ans[opt.back()];
        }
        
        // Add the current ring's height
        ans[i] += merged_rings[i].height;
        
        // Push current index onto the stack
        opt.push_back(i);
        
        // Keep track of the maximum height achieved across all possible tower tops
        max_total_height = max(max_total_height, ans[i]);
    }

    cout << max_total_height << "\n";

    return 0;
}

Let the XOR sum of the entire tree be $$$X$$$. If we successfully divide the tree into three components with XOR sums $$$X_1, X_2,$$$ and $$$X_3$$$, the problem statement requires $$$X_1 = X_2 = X_3$$$.

By the properties of bitwise XOR, the total XOR sum of the tree is $$$X_1 \oplus X_2 \oplus X_3 = X$$$.
Substituting the equality gives $$$X_1 \oplus X_1 \oplus X_1 = X \implies X_1 = X$$$.

Thus, every resulting component must have an XOR sum exactly equal to $$$X$$$.

Pick an arbitrary root (e.g., vertex 1) and calculate the XOR sum of every subtree.

If $$$X = 0$$$, we just need to find any two non-overlapping subtrees that evaluate to $$$0$$$. The remaining component will naturally evaluate to $$$0 \oplus 0 \oplus 0 = 0$$$.
If $$$X \neq 0$$$, we need to find at least two subtrees with an XOR sum of $$$X$$$ that can be safely separated from the rest of the tree.

A greedy bottom-up approach works perfectly for both cases. Perform a post-order DFS. Whenever you evaluate a subtree's XOR sum to be equal to $$$X$$$ (and the node is not the root), "cut" it by pretending its XOR contribution to its parent is $$$0$$$, and increment a counter. If you can make at least 2 cuts, the answer is YES.

We want to partition the tree into 3 components with equal XOR sums. As established in the hints, each component must have an XOR sum equal to $$$X$$$, where $$$X$$$ is the total XOR sum of all vertices in the initial tree.

We can solve this efficiently using a greedy Depth-First Search (DFS):

• First, calculate the total XOR sum $$$X$$$ of all vertices.
• Root the tree arbitrarily at vertex 1 and run a DFS to compute the XOR sum of each subtree.
• Let curr be the XOR sum of the subtree rooted at the current node $$$u$$$.
• During the bottom-up return of the DFS, if we find that curr == X and $$$u \neq 1$$$, we have successfully isolated a valid component! We increment a cuts counter and return $$$0$$$ to the parent. Returning $$$0$$$ simulates "severing" the edge above $$$u$$$, removing its influence from the remainder of the tree.
• If $$$u$$$ is the root or curr != X, we simply return curr to the parent.
• Finally, if cuts >= 2, we output YES. Otherwise, NO.

#include <bits/stdc++.h>
using namespace std;

// Standard DFS function that returns the XOR sum of the current subtree
int dfs(int u, int p, const vector<vector<int>>& adj, const vector<int>& a, int tot, int& cuts) {
    int curr = a[u];
    
    for (int v : adj[u]) {
        if (v != p) {
            // Add the contribution of the child subtree to the current node
            curr ^= dfs(v, u, adj, a, tot, cuts);
        }
    }
    
    // If we found a valid component and it's not the root
    if (curr == tot && u != 1) {
        cuts++;
        return 0; // "Cut" the edge by returning 0 to the parent
    }
    
    return curr;
}

void solve() {
    int n;
    cin >> n;
    
    vector<int> a(n + 1);
    int tot = 0;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        tot ^= a[i]; // Calculate the total XOR sum of the tree
    }
    
    vector<vector<int>> adj(n + 1);
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    int cuts = 0;
    
    // Start DFS from root 1 with parent 0
    dfs(1, 0, adj, a, tot, cuts);

    if (cuts >= 2) {
        cout << "YES\n";
    } else {
        cout << "NO\n";
    }
}

int main() {
    // Fast I/O
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    
    return 0;
}