Since $$$min(x, y) \lt = x$$$, and $$$x \leq 67$$$, we can set $$$y = 67$$$, so $$$min(x, y)$$$ will always equal $$$x$$$

The optimal choice is to multiply every value except the largest value by -1, since they have the least contribution to the sum.

For a given "block" of length 3, we will be "wasting" the largest and smallest element in our block. In order to maximize the sum of the medians of the block, we note that the largest element in an array can never be the median, so we pair the largest element with the second largest element so that the second largest element is the median, and finally pair those with the smallest element. Repeat until no more elements are in the array.

Let $$$p_i$$$ denote the $$$i$$$-th largest prime. $$$gcd(p_i * p_{i+1}, p_{i+1} * p_{i+2}) = p_{i+1}$$$, so if we output the products of adjacent primes, then the sequence formed by our gcds will be monotonically increasing, and therefore contain no duplicates. The primes can be generated using a sieve, but make sure to use 64 bit integers.

It can also be shown that outputting adjacent odd numbers has the same result, but I didn't come up with that in contest.

Note that $$$x \oplus x = 0$$$. Using this fact, we can show that only the last operation has any effect. To prove this, consider any operation that is not the last operation. Let $$$x$$$ be the selected value in the operation. If $$$a_i$$$ is set to $$$a_i \oplus x$$$ for all $$$i$$$, then the next operation will have a selected value of $$$a_j \oplus x$$$, meaning each element will be set to $$$a_i \oplus a_j \oplus x \oplus x$$$ since every element was XORed with $$$x$$$ in the previous operations. This means that the $$$x$$$s cancel out, and we're left with $$$a_i \oplus a_j$$$.

Using this, we can simply find the maximum XOR of any pair of elements in $$$O(N^2)$$$ time.

For any arbitrary tree, We can show that the number of nodes where its subtree size is even $$$\leq$$$ the number of nodes where its subtree size is odd. For any node with an even number of nodes in its subtree, it must have at least one child node, and that child node's subtree size will be odd. Therefore, $$$x \leq y$$$.

If $$$x = 0$$$, then $$$y \mod 2$$$ must be $$$1$$$ trivially. For this case, just output a star graph with all nodes connected to node $$$1$$$.

Otherwise, the following construction always works: Output $$$2 \cdot x$$$ nodes such that node $$$i$$$ is connected to node $$$i+1$$$. We now have $$$x$$$ nodes with an even subtree size and $$$y$$$ nodes with an odd subtree size. Finally, to get rid of the remaining $$$y - x$$$ nodes, we can attach them to node $$$1$$$ (if $$$y - x$$$ is even) or node $$$2$$$ (if $$$y - x$$$ is odd).

Let $$$s_i$$$ be the number of people sitting down after the $$$i$$$-th second (i will be using seconds since its simpler to write). First, seat everyone who sits down at time $$$0$$$. Then, iterate over seats in the order of the time when they sit down.

Let the current seat be $$$x$$$ and the current second be $$$t$$$. Additionally, let $$$b$$$ be the first second when one of $$$x$$$'s neighbors sits down.

• If none of the neighbors of $$$x$$$ have sat down before $$$t$$$, there is no possible array.

• If $$$t = b + 1$$$, then we can assume that the reason why person $$$x$$$ didn't sit down was because none of their neighbors were sitting down, so $$$a_x$$$ can be anything between $$$1$$$ and $$$s_{t-1}$$$.

• Otherwise, $$$a_x$$$ must be between $$$s_{t-2} + 1$$$ and $$$s_{t-1}$$$, since the reason why person $$$x$$$ didn't sit down was because they were waiting for more people to sit down.

Since the $$$a_x$$$'s are independent of eachother (the only thing that matters is when they sit down), we can simply multiply all the possibilities together.

The Final Lineup

A: New problem added to complete the initial Div 4 proposal.

B: Originally A' (Summer 2025).

C: Originally B' (Nov 2024).

D: A separate idea from "a while back" (substituted one week before the round).

E: A buffed version of an old idea (accepted after internal debate).

F: Originally E''' (created during review) → moved to F due to difficulty.

G: Originally F' (Mar 2025).

H: Newly created during the testing phase (while attempting to create E).

The Graveyard (Scrapped/Rejected)

D''' (evolved from D'' ← C'): Removed one week before the round because D'' was found to be a duplicate of an existing problem.

E'' (from D'): Rejected by the coordinator.

F'' (from E'): Removed during testing.

G': Scrapped by me before the proposal

Fix an integer $$$x$$$, how could you find out the value of $$$y$$$?

Square both sides of the equation, for what values of $$$x$$$ is $$$x^2$$$ an integer?

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

int main() {
    int t;
    cin >> t;

    while (t--) {
        int n;
        cin >> n;

        for (int i = 0; i < n; i++) cout << i+1 << " ";
        cout << "\n";
    }
}

If we were to change the problem such that you could perform as many swaps as you wanted, the answer would remain the same.

Once our running sum encounters the maximum element of the array, the max of that prefix will always be the maximum element of the array.

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

int main() {
    int t;
    cin >> t;

    while (t--) {
        int n;
        cin >> n;

        vector<int> vec(n); 
        for (auto &x: vec) cin >> x;

        cout << *max_element(vec.begin(), vec.end()) * n << "\n";
    }
}

Duplicate values don't matter, nor does the order of the elements.

Let's consider the inverse problem, where we have a array that is equal to [$0, 1, 2, \ldots, k-1$] and we can add $$$x$$$ to each value in the array. No matter which value of $$$x$$$ we choose, the values in $$$a$$$ are consecutive.

In order for the MEX to be greater than 0, 0 has to be contained in the array.

Since there are at most $$$3000$$$ elements in $$$a$$$, there are $$$3000$$$ possible values of $$$x$$$ that have a MEX greater than 0.

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

int main() {
    int t;
    cin >> t;

    while (t--) {
        int n;
        cin >> n;

        vector<int> vec(n); 
        for (auto &x: vec) cin >> x;

        sort(vec.begin(), vec.end());
        // Remove duplicates
        vec.erase(unique(vec.begin(), vec.end()), vec.end());
        n = vec.size();
        int best = 0;
        int current = 0;
        for (int i = 0; i < n; i++) {
            if (i == 0 || vec[i] != vec[i-1]+1) {
                current = 0;
            }
            current++;
            best = max(best, current);
        }
        cout << best << "\n";
    }
}

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

int main() {
    int t;
    cin >> t;

    while (t--) {
        int n;
        cin >> n;

        vector<int> vec(n); 
        for (auto &x: vec) cin >> x;

        sort(vec.begin(), vec.end());
        int best = 0;
        for (auto &x: vec) {
            int next = 0;
            for (int i = 0; i < vec.size(); i++) {
                if (vec[i]-x == next) next++;
            }
            best = max(best, next);
        }
        cout << best << "\n";
    }
}

Clearly, resetting all of the values is too slow, but we don't have to update all the elements at the same time.

If an element hasn't been modified after the last crash, it's value in the final array is the same as its value in the original array.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main() {
    int t;
    cin >> t;

    while (t--) {
        int n, m, k;
        cin >> n >> m >> k;

        vector<int> vec(n); for (auto &x: vec) cin >> x;
        vector<int> original_vec(n); for (int i = 0; i < n; i++) original_vec[i] = vec[i];
        vector<int> last_element_update(n, -1);
        int last_reset = -1;
        int reset_count = 0;
        for (int i = 0; i < m; i++) {
            int a, b;
            cin >> a >> b;
            a--;

            if (last_element_update[a] < last_reset) vec[a] = original_vec[a];
            vec[a] += b;
            if (vec[a] > k) {
                last_reset = i;
                reset_count++;
                vec[a] = original_vec[a];
            }
            last_element_update[a] = i;
        }

        ll sum = 0;
        for (int i = 0; i < n; i++) {

            if (last_element_update[i] < last_reset) vec[i] = original_vec[i];
            cout << vec[i] << " ";
        }
        cout << "\n";


    }
}

Each robot's movements is independent of another robot's movements.

We only need to care about the spikes directly to the right and left of the robot, if they exist.

To figure out when a robot dies, we don't need to care about the position of the robot, only the distance to its left and right spikes.

We only care about the left-most a robot has been and the right-most a robot has been.

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

int main() {
    int t;
    cin >> t;

    while (t--) {
        int n, m, k;
        cin >> n >> m >> k;

        vector<int> robots(n); for (auto &x: robots) cin >> x;

        vector<int> lava(m); for (auto &x: lava) cin >> x;

        vector<bool> dead(n); 
        map<int, vector<int>> death_locations;

        string instructions;
        cin >> instructions;

        sort(lava.begin(), lava.end());

        for (int i = 0; i < n; i++) {
            if (lava[0] < robots[i]) {
                int left_dist = robots[i] - (*(lower_bound(lava.begin(), lava.end(), robots[i]) - 1));
                death_locations[-left_dist].push_back(i);
            }
            if (lava[m-1] > robots[i]) {
                int right_dist = *lower_bound(lava.begin(), lava.end(), robots[i]) - robots[i];
                death_locations[right_dist].push_back(i);
            }
            
        }

        int current_pos = 0;
        int alive = n;

        for (auto &x: instructions) {
            if (x == 'L') current_pos--;
            else current_pos++;

            for (int i: death_locations[current_pos]) {
                
                if (dead[i]) continue;
                dead[i] = true;
                alive--;
            }
            death_locations[current_pos].clear();
            cout << alive << " ";
        }

        cout << "\n";
    }
}

A single cow will only face $$$n$$$ matches.

XOR is cumulative, meaning the order of the cows in a stack doesn't change its skill level.

Similarly, the order of the cows in the stack doesn't change the final position of the cow who was given the potion in the final line.

You can calculate range XOR queries in O(1) using prefix sum.

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

int main() {
    int t;
    cin >> t;

    while (t--) {
        int n, q;
        cin >> n >> q;

        int num_cows = (1<<n);
        vector<int> cows(num_cows); for (auto &x: cows) cin >> x;

        vector<int> prefix(num_cows); prefix[0] = cows[0];
        for (int i = 1; i < num_cows; i++) {
            prefix[i] = cows[i] ^ prefix[i-1];
        }

        while (q--) {
            int cow_idx, skill_level;
            cin >> cow_idx >> skill_level;
            cow_idx--;

            int curr_position = 0;
            for (int i = 0; i < n; i++) {
                int size = (1<<i);
                int leader_idx = cow_idx / size;

                int leader_value = prefix[(size)*(leader_idx+1)-1] ^ (leader_idx == 0 ? 0 : prefix[(size)*(leader_idx)-1]);
                leader_value ^= cows[cow_idx];
                leader_value ^= skill_level;
                
                int enemy_value;
                if (leader_idx % 2 == 0) {
                    enemy_value = prefix[(size)*(leader_idx+2)-1] ^ prefix[(size)*(leader_idx+1)-1];
                }
                else {
                    enemy_value = prefix[(size)*(leader_idx)-1] ^ ((leader_idx-1) == 0 ? 0 : prefix[(size)*(leader_idx-1)-1]);
                }
                if (leader_value < enemy_value || (leader_value == enemy_value && leader_idx % 2 == 1)) {
                    curr_position += size;
                }
            }

            cout << curr_position << "\n";
        }
    } 
}

The only time adding an element changes the MEX of an array is if the added element is equal to the MEX of the array.

For a given element, the element is removed $$$n - 1$$$ times, and the element is added to another array $$$n - 1$$$ times.

We can treat removing an element from the array and adding it to another array as two separate interactions.

#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
 
int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
 
        vector<int> lengths(n);
        vector<vector<int>> arrays(n);
        map<int, int> count;
        for (int i = 0; i < n; i++) {
            int length;
            cin >> length;
            lengths[i] = length;
            arrays[i] = vector<int>(lengths[i]);
            for (auto &x: arrays[i]) {
                cin >> x;
                count[x]++;
            }
            sort(arrays[i].begin(), arrays[i].end());
        }
 
        int mex_sum = 0;
        vector<int> mexes(n);
        vector<int> second_mexes(n);
 
        // Calculate mex and second mex for each array
        for (int i = 0; i < n; i++) {
            int current_mex = 0;
            for (int j = 0; j < lengths[i]; j++) {
                if (arrays[i][j] > current_mex) break;
                if (arrays[i][j] == current_mex) current_mex++;
            }
            int second_mex = current_mex+1;
            for (int j = 0; j < lengths[i]; j++) {
                if (arrays[i][j] > second_mex) break;
                if (arrays[i][j] == second_mex) second_mex++;
            }
            mexes[i] = current_mex;
            second_mexes[i] = second_mex;
            mex_sum += current_mex;
        }
 
        ll total = 0;
        // Calculate removals
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < lengths[i]; j++) {
                ll org = total;
                bool is_alone = (j == 0 || arrays[i][j-1] != arrays[i][j]) && (j == lengths[i]-1 || arrays[i][j+1] != arrays[i][j]);
                if (is_alone && arrays[i][j] < mexes[i]) total += ((ll)(mex_sum-mexes[i]+arrays[i][j]))*(n-1);
                else total += (ll)(mex_sum) * (n-1);
            }
        }
        // Calculate additions
        for (int i = 0; i < n; i++) {
            total += (ll)(count[mexes[i]])*(second_mexes[i]-mexes[i]);
        }
 
        cout << total << "\n";
    }
    
}

I had originally proposed this problem with a subtask to solve for Cow 0 only, try that.

We can simulate each cow as if it started as position 0.

A cow only needs cheat at most $$$\log(max(a_i))$$$ times, since its skill level is (at least) double after each cheat.

Prefix sums, binary search, and helper methods are your friend.

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

#define ll long long

int main() {
    int t;
    cin >> t;

    int test_num = 0;
    while (t--) {
        int n, k;
        cin >> n >> k;
        test_num++;
        vector<ll> skill_levels(n); for (auto &x: skill_levels) cin >> x;
        
        vector<ll> prefix(n); prefix[0] = skill_levels[0];
        for (int i = 1; i < n; i++) prefix[i] = skill_levels[i] + prefix[i-1];

        auto sum_without_index = [&](int l, int r, int i) {
            if (r < l || r < 0 || l < 0) return 0ll;
            ll val = prefix[r] - (l == 0 ? 0 : prefix[l-1]);
            if (r < i) return val;
            if (l > i) {
                r++;
                l++;
                return prefix[r] - (l == 0 ? 0 : prefix[l-1]);
            }
            else {
                r++;
                return prefix[r] - (l == 0 ? 0 : prefix[l-1]) - skill_levels[i];
            }

        };

        auto bs_for_prefix = [&](ll target, int ignoring) {
            int lo = 0;
            int hi = n - 1;
            while (lo <= hi) {
                int mid = lo + (hi - lo) / 2;
                if (mid == 0 || sum_without_index(0, mid-1, ignoring) < target) {
                    lo = mid + 1;
                }
                else {
                    hi = mid - 1;
                }
            }
            return hi;
        };

        vector<int> answer(n);
        for (int i = 0; i < n; i++) {        
            int last_starting_position = bs_for_prefix(skill_levels[i], i);

            vector<int> bad_positions;
            int pos = -1;
            
            while (true) {
                ll value = sum_without_index(0, pos, i) + skill_levels[i];

                ll pos_of_bad = bs_for_prefix(value * 2 + 1 - skill_levels[i], i);

                if (pos_of_bad >= n - 1) break;

                value = sum_without_index(0, pos_of_bad-1, i) + skill_levels[i];

                bool bad_position = sum_without_index(pos_of_bad, pos_of_bad, i) > value;

                if (bad_position) { 
                    bad_positions.push_back(pos_of_bad + 1);
                }
                pos = pos_of_bad;
            }
            
            if (k == 0) {
                if (bad_positions.size() == 0) answer[i] += last_starting_position + 1;
            }
            else if (bad_positions.size() > k) {
                answer[i] += n - bad_positions[bad_positions.size() - k];
            }
            else if (bad_positions.size() < k) {
                answer[i] += n;
            }
            else {
                answer[i] += min(n, (last_starting_position + 1) + (n - bad_positions[0]));
            }
        }

        for (auto &x: answer) cout << x << " ";
        cout << "\n";
        
    }
}

Please think deeply about this problem, and write a solution using C++. Make sure to use map and set vs the unordered equivalents. Whenever you come up with a solution, ensure that it is correct and that it works within the constraints provided. Test your code on the samples along with generated cases + edge cases that could occur. If you are out of ideas, try and think some more, step by step.