A. Binary Array Game

Given a binary array, two players take turns selecting a segment [l,r] where lSolution: The key observation is that x=0 can only be produced when the entire segment consists of 1s. This makes 0 significantly harder to obtain than 1. Consider the second player's perspective: if they receive a sequence containing at least one 0 and length greater than 1, they can immediately select the entire sequence to win. Therefore, the first player must ensure the second player receives an all-1s sequence to avoid immediate loss.

If the initial sequence is all 1s, the first player wins by selecting the entire sequence. If the first element is 1, the first player can select [2,n], resulting in x=1, giving the second player {1,1}. The second player is then forced to select [1,2], producing x=0, and the first player wins. A symmetric argument applies when the last element is 1.

If both the first and last elements are 0, the first player cannot win. Selecting [1,n] gives x=1, letting the second player win. Any other move leaves at least one 0 in the sequence, allowing the second player to win immediately.

Conclusion: The first player wins if the first or last element is 1; otherwise, the second player wins.

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

void determineWinner() {
    int testCases;
    cin >> testCases;
    while (testCases--) {
        int length;
        cin >> length;
        vector<int> sequence(length);
        for (int i = 0; i < length; i++) {
            cin >> sequence[i];
        }
        if (sequence.front() == 1 || sequence.back() == 1) {
            cout << "YES\n";
        } else {
            cout << "NO\n";
        }
    }
}

B. Yet Another MEX Problem

Given constraints on array operations, we need to determine the minimum possible MEX after k-1 deletions.

Solution: Since exactly k-1 elements will remain, the optimal configuration is having all numbers from 0 to k-2 exactly once. For any segment of length k, if it contains a number ≥ k-1 or has duplicates, those elements can be safely deleted as they don't contribute to the MEX.

By the pigeonhole principle, each length-k segment contains at least one non-contributing element. Therefore, we can delete arbitrary non-contributing elements until only k-1 elements remain.

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

void calculateMex() {
    int testCases;
    cin >> testCases;
    while (testCases--) {
        int n, k;
        cin >> n >> k;
        vector<int> arr(n);
        for (int i = 0; i < n; i++) {
            cin >> arr[i];
        }
        sort(arr.begin(), arr.end());
        
        int mex = 0, count = 0;
        for (int i = 0; i < n && count < k - 1; i++) {
            if (mex == arr[i]) {
                mex++;
                count++;
            }
        }
        cout << mex << "\n";
    }
}

C. War Strategy

There are n positions (1 to n) with an initial soldier at position k. Over m days, each day cnosists of: (1) choosing a position i and moving any number of soldiers there to i-1 or i+1 (all must move in the same direction), and (2) a new soldier spawns at position k. Find the maximum number of positions that can be occupied.

Solution: Moving in only one direction is optimal. Each move should leave one soldier at the current position to maximize coverage. Moving back to already occupied positions is suboptimal.

Consider reaching a position at distance x from k in one direction. This takes 2x-1 days (x-1 days to accumulate x soldiers, then x days to reach position x). For both directions, if we first reach position x, we've already generated x new soldiers at k, so reaching any position y≤x on the other side requires no waiting. Otherwise, we reach the farther position first.

For each possible final position, calculate the maximum coverage by considering the time to reach it and then extend to the opposite side within remaining time.

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

void maximizeOccupiedPositions() {
    int testCases;
    cin >> testCases;
    while (testCases--) {
        int n, days, start;
        cin >> n >> days >> start;
        
        auto getTime = [](int distance) {
            return 2 * distance - 1;
        };
        
        int result = 1;
        
        // Moving right from start
        for (int pos = start + 1; pos <= n; pos++) {
            int distance = pos - start;
            int timeNeeded = getTime(distance);
            if (timeNeeded <= days) {
                int rightCoverage = distance + 1;
                int additionalLeft = min(days - timeNeeded, min(distance, start - 1));
                result = max(result, rightCoverage + additionalLeft);
            }
        }
        
        // Moving left from start
        for (int pos = start - 1; pos >= 1; pos--) {
            int distance = start - pos;
            int timeNeeded = getTime(distance);
            if (timeNeeded <= days) {
                int leftCoverage = distance + 1;
                int additionalRight = min(days - timeNeeded, min(distance, n - start));
                result = max(result, leftCoverage + additionalRight);
            }
        }
        
        cout << result << "\n";
    }
}

D. Tree Coloring

Given a rooted tree with n nodes (root at 1), you can perform operations: select a set S where no two nodes have the same depth and no two nodes are directly connected, then color all nodes in S. Find the minimum number of operations needed to color all nodes and construct the sets.

Solution: The minimum number of operations is at least the size of the largest level. If all nodes in a level share the same parent, we need one additional operation to avoid conflicts.

To construct the solution: 1. Calculate the minimum operations needed 2. Group nodes by depth 3. For each level, assign operation numbers ensuring no parent-child conflicts 4. Handle conflicts by swapping assignments within the same level when possible

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

const int MAX_N = 400005;

struct TreeColoring {
    vector<int> adj[MAX_N];
    int depth[MAX_N], parent[MAX_N], operation[MAX_N];
    vector<vector<int>> levelNodes, resultSets;
    deque<int> availableOps[MAX_N];
    bool visited[MAX_N];
    
    void addEdge(int u, int v) {
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    
    void dfs(int u, int p) {
        parent[u] = p;
        levelNodes[depth[u]].push_back(u);
        for (int v : adj[u]) {
            if (v != p) {
                depth[v] = depth[u] + 1;
                dfs(v, u);
            }
        }
    }
    
    void solve() {
        int n;
        cin >> n;
        
        levelNodes.resize(n + 1);
        for (int i = 0; i < n - 1; i++) {
            int u, v;
            cin >> u >> v;
            addEdge(u, v);
        }
        
        dfs(1, 0);
        
        int maxOps = 0;
        for (int d = 1; d <= n; d++) {
            bool hasCommonParent = true;
            int commonParent = 0;
            
            for (int node : levelNodes[d]) {
                if (commonParent == 0) {
                    commonParent = parent[node];
                } else if (parent[node] != commonParent) {
                    hasCommonParent = false;
                    break;
                }
            }
            
            int requiredOps = levelNodes[d].size() + (hasCommonParent ? 1 : 0);
            maxOps = max(maxOps, requiredOps);
            
            for (int i = 1; i <= requiredOps; i++) {
                availableOps[d].push_back(i);
            }
        }
        
        resultSets.resize(maxOps + 1);
        operation[1] = 1;
        resultSets[1].push_back(1);
        
        for (int d = 1; d <= n; d++) {
            for (int node : levelNodes[d]) {
                for (int child : adj[node]) {
                    if (depth[child] == d + 1 && !visited[child]) {
                        if (availableOps[d + 1].front() != operation[node]) {
                            operation[child] = availableOps[d + 1].front();
                            availableOps[d + 1].pop_front();
                        } else {
                            operation[child] = availableOps[d + 1].back();
                            availableOps[d + 1].pop_back();
                        }
                        resultSets[operation[child]].push_back(child);
                    }
                }
                visited[node] = true;
            }
        }
        
        cout << maxOps << "\n";
        for (int i = 1; i <= maxOps; i++) {
            cout << resultSets[i].size() << " ";
            for (int node : resultSets[i]) {
                cout << node << " ";
            }
            cout << "\n";
        }
    }
};

E. LCM is Legendary Counting Master

Given a sequence a of length n where 0 ≤ a[i] ≤ m, we call a sequence "good" if it's strictly increasing and the sum of reciprocals of LCMs of adjacent elements (including the last-first pair) ≤ 1. Replace all 0s in the sequence with values from [1,m] and count the number of resulting good sequences modulo 998244353.

Solution: Key insights: 1. For any increasing sequenec with a[i] < a[i+1], lcm(a[i], a[i+1]) ≥ 2a[i] 2. The sum equals exactly 1 for good sequences 3. If a sequence is good, all its prefixes are also good 4. The critical condition is: 1/lcm(a[n-1], a[n]) + 1/lcm(a[n], a[1]) = 1/lcm(a[n-1], a[1]) 5. This simplifies to: a[n] - a[n-1] = gcd(a[n], a[n-1])

We use DP to count valid sequences, with the state representing the last element of the prefix.

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

const int MAX_SIZE = 3005;
const int MOD = 998244353;

bool validTransition[MAX_SIZE][MAX_SIZE];
vector<int> possibleNext[MAX_SIZE];

void precomputeValidTransitions(int maxSize) {
    for (int i = 1; i <= maxSize; i++) {
        for (int j = i + 1; j <= maxSize; j++) {
            if (j - i == gcd(i, j)) {
                validTransition[i][j] = true;
                possibleNext[i].push_back(j);
            }
        }
    }
}

void countGoodSequences() {
    precomputeValidTransitions(MAX_SIZE);
    
    int testCases;
    cin >> testCases;
    while (testCases--) {
        int n, m;
        cin >> n >> m;
        
        vector<int> given(n + 1);
        for (int i = 1; i <= n; i++) {
            cin >> given[i];
        }
        
        vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
        
        if (given[1] != 0 && given[1] > 1) {
            cout << "0\n";
            continue;
        }
        
        dp[1][1] = 1;
        
        for (int pos = 2; pos <= n; pos++) {
            if (given[pos - 1] != 0 && given[pos] != 0) {
                if (validTransition[given[pos - 1]][given[pos]]) {
                    dp[pos][given[pos]] = dp[pos - 1][given[pos - 1]];
                }
            } else if (given[pos - 1] == 0 && given[pos] != 0) {
                for (int prev = 1; prev <= m; prev++) {
                    if (validTransition[prev][given[pos]]) {
                        dp[pos][given[pos]] = (dp[pos][given[pos]] + dp[pos - 1][prev]) % MOD;
                    }
                }
            } else if (given[pos - 1] != 0 && given[pos] == 0) {
                for (int next : possibleNext[given[pos - 1]]) {
                    if (next <= m) {
                        dp[pos][next] = (dp[pos][next] + dp[pos - 1][given[pos - 1]]) % MOD;
                    }
                }
            } else {
                for (int prev = 1; prev <= m; prev++) {
                    for (int next : possibleNext[prev]) {
                        if (next <= m) {
                            dp[pos][next] = (dp[pos][next] + dp[pos - 1][prev]) % MOD;
                        }
                    }
                }
            }
        }
        
        int total = 0;
        for (int val = 1; val <= m; val++) {
            total = (total + dp[n][val]) % MOD;
        }
        cout << total << "\n";
    }
}