Contest Overview

This round was relatively straightforward, so this editorial will focus on both the technical problem solutions and the interesting sequence of events during the contest.

Problem A - Subset Mex

Problem Statement: Given a set a with |a| = n, partition it into two sets A and B to maximize mex(A) + mex(B). Multiple test cases.

Constraints: n ∈ [1, 100], aᵢ ∈ [0, 100], T ∈ [1, 100]

Solution: A greedy approach works well here. The two sets' mex values should progress together. When one set cannot accommodate the next integer, that set stops. When both stop, we've reached the maximum possible sum. Simply count occurrences and find the smallest integer that appears less than twice, then find the next integer not present at all.

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

const int MAXV = 100;

int main() {
    int testCount;
    cin >> testCount;
    while (testCount--) {
        int len;
        cin >> len;
        vector<int> arr(len);
        for (int i = 0; i < len; i++) cin >> arr[i];
        sort(arr.begin(), arr.end());
        
        vector<int> freq(MAXV + 1, 0);
        for (int val : arr) freq[val]++;
        
        int firstMissing = 0;
        for (int i = 0; i <= MAXV; i++) {
            if (freq[i] < 2) {
                firstMissing = i;
                break;
            }
        }
        
        for (int i = firstMissing; i <= MAXV; i++) {
            if (freq[i] == 0) {
                cout << firstMissing + i << "\n";
                break;
            }
        }
    }
    return 0;
}

Problem B - Maximum Product

Problem Statement: Given n integers (can be positive, negative, or zero), find the maximum product of any 5 numbers. Multiple test cases.

Constraints: n ∈ [5, 10⁵], Σn ≤ 2 × 10⁵

Solution: Consider two cases: presence of zero, and absence of zero.

If zero is present, the answer is 0 (or higher with other combinations).

Otherwise, enumerate the count of positive numbers used, then sort both positive and negative arrays. The key insight is that if we're using an odd number of negatives, we need to take the smallest positives to minimize the product reduction.

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

int main() {
    int testCount;
    cin >> testCount;
    while (testCount--) {
        int len;
        cin >> len;
        vector<int> positives, negatives;
        int64 answer = LLONG_MIN;
        
        for (int i = 0; i < len; i++) {
            int x;
            cin >> x;
            if (x > 0) positives.push_back(x);
            else if (x == 0) answer = 0;
            else negatives.push_back(x);
        }
        
        sort(positives.begin(), positives.end(), greater<int>());
        sort(negatives.begin(), negatives.end());
        
        for (int posUsed = 0; posUsed <= 5; posUsed++) {
            int negUsed = 5 - posUsed;
            if (posUsed <= (int)positives.size() && negUsed <= (int)negatives.size()) {
                int64 product = 1;
                
                if (negUsed & 1) {
                    for (int j = (int)positives.size() - 1; j >= (int)positives.size() - posUsed; j--)
                        product *= positives[j];
                    for (int j = (int)negatives.size() - 1; j >= (int)negatives.size() - negUsed; j--)
                        product *= negatives[j];
                } else {
                    for (int j = 0; j < posUsed; j++)
                        product *= positives[j];
                    for (int j = 0; j < negUsed; j++)
                        product *= negatives[j];
                }
                answer = max(answer, product);
            }
        }
        cout << answer << "\n";
    }
    return 0;
}

Problem C - Link Cut Centroids

Problem Statement: Given a tree with n nodes, find a way to delete one edge and add another edge to make the centroid unique. Multiple test cases.

Constraints: n ∈ [3, 10⁵], Σn ≤ 10⁵

Solution: First, find all current centroids. If there's only one, output nothing.

If there are two centroids, they must be adjacent. Choose one as root, then the other becomes a child. Since n ≥ 3, the centroid child must have its own children. Delete an edge from the child centroid to one of its children, and reconnect that child to the root. This ensures the original root remains a centroid (with reduced subtree size), while the child centroid can no longer be a centroid. No other node can become a centroid since they remain at the same distance from the root.

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

const int MAXN = 100000;
int n;
vector<int> graph[MAXN + 1];
int subtreeSize[MAXN + 1];

void computeSizes(int node, int parent) {
    subtreeSize[node] = 1;
    for (int neighbor : graph[node]) {
        if (neighbor == parent) continue;
        computeSizes(neighbor, node);
        subtreeSize[node] += subtreeSize[neighbor];
    }
}

int main() {
    int testCount;
    cin >> testCount;
    while (testCount--) {
        cin >> n;
        for (int i = 1; i <= n; i++) graph[i].clear();
        
        for (int i = 1; i < n; i++) {
            int u, v;
            cin >> u >> v;
            graph[u].push_back(v);
            graph[v].push_back(u);
        }
        
        computeSizes(1, 0);
        vector<int> centroids;
        
        for (int i = 1; i <= n; i++) {
            bool valid = true;
            int maxChild = 0;
            int sum = 1;
            
            for (int neighbor : graph[i]) {
                if (subtreeSize[neighbor] > subtreeSize[i]) continue;
                valid &= (subtreeSize[neighbor] <= n / 2);
                maxChild = max(maxChild, subtreeSize[neighbor]);
                sum += subtreeSize[neighbor];
            }
            valid &= (n - sum <= n / 2);
            
            if (valid) centroids.push_back(i);
        }
        
        if (centroids.size() == 1) {
            cout << 1 << " " << graph[1][0] << "\n";
            cout << 1 << " " << graph[1][0] << "\n";
        } else {
            int rootCentroid = centroids[0];
            int otherCentroid = centroids[1];
            int childNode = graph[rootCentroid][0] == otherCentroid 
                          ? graph[rootCentroid][1] 
                          : graph[rootCentroid][0];
            cout << rootCentroid << " " << childNode << "\n";
            cout << otherCentroid << " " << childNode << "\n";
        }
    }
    return 0;
}

Problem D - Three Sequences

Problem Statement: Given an array a of length n, construct two arrays b and c such that aᵢ = bᵢ + cᵢ, b is non-decreasing, and c is non-increasing. Minimize max(bᵢ, cᵢ). Then handle q range addition queries.

Constraints: n, q ∈ [1, 10⁵]

Solution: First, establish a key observation: for any valid construction, max(bᵢ, cᵢ) = max(bₙ, c₁). When aᵢ₊₁ - aᵢ ≥ 0, we should increase b; otherwise, decrease c. This minimizes b's total growth.

Let Δᵢ = aᵢ₊₁ - aᵢ, and let Σ = Σ[Δᵢ ≥ 0]Δᵢ. We need to minimize max(b₁ + Σ, a₁ - b₁).

Since these two terms sum to a constant (a₁ + Σ), they're minimized when they're equal. Solving b₁ = (a₁ - Σ) / 2 gives us the optimal split. Since b₁ must be integer, we round to the nearest integer.

For range additions, only two deltas change, so we can maintain the answer in O(1) time per query.

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

const int MAXN = 100000;
int n;
int64 arr[MAXN + 1];
int64 delta[MAXN + 1];

int64 findOptimal(int64 base, int64 increment) {
    int64 best = LLONG_MAX;
    for (int64 offset = base - 3; offset <= base + 3; offset++) {
        best = min(best, max(offset + increment, arr[1] - offset));
    }
    return best;
}

int main() {
    int testCount = 1;
    while (testCount--) {
        cin >> n;
        for (int i = 1; i <= n; i++) scanf("%lld", &arr[i]);
        
        for (int i = 1; i < n; i++) delta[i] = arr[i + 1] - arr[i];
        
        int64 positiveSum = 0;
        for (int i = 1; i < n; i++) {
            if (delta[i] > 0) positiveSum += delta[i];
        }
        
        cout << findOptimal((arr[1] - positiveSum) / 2, positiveSum) << "\n";
        
        int q;
        cin >> q;
        while (q--) {
            int l, r;
            int64 val;
            scanf("%d%d%lld", &l, &r, &val);
            
            if (l == 1) arr[1] += val;
            
            if (l > 1 && delta[l - 1] > 0) positiveSum -= delta[l - 1];
            if (r < n && delta[r] > 0) positiveSum -= delta[r];
            
            delta[l - 1] += val;
            delta[r] -= val;
            
            if (l > 1 && delta[l - 1] > 0) positiveSum += delta[l - 1];
            if (r < n && delta[r] > 0) positiveSum += delta[r];
            
            printf("%lld\n", findOptimal((arr[1] - positiveSum) / 2, positiveSum));
        }
    }
    return 0;
}

Problem E - Deleting Numbers

Problem Statement: This is an interactive problem. Given n, initially A = [1, n] ∩ ℤ. You have 3 operations:

1. Query: count how many multiples of a exist in A (a ∈ [1, n])
2. Query and delete: count multiples of a in A (a ∈ [2, n]), then delete all multiples of a except a itself
3. Answer: gues the hidden value x ∈ A

Find the hidden x within 10⁴ operations.

Constraints: n ∈ [2, 10⁵]

Solution: The key insight is combining operations (1) and (2) to check divisibility. Use the strategy from classical divisor problems: split primes into small and large categories. Every number has at most one large prime factor.

First, handle small prime factors. For each prime p ≤ √n, use operation (2) to mark it, then check each power of p using operation (1). After processing, if x > 1 after removing small factors, we know x has a large prime factor.

Case 1: Small factor product > 1. Simply check each large prime to find which one multiplies with the small factor product to equal x.

Case 2: Small factor product = 1. Use block deletion on large primes. If deleting a block reduces the set size by the expected amount, x is not in that block; otherwise, x is in that block and can be found with individual checks.

The total operations approximately equal: π(√n) + τ(√n) + π(n) + 2√(π(n) - π(√n))

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

bool isPrime(int x) {
    if (x < 2) return false;
    for (int i = 2; i * i <= x; i++)
        if (x % i == 0) return false;
    return true;
}

int queryA(int x) {
    printf("A %d\n", x);
    fflush(stdout);
    cin >> x;
    return x;
}

int queryB(int x) {
    printf("B %d\n", x);
    fflush(stdout);
    cin >> x;
    return x;
}

void answer(int x) {
    printf("C %d\n", x);
    fflush(stdout);
    exit(0);
}

int main() {
    int n;
    cin >> n;
    
    if (n == 1) answer(1);
    
    vector<int> primes;
    for (int i = 2; i <= n; i++)
        if (isPrime(i)) primes.push_back(i);
    
    long long x = 1;
    int limit = sqrt(n);
    
    for (int i = 0; primes[i] <= limit; i++) {
        queryB(primes[i]);
        int current = 1;
        while (current * primes[i] <= n) current *= primes[i];
        
        while (current > 1) {
            if (queryA(current) == 1) {
                x *= current;
                break;
            }
            current /= primes[i];
        }
    }
    
    vector<int> largePrimes;
    for (int p : primes)
        if (p > limit) largePrimes.push_back(p);
    
    if (x == 1) {
        int remaining = queryA(1);
        for (int i = 0; i < (int)largePrimes.size(); i += 100) {
            int blockEnd = min(i + 100, (int)largePrimes.size());
            for (int j = i; j < blockEnd; j++) queryB(largePrimes[j]);
            
            int newRemaining = queryA(1);
            if (remaining - newRemaining == blockEnd - i) {
                remaining = newRemaining;
            } else {
                for (int j = i; j < blockEnd; j++)
                    if (queryA(largePrimes[j]) == 1) {
                        x = largePrimes[j];
                        break;
                    }
                break;
            }
        }
    } else {
        for (int p : largePrimes) {
            if (1LL * x * p <= n && queryA(x * p) == 1) {
                x *= p;
                break;
            }
        }
    }
    
    answer(x);
    return 0;
}

Contest Reflections

The contest presented an interesting sequence of events. During the final minutes, after submitting problem E and receiving a wrong answer, attention turned to the rating predictor. Rather than risking a rating increase, several unsuccessful hack attempts were made. When the contest concluded with the predictor showing an unexpected +130 points increase, it resulted in a final rating of 2096—surprisingly close to the intended target.

Upon waking the next day, the final rating change showed +127, landing at 2099. This near-perfect outcome demonstrated effective rating management strategies.

The problems in this round ranged from straightforward greedy approaches to more sophisticated interactive techniques. Problems A through D tested fundamental algorithmic skills, while Problem E required creative use of prime factorization and block-based elimination in an interactive setting.