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;
}

Observation The problem asks us to construct an h by w grid containing exactly one occurrence of the word "KIT" in any of the 8 directions, given exact counts for the letters 'K', 'I', and 'T'.

A brute-force or randomized placement approach is prone to accidentally creating secondary "KIT" occurrences, especially in larger grids where letters are densely packed.

Instead of thinking in 2D, we can flatten the grid into a 1D string of length h * w and fill it row by row. Any straight line in a 2D grid (horizontal, vertical, or diagonal) corresponds to an arithmetic progression of indices in this 1D string. Therefore, reading a word in the grid in any direction is equivalent to reading a subsequence from either our 1D string or its exact reverse.

Construction Strategy We can completely eliminate the possibility of accidental occurrences by controlling the order of the remaining characters in our 1D string.

• Place the intended "KIT": Start by placing "K", "I", and "T" at the very first three positions (indices 0, 1, and 2). This guarantees our single required occurrence.
• Isolate the remaining letters: Append all remaining 'T's, followed by all remaining 'K's, and finally all remaining 'I's.

Our complete 1D string S will look like this: S = "K" + "I" + "T" + (t — 1 times 'T') + (k — 1 times 'K') + (i — 1 times 'I')

#include<bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> ii;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef vector<ii> vii;
 
#define x first
#define y second
#define pb push_back
#define eb emplace_back
#define rep(i,a,b) for(auto i=(a); i<(b); ++i)
#define REP(i,n) rep(i,0,n)
#define all(v) (v).begin(), (v).end()
#define rs resize
#define DBG(x) cerr << __LINE__ << ": " << #x << " = " << (x) << endl
 
const ld PI = acos(-1.0);
template<class T> using min_queue =
priority_queue<T, vector<T>, greater<T>>;
template<class T> int sz(const T &x) {
    return (int) x.size(); // copy the ampersand(&)!
}
 
// START OF ACTUAL PROGRAM, START READING HERE
 
void run() {
	ll h, w, k, i, t;
	cin >> h >> w >> k >> i >> t;
	vector<char> A{'K','I','T'};
	for (ll j = 0; j < k-1; j++) A.pb('K');
	for (ll j = 0; j < t-1; j++) A.pb('T');
	for (ll j = 0; j < i-1; j++) A.pb('I');
	for (ll r = 0; r < h; r++) {
		for (ll c = 0; c < w; c++) {
			cout << A[r*w + c];
		}
		cout << endl;
	}
}
 
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout << fixed << setprecision(20);
    run();
    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;
}

If you fix a threshold x (meaning only slabs numbered <= x are allowed to move), can you check in O(nm) whether it's possible to clear the rectangle using only slabs numbered <= x? Think about what "achievability" looks like as a function of x.

Achievability is monotonic in x — if it's possible with a given x, it's also possible with any larger x — so binary search on x. For a fixed x, two conditions must both hold: no slab numbered greater than x sits inside the rectangle itself, and the connected component (formed by treating slabs numbered greater than x as walls) containing the rectangle must have at least as many empty cells as the rectangle's area.

Suppose the maximum slab number we're allowed to move is x (i.e. the energy budget caps us at moving slabs numbered <= x). To be able to clear the rectangle entirely, two conditions must hold:

1. No slab numbered greater than x lies inside the rectangle. Such a slab is immovable under this budget, so it would be permanently stuck inside — checkable directly by scanning the slab numbers within the rectangle.

2. The rectangle must fit inside its connected component of "free space." Treat every slab numbered greater than x as a wall. These walls partition the garden into connected components. Given condition (1) holds, the entire rectangle lies inside one connected component. For the rectangle to be clearable, the number of empty cells (cells without an immovable slab) in that connected component must be at least the area of the rectangle — otherwise there simply isn't enough free space to shuffle all the movable slabs out of the rectangle, regardless of the sequence of moves.

Condition (1) is checked by inspecting slab numbers within the rectangle directly. Condition (2) is checked with a DFS/BFS/DSU flood-fill from any cell of the rectangle (e.g. corner (x1,y1)) over cells not blocked by slabs numbered greater than x, comparing the resulting component's empty-cell count against the rectangle's area.

Since feasibility is monotonic in x (if x works, any x' > x also works), we binary search on x to find the minimum feasible value. Each feasibility check costs O(nm) for the flood fill, giving total complexity O(nm log k).

Edge cases to watch for: - Answer is 0 if the rectangle is already clearable with no slabs needing to move. - Answer is -1 if even using all k slabs (the maximum budget), the rectangle still cannot be cleared. - Answer is k if the full budget is necessary and sufficient.

Time Complexity: O(nm log k) Space Complexity: O(nm)

vp dir = { {-1, 0}, {0, 1}, {0, -1}, {1, 0} };

bool check2(int a, int b, int x1, int y1, int x2, int y2) {
    return a >= x1 && a <= x2 && b >= y1 && b <= y2;
}

bool check3(int a, int b, int n, int m) {
    return a < 0 || b < 0 || a >= n || b >= m;
}

bool check(int mid, vvi &grid, int x1, int y1, int x2, int y2, int n, int m, int issue) {

    int fre = 0;
    queue<pll> q;
    vector<vector<bool>> vis(n, vector<bool>(m, false));

    q.push({x1, y1});
    vis[x1][y1] = true;

    while (!q.empty()) {
        auto [x, y] = q.front();
        q.pop();

        for (auto [dx, dy] : dir) {
            int nx = x + dx;
            int ny = y + dy;

            if (check3(nx, ny, n, m)) continue;
            if (vis[nx][ny]) continue;

            if (check2(nx, ny, x1, y1, x2, y2)) {
                vis[nx][ny] = true;
                q.push({nx, ny});
            } else if (grid[nx][ny] <= mid) {
                vis[nx][ny] = true;
                q.push({nx, ny});
                if (grid[nx][ny] == 0) fre++;
            }
        }
    }

    return fre >= issue;
}

void resolve2(int tc) {
    int n, m ,k;
    cin >> n >> m >> k;
    vvi grid(n, vi(m, 0));
    f(1, k + 1, i) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        grid[u][v] = i;
    }
    int x1, x2, x3, x4;
    cin >> x1 >> x2 >> x3 >> x4;
    x1--, x2--, x3--, x4--;
    int maxi = 0;
    int issue = 0;
    f(x1, x3 + 1, i){
        f(x2, x4 + 1, j) {
            if(grid[i][j] > 0) issue++;
            maxi = max(grid[i][j], maxi);
        }
    }
    int l = maxi;
    int r = k;
    rn(bs_min(l, r, check, grid, x1, x2, x3, x4, n, m, issue));
}


int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    precalc();
    int t = 1;
    // cin >> t;
    while (t--) {
        resolve2(t);
        // resolve(t);
    }
    return 0;
}

Think of the string as a sequence of maximal blocks of identical characters. The score is the sum of $$$(\text{length}-1)$$$ over all blocks — so merging blocks together (turning several blocks into one bigger block) is what increases the score. What operation lets you merge two neighboring blocks?

You're allowed to delete blocks entirely (never partially — a partial deletion is never optimal). Deleting a block of length $$$1$$$ merges its two neighbors and increases the answer by exactly $$$1$$$. What happens if you delete a block with length $$$ \gt 1$$$ instead — does it ever help?

Decompose the string into maximal contiguous blocks of identical characters:

The score of the string as given is:

i.e. each block contributes $$$(\text{length}-1)$$$.

Key observations:

• We should never remove a block partially — partial removal never increases the score, since it just shortens a block without merging anything.
• We should only ever remove a block completely when its length is exactly $$$1$$$. Removing such a block merges its left and right neighboring blocks (which must share the same character, since blocks alternate), increasing the answer by exactly $$$1$$$.
• If a block has length $$$n_i \gt 1$$$, removing it entirely either keeps the answer the same or decreases it — so it's never beneficial.

So the strategy reduces to: repeatedly find and remove singleton blocks (length $$$1$$$), each one merging its neighbors and adding $$$1$$$ to the score, until no more singleton blocks can be merged away.

This can be simulated in a single left-to-right pass: whenever we see a character that differs from its previous character (starting a potential new block) but the block after it goes back to matching the previous character (i.e., it's a singleton block sandwiched between two equal blocks), we conceptually merge it by relabeling it to match its neighbors, allowing the merge to propagate. Whenever two adjacent characters in this evolving string are equal, we count it towards the answer.

Time Complexity: $$$O(n)$$$ per test Space Complexity: $$$O(n)$$$ (for the string)

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

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef set<int> si;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;

#define fo(i, a, b) for (ll i = a; i < b; i++)
#define F first
#define S second
#define pb push_back
#define mp make_pair
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()

ll p = 1e9+7;
#define mod p

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);
    ll T,n;
    cin >> T;
    while (T--) {
        cin >> n;
        string s;
        cin >> s;
        ll ans = 0;
        fo(i,1,n){
            if(s[i] != s[i-1]){
                if(i < n-1){
                    if(s[i] != s[i+1]){
                        s[i] = s[i-1];
                    }
                }
            }
            else{
                ans++;
            }
        }
        cout << ans << "\n";
    }
}

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;
}

Does the order of the artifacts in the vault matter? No, since two selections are considered different if they are chosen from different positions, we only care about the frequency of each artifact type.

If we know the frequencies of each distinct artifact type, say $$$f_1, f_2, \ldots, f_k$$$, how many ways can we choose one artifact of type $$$i$$$, one of type $$$j$$$, and one of type $$$m$$$? The number of ways is simply $$$f_i \times f_j \times f_m$$$. We need to sum this over all valid triplets $$$(i, j, m)$$$ where $$$i \lt j \lt m$$$.

First, we can use a Hash Map (or sort the array) to count the frequencies of each artifact type. Let's store these non-zero frequencies in a list $$$F = [f_1, f_2, \dots, f_k]$$$.

If the number of distinct artifact types $$$k$$$ is less than $$$3$$$, it is impossible to pick three strictly different types. In this case, the answer is immediately $$$0$$$.

If $$$k \ge 3$$$, the problem reduces to finding the sum of products of all triplets of frequencies:

Instead of iterating three times, we can iterate through the frequency list backwards and maintain running sums to build up our triplets.

Let's maintain three variables as we loop from right to left:

• suff_sum: The sum of the frequencies we have processed so far.
• pair_sum: The sum of the products of all pairs we have processed so far.
• ans: The total accumulated valid triplets.

When we are at index $$$i$$$ with frequency $$$F[i]$$$:

• We can form valid triplets by combining our current frequency $$$F[i]$$$ with all the valid pairs we've already found to the right. So, we add $$$F[i] \times \text{pair_sum}$$$ to ans.
• Next, we update pair_sum so it's ready for the next iteration. The new pairs formed by $$$F[i]$$$ will be $$$F[i] \times \text{suff_sum}$$$. We add this to pair_sum.
• Finally, we add $$$F[i]$$$ to suff_sum. This requires only a single pass through the frequencies list!

Time Complexity: $$$\mathcal{O}(N \log N)$$$ if using a std::map to count frequencies, or $$$\mathcal{O}(N)$$$ if using an unordered_map. The subsequent mathematical reduction takes $$$\mathcal{O}(k)$$$ where $$$k \le N$$$.

Space Complexity: $$$\mathcal{O}(N)$$$ to store the frequencies in a map and list.

#include <bits/stdc++.h>
using namespace std;
void run()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}
#define ll long long
#define vll vector<ll>
void fun()
{
    ll n;
    cin >> n;
    vll v(n);for (auto &it : v)  cin >> it;
 
    map<ll, ll> mp;
    for (auto it : v)   mp[it]++;
 
    vll v1;
    for (auto it : mp)  v1.push_back(it.second);
 
    ll suffsum = 0, ans = 0, sz = v1.size();
    if (sz < 3)
    {
        cout << 0 << endl;
        return;
    }
 
    suffsum += v1[sz - 1] + v1[sz - 2];
    ll nextval = v1[sz - 1] * v1[sz - 2];
 
    for (int i = sz - 3; i >= 0; i--)
    {
        ans += (v1[i] * nextval);
        nextval = nextval + (v1[i] * suffsum);
        suffsum += v1[i];
    }
    cout << ans << endl;
}
int main()
{
    run();
    ll t;
    cin >> t;
    while (t--)
        fun();
}