• Excellent contest
• Good contest
• Average contest
• Bad contest
• Horrible contest

• Easy contest
• Normal contest
• Hard contest

Assume $$$a \le b \le c$$$, does $$$b$$$ ever change?

For simplicity, let's assume $$$a \le b \le c$$$ (we can sort the input to achieve this). The operation decreases $$$c$$$ by $$$1$$$ and increases $$$a$$$ by $$$1$$$. Therefore, $$$a$$$ is getting closer to $$$b$$$ and $$$c$$$ is also getting closer to $$$b$$$. The round ends when $$$2$$$ players have the same value, so the answer is $$$\min(b - a, c - b)$$$ since if either $$$a$$$ or $$$c$$$ become equal to $$$b$$$, the game will end.

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

int main() {
    int t;
    cin >> t;
    while(t--) {
        vector<int> v(3);
        for(int &x : v) cin >> x;
        sort(v.begin(), v.end());
        cout << min(v[2] - v[1], v[1] - v[0]) << endl;
    }
}

• Excellent problem
• Good problem
• Average problem
• Bad problem
• Horrible problem

If we perform the operation on any character in a maximal contiguous block of length $$$ \gt 1$$$, then $$$f(s') = f(s)$$$.

The function $$$f(s)$$$ converts every maximal contiguous block into a block of size $$$1$$$. Therefore, removing a character from a block does not change anything if the block will still exist. The only way we can delete the whole block is if it had a size of $$$1$$$. This allows to delete the sole character that exists in the block, additionally achieving $$$f(s') \lt f(s)$$$.

When deleting a block of size $$$1$$$, we should consider what happens when the left block touches the right block. If they both contain the same character, then they would merge into one block. Therefore, the answer would decrease by $$$2$$$ (our $$$1$$$-sized block got removed, and $$$2$$$ separate blocks got merged into one).

Otherwise, if the blocks do not contain the same character, then the answer would decrease by $$$1$$$ since nothing will happen other than removing the $$$1$$$-sized block.

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

int main() {
    int t;
    cin >> t;
    while(t--) {
        int n;
        cin >> n;
        string s;
        cin >> s;
        
        int ans = 1, x = 0;
        for(int i = 1; i < n; i++) {
            if(s[i] != s[i - 1]) ans++;
            if(i == n - 1) break;
            
            if(s[i] != s[i - 1] && s[i] != s[i + 1]) {
                if(s[i + 1] == s[i - 1]) x = 2;
                else x = max(x, 1);
            }
        }
        
        cout << ans - x << endl;
    }
}

• Excellent problem
• Good problem
• Average problem
• Bad problem
• Horrible problem

The operation is equivalent to freely swapping $$$a_i$$$ with $$$a_{i+2}$$$ for any valid index $$$i$$$.

After the reduction from Hint 1, we can treat $$$a$$$ as two separate strings.

Notice that the operation can be treated as swapping $$$a_i$$$ with $$$a_{i+2}$$$, this works since the operation does not change the middle element, and only changes the first one and the third one.

Because an element can only move in steps of two, it can never change the parity of its index. Any character at an odd position will always remain at an odd position, and the same applies for even indices.

Since we have the power to swap the characters at odd indices endlessly (as many times as we want), we can rearrange them into any arrangement we want, independently of the characters at even indices. Therefore, the elements at odd positions in $$$a$$$ can match the elements at odd positions in $$$b$$$ if they have the same number of ones (or zeros). The same can be applied for even positions.

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int t;
    cin >> t;
    while(t--) {
        int n;
        cin >> n;
        string a, b;
        cin >> a >> b;
        
        int cnta[2] = {}, cntb[2] = {};
        for(int i = 0; i < n; i++) {
            cnta[i % 2] += a[i] == '1';
            cntb[i % 2] += b[i] == '1';
        }
        
        cout << (cnta[0] == cntb[0] && cnta[1] == cntb[1] ? "YES" : "NO") << endl;
    }
}

• Excellent problem
• Good problem
• Average problem
• Bad problem
• Horrible problem

Building off the core observation from the easy version, we know that elements are strictly trapped in their own parity. Odd-indexed characters only interact with odd-indexed characters, and even with even.

The problem then boils down to a classic task: what is the minimum number of adjacent swaps needed to transform a binary array into another?

Since all '$$$\texttt{1}$$$'s are identical, they never need to leapfrog over each other. The optimal path is always for the $$$k$$$-th '$$$\texttt{1}$$$' in your starting array to walk directly to the position of the $$$k$$$-th '$$$\texttt{1}$$$' in your target array.

To implement this, just iterate through both strings and collect the positions of the '$$$\texttt{1}$$$'s in the odd indices into one list, and the positions of the '$$$\texttt{1}$$$'s in the even indices into another. If the lengths of the corresponding lists for $$$a$$$ and $$$b$$$ don't match, it's impossible to transform, so output $$$-1$$$. Otherwise, just sum up the absolute differences between the $$$k$$$-th elements of the starting and target lists for both the odd and even arrays. That sum, divided by $$$2$$$, is your exact minimum number of operations. We divide by $$$2$$$ because one operation moves characters by $$$2$$$ steps.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
 
int main() {
    int t;
    cin >> t;
    while(t--) {
        int n;
        cin >> n;
        string a, b;
        cin >> a >> b;
        
        ll ans = 0;
        bool ok = true;
        
        for(int k = 0; k < 2; k++) {
            vector<int> p1, p2;
            for(int i = k; i < n; i += 2) {
                if(a[i] == '1') p1.push_back(i);
                if(b[i] == '1') p2.push_back(i);
            }
            
            if(p1.size() != p2.size()) {
                ok = false;
                break;
            }
            
            for(int i = 0; i < p1.size(); i++) ans += abs(p1[i] - p2[i]);
        }
        
        if(!ok) cout << -1 << endl;
        else cout << ans / 2 << endl;
    }
}

• Excellent problem
• Good problem
• Average problem
• Bad problem
• Horrible problem

Equal values in $$$a$$$ will always have the exact same shadow, and larger elements always have strictly larger shadows. So if you sort the distinct values of $$$b$$$, they correspond in order to the distinct values of $$$a$$$: the group with the $$$i$$$-th smallest value has shadow equal to the $$$i$$$-th smallest distinct value in $$$b$$$.

Let $$$s_1 \lt s_2 \lt \dots \lt s_m$$$ be the distinct sorted values of $$$b$$$, and let group $$$i$$$ be all elements sharing the value corresponding to $$$s_i$$$. Then $$$s_i$$$ is the sum of all groups smaller than group $$$i$$$, and $$$s_{i+1}$$$ is that same sum plus group $$$i$$$ itself. So $$$s_{i+1} - s_i = c_i \cdot v_i$$$, where $$$c_i$$$ is the count of elements in group $$$i$$$ and $$$v_i$$$ is their value.

What must $$$s_1$$$ be? And once every $$$v_i$$$ is pinned down by the equation above, is there a group left with no equation constraining its value? What's the smallest legal choice for it?

It's easy to see that equal values in $$$a$$$ produce equal shadows. The converse also holds: distinct values in $$$a$$$ always produce distinct shadows, and moreover a larger value always produces a larger shadow. So if we sort the distinct values of $$$a$$$ as $$$v_1 \lt v_2 \lt \dots \lt v_k$$$ with frequencies $$$c_1, \dots, c_k$$$, then the shadow of group $$$i$$$ is simply the sum of all smaller groups, $$$S_{i-1} = \sum_{j \lt i} c_j v_j$$$, and these prefix sums satisfy $$$S_0 = 0 \lt S_1 \lt \dots \lt S_{k-1}$$$. In other words, the distinct values of $$$b$$$, sorted, correspond exactly and in order to these prefix sums.

This gives a direct reconstruction. Sort the distinct values of $$$b$$$ as $$$s_1 \lt s_2 \lt \dots \lt s_m$$$; since $$$S_0$$$ must be $$$0$$$, we need $$$s_1 = 0$$$, otherwise the answer is $$$-1$$$. The count of $$$s_i$$$ in $$$b$$$ gives $$$c_i$$$, the size of group $$$i$$$, and since $$$s_{i+1} - s_i = c_i \cdot v_i$$$, we can recover $$$v_i = \frac{(s_{i+1} - s_i)}{c_i}$$$. If this division isn't exact, or if the resulting $$$v_i$$$ doesn't exceed $$$v_{i-1}$$$, no valid array exists. The very last group has no such equation to pin it down, so to keep $$$a$$$ lexicographically smallest we assign it the smallest legal value, one more than the previous group's value.

Once every group's value is known, replace each $$$b_i$$$ by its group's value to get $$$a$$$.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
 
int main() {
    int t;
    cin >> t;
    while(t--) {
        int n;
        cin >> n;
        vector<ll> b(n);
        map<ll, ll> freq;
        
        for(int i = 0; i < n; i++) {
            cin >> b[i];
            freq[b[i]]++;
        }
    
        if (!freq.count(0)) {
            cout << -1 << endl;
            continue;
        }
    
        map<ll, ll> ans;
        ll prv_shadow = 0, prv_cnt = 0, lst = 0;
        bool ok = true;
    
        for(auto [cur_shadow, cur_cnt] : freq) {
            if(cur_shadow != 0) {
                ll diff = cur_shadow - prv_shadow;
                
                if(diff % prv_cnt != 0) {
                    ok = false;
                    break;
                }
                
                ll u = diff / prv_cnt;
                if(u <= lst) {
                    ok = false;
                    break;
                }
                
                ans[prv_shadow] = u;
                lst = u;
            }
            
            prv_shadow = cur_shadow;
            prv_cnt = cur_cnt;
        }
        
        if(!ok) {
            cout << -1 << endl;
            continue;
        }
        
        ans[prv_shadow] = lst + 1;
        for(int i = 0; i < n; ++i) cout << ans[b[i]] << " \n"[i == n - 1];
    }
}

• Excellent problem
• Good problem
• Average problem
• Bad problem
• Horrible problem

The problem states that $$$b_i = a_i - a_{i-1}$$$. This directly implies that $$$a_i = a_{i-1} + b_i$$$. If you assume $$$a_0 = 0$$$, you can view $$$a$$$ simply as the prefix sums of some permutation of $$$b$$$.

The standard way to achieve a lexicographically smallest sequence is to build it greedily from left to right, making $$$a_1$$$ as small as possible, then $$$a_2$$$ as small as possible, and so forth.

Since $$$a_{i-1}$$$ is fixed from the previous steps, minimizing $$$a_i$$$ means you must pick the smallest available $$$b_i$$$. However, the problem imposes a strict rule: every element in $$$a$$$ must be strictly positive ($$$a_i \ge 1$$$). How does this restrict your choice of $$$b_i$$$?

Let's rewrite the given operation backwards. We are told that $$$b_i = a_i - a_{i-1}$$$. By rearranging this, we get $$$a_i = a_{i-1} + b_i$$$. If we define $$$a_0 = 0$$$, the array $$$a$$$ is essentially just the prefix sums of some permutation of the array $$$b$$$.

We are asked to find a permutation of $$$b$$$ that produces an array $$$a$$$ satisfying two conditions: every $$$a_i$$$ must be strictly positive, and $$$a$$$ must be lexicographically smallest.

To construct the lexicographically smallest array $$$a$$$, we should build it greedily from left to right. Suppose we have already successfully constructed the prefix of $$$a$$$ up to $$$a_{i-1}$$$. To determine $$$a_i$$$, we need to choose an unused element from $$$b$$$ to act as $$$b_i$$$. Since $$$a_{i-1}$$$ is already fixed, minimizing $$$a_i$$$ is exactly the same as picking the smallest possible $$$b_i$$$.

However, we can't just pick the absolute minimum available element because we must guarantee that $$$a_i \ge 1$$$. Substituting our earlier equation, this means $$$a_{i-1} + b_i \ge 1$$$, which simplifies to $$$b_i \ge 1 - a_{i-1}$$$.

This gives us a clear greedy strategy. At each step $$$i$$$, we must select the smallest available element in $$$b$$$ that is greater than or equal to $$$1 - a_{i-1}$$$. To implement this efficiently, we can insert all elements of the given array $$$b$$$ into a multiset. We maintain a running sum variable to represent $$$a_{i-1}$$$ (initially $$$0$$$). At each step, we query the multiset for the lower_bound of $$$1 - a_{i-1}$$$. If the iterator returns the end of the multiset, it means no available element is large enough to keep the current value strictly positive. In this case, a valid array cannot be formed, and we immediately output $$$-1$$$. If a valid element is found, we add it to our running sum to compute $$$a_i$$$, store it in our answer array, and erase that element from the multiset. We repeat this process $$$n$$$ times.

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

void solve() {
    int n, cur = 0;
    cin >> n;
    multiset<int> b;
    for(int i = 0; i < n; i++) {
        int x;
        cin >> x;
        b.insert(x);
    }
    
    vector<int> ans(n);
    for(int i = 0; i < n; i++){
        auto it = b.lower_bound(1 - cur);
        if(it == b.end()) return void(cout << -1 << '\n');
        cur += *it;
        b.erase(it);
        ans[i] = cur;
    }
    
    for(int i = 0; i < n; i++) cout << ans[i] << " \n"[i == n - 1];
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while(t--) solve();
}

• Excellent problem
• Good problem
• Average problem
• Bad problem
• Horrible problem

Try tracing the array elements after performing two consecutive operations, say on index $$$i$$$ and then on index $$$j$$$. If you look at the set of resulting values and ignore their order, how does it compare to the set of values you would get if you only performed a single operation on index $$$j$$$?

Any sequence of operations results in an array that is just a permutation of either the original array $$$a$$$, or the array $$$a$$$ after exactly one operation.

Let's analyze how a single operation affects the overall XOR sum of the array. Let $$$S_a$$$ be the XOR sum of all elements in $$$a$$$. When we choose an index $$$i$$$, we XOR $$$n-1$$$ elements with $$$a_i$$$. Since $$$n$$$ is even, $$$n-1$$$ is odd. The new XOR sum of the array will be $$$S_a \oplus (a_i \text{ XORed } n-1 \text{ times})$$$, which simplifies perfectly to $$$S_a \oplus a_i$$$.

Now, let's observe what happens if we perform multiple operations. Suppose we perform an operation on index $$$i$$$, followed by an operation on index $$$j$$$. After the first operation, the element at index $$$j$$$ becomes $$$a_j \oplus a_i$$$, and the element at index $$$i$$$ remains $$$a_i$$$. All other elements $$$a_k$$$ become $$$a_k \oplus a_i$$$.

During the second operation, we XOR everything (except index $$$j$$$) with the current value at index $$$j$$$, which is $$$a_j \oplus a_i$$$.

Let's look at the resulting values:

• For any other index $$$k$$$, the value becomes $$$(a_k \oplus a_i) \oplus (a_j \oplus a_i) = a_k \oplus a_j$$$.
• For index $$$i$$$, the value becomes $$$a_i \oplus (a_j \oplus a_i) = a_j$$$.
• For index $$$j$$$, the value remains $$$a_j \oplus a_i$$$.

If we look at this final set of values, it is exactly the same as if we had skipped the first operation and only performed a single operation on index $$$j$$$ from the very beginning. The order of the elements is different, but the set of values is identical.

This reveals the core property of the problem: no matter how many operations you perform, the resulting array (ignoring the order of elements) will either be identical to the original array $$$a$$$, or identical to the array $$$a$$$ after exactly one operation.

This gives us a straightforward solution. First, sort both arrays. If $$$a$$$ and $$$b$$$ are already identical, we output "YES" (0 operations needed). If they are not identical, we need to simulate exactly one operation. Which element $$$a_i$$$ should we use? We know from our first observation that the target XOR sum $$$S_b$$$ must equal $$$S_a \oplus a_i$$$. By rearranging this, the required element must be $$$a_i = S_a \oplus S_b$$$. We compute this target value $$$x = S_a \oplus S_b$$$. If $$$x$$$ does not exist in our initial array $$$a$$$, we can immediately output "NO". If it does exist, we find its index, apply the operation to array $$$a$$$, sort the modified array, and check if it now matches $$$b$$$.

#include <bits/stdc++.h>
using namespace std;
 
signed main() {
    int t;
    cin >> t;
    while(t--) {
        int n;
        cin >> n;
        vector<int> a(n), b(n);
        for(auto &it : a) cin >> it;
        for(auto &it : b) cin >> it;
 
        sort(a.begin(), a.end());
        sort(b.begin(), b.end());

        if(a == b) {
            cout << "YES" << endl;
            continue;
        }
 
        int x = 0;
        for(auto it : a) x ^= it;
        for(auto it : b) x ^= it;
		
        int idx = -1;
        for(int i = 0; i < n; i++) {
            if(a[i] == x) {
                idx = i;
                break;
            }
        }

        if(idx == -1) {
            cout << "NO" << endl;
            continue;
        }
 
        for(int i = 0; i < n; i++) {
            if(i == idx) continue;
            a[i] ^= x;
        }
 
        sort(a.begin(), a.end());
        cout << (a == b ? "YES" : "NO") << endl;
    }
}

• Excellent problem
• Good problem
• Average problem
• Bad problem
• Horrible problem

Because no subset can contain branching paths, two distinct leaves can never belong to the same subset. If the tree has $$$\ell$$$ leaves, you need at least $$$\ell$$$ subsets. Any $$$k \lt \ell$$$ is impossible. For $$$k \ge \ell$$$, the condition is always satisfiable since you can always break paths into smaller singletons.

Try to build the solution bottom-up. Each leaf starts a path. When these paths meet at a parent node, the parent can only join one of them. To maximize the total score, which path's maximum should the parent node interact with?

It is always optimal for the parent to join the path that currently has the smallest maximum. If the parent's value is larger, it successfully increases that path's maximum, leaving the old maximum behind as a spare value. If the parent is smaller, the path is unaffected, and the parent itself becomes the spare value that we can use if we are allowed extra subsets.

The core restriction is that every subset must form a straight vertical chain (an ancestor-descendant path). This immediately tells us that two distinct leaves can never be placed in the same subset. Consequently, the minimum number of subsets $$$k$$$ we can ever form is exactly the number of leaves in the tree, which we will call $$$\ell$$$. For any $$$k \lt \ell$$$, a valid partition is impossible, and we output $$$-1$$$. For $$$k \ge \ell$$$, it is always possible because we can just break valid chains into individual singleton nodes.

Let's build the optimal chains from the bottom up. Every leaf initially forms its own chain where the maximum value is just the leaf's value. As we move up the tree, paths merge at a parent node $$$u$$$. The node $$$u$$$ must join exactly one of the chains coming from its descendants.

To maximize the overall sum of chain maximums, $$$u$$$ should greedily join the chain with the lowest current maximum. Let's say the smallest maximum among all incoming chains is $$$x$$$. If $$$a_u$$$ is greater than $$$x$$$, placing $$$u$$$ in this chain upgrades its maximum from $$$x$$$ to $$$a_u$$$. The old maximum $$$x$$$ doesn't disappear; it gets detached and becomes an extra node that we can use to form a new chain if we are allowed to use more than $$$\ell$$$ subsets. Conversely, if $$$a_u \le x$$$, placing $$$u$$$ in the chain doesn't improve the maximum at all, so $$$a_u$$$ itself becomes the detached spare node.

This process translates elegantly into a data structure approach. For each subtree, we can maintain the maximums of its active chains using a min-heap (a priority queue). When we process a node $$$u$$$, we merge all the heaps of its children. To do this efficiently, we always merge smaller heaps into larger heaps, a technique known as small-to-large merging. Once the children's paths are merged, we extract the absolute minimum element from $$$u$$$'s heap, compare it with $$$a_u$$$, push the larger of the two back into the active heap, and append the smaller one to a global list of extra available values.

By the time we finish processing the root, the root's heap will contain exactly $$$\ell$$$ elements, representing the maximums of the $$$\ell$$$ essential chains. The sum of these elements gives our optimal answer for exactly $$$\ell$$$ subsets. To find the answer for larger values of $$$k$$$, we simply sort our global list of extra values in descending order and greedily add the largest available extra to our running total for each additional subset allowed.

Because of the small-to-large merging, each element is moved between heaps at most $$$\mathcal{O}(\log n)$$$ times. Each heap operation takes logarithmic time, resulting in an overall time complexity of $$$\mathcal{O}(n \log^2 n)$$$, which comfortably passes the time limits.

#include <bits/stdc++.h>
 
using namespace std;
#define ll long long
 
void solve() {
    int n;
    cin >> n;
 
    vector<ll> a(n + 1);
    for(int i = 1; i <= n; i++) cin >> a[i];
 
    vector<int> p(n + 1);
    for(int i = 2; i <= n; i++) cin >> p[i];
 
    vector<priority_queue<ll, vector<ll>, greater<ll>>> pq(n + 1);
    vector<ll> av;
 
    for(int i = n; i >= 1; i--) {
        if(pq[i].empty()) pq[i].push(a[i]);
        else {
            ll x = pq[i].top();
            pq[i].pop();
            pq[i].push(max(x, a[i]));
            av.push_back(min(x, a[i]));
        }
 
        if(i > 1) {
            int par = p[i];
            if(pq[par].size() < pq[i].size()) swap(pq[par], pq[i]);
 
            while(!pq[i].empty()) {
                pq[par].push(pq[i].top());
                pq[i].pop();
            }
        }
    }
 
    int l = pq[1].size();
    ll sum = 0;
    
    while(!pq[1].empty()) {
        sum += pq[1].top();
        pq[1].pop();
    }
 
    vector<ll> ans(n + 1, -1);
    ans[l] = sum;
 
    sort(av.rbegin(), av.rend());
    for(int i = 0; i < av.size(); i++) {
        sum += av[i];
        ans[l + i + 1] = sum;
    }
 
    for(int k = 1; k <= n; k++) cout << ans[k] << " \n"[k == n];
}
 
int main() {
    int t;
    cin >> t;
    while(t--) solve();
}

• Excellent problem
• Good problem
• Average problem
• Bad problem
• Horrible problem