The problem requires the remaining characters in the numerator $$$p$$$ to form exactly the string six after completely cancelling out the denominator $$$q$$$.

This means the collection of characters in $$$p$$$ must be exactly the characters in $$$q$$$ combined with the letters s, i, and x. Therefore, if we append the string six to $$$q$$$, the modified string $$$q$$$ must be an exact anagram of $$$p$$$. We can check this condition by sorting both strings and verifying if they are identical, or by comparing their character frequency counts.

Time Complexity: $$$\mathcal{O}(n + m)$$$.

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

int main(){

    int t;
    cin >> t;

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

        q += "six";

        vector<int> pc(255, 0), qc(255, 0);
        for(auto& z : p) pc[z]++;
        for(auto& z : q) qc[z]++;

        if(pc == qc) cout << "YES\n";
        else cout << "NO\n";
    }

    return 0;
}

• Best Problem
• Good Problem
• Okay Problem
• Bad Problem
• Didn't Solve

Let's consider a strategy where Bob plays the exact same move in all $$$x+y+z$$$ rounds.

If Bob chooses to always play the move that beats Alice's most frequent choice, the number of rounds he wins will be exactly the maximum of $$$x, y,$$$ and $$$z$$$.

Alice will only win the rounds where she plays the move that beats Bob's choice. The number of rounds she wins will correspond to one of the other two frequencies.

Since the maximum frequency is at least as large as the remaining frequencies, the number of rounds Bob wins will always be at least the number of rounds Alice wins. Therefore, the optimal sequence is to simply find the maximum of $$$x, y,$$$ and $$$z$$$ and output its counter-move $$$x+y+z$$$ times.

Time Complexity: $$$\mathcal{O}(x+y+z)$$$.

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

int main(){

    int t;
    cin >> t;

    while(t--){
        vector<int> a(3);
        cin >> a[0] >> a[1] >> a[2];

        string s = "PRS";

        int total = a[0] + a[1] + a[2];
        for(int i = 0; i < total; i++){
            cout << s[max_element(a.begin(), a.end()) - a.begin()];
        }

        cout << '\n';
    }

    return 0;
}

• Best Problem
• Good Problem
• Okay Problem
• Bad Problem
• Didn't Solve

Let's analyze how the total mass of the array changes during an operation.

When we choose to operate on an inner core ($$$1 \lt i \lt k$$$), its mass $$$a_i$$$ is partitioned into two parts $$$x$$$ and $$$y$$$ ($$$x, y \ge 1$$$), which are completely absorbed by the left and right neighbors. Thus, the total mass of the array is perfectly conserved.

However, if we operate on an edge core ($$$i = 1$$$ or $$$i = k$$$), one of the split parts falls out of bounds. This means we permanently lose at least $$$1$$$ unit of mass to the environment.

To reduce the array to a single core, we must eventually reach a state with exactly $$$2$$$ cores. To merge them, we are forced to operate on one of them. Since both are edge cores at that point, it is strictly impossible to avoid losing at least $$$1$$$ unit of mass. Therefore, the theoretical maximum final mass is bounded by $$$\sum_{i=1}^n a_i - 1$$$.

Now, can we always achieve this upper bound? Let's classify the initial state into three cases:

Case 1: All initial elements are $$$1$$$. The operation strictly requires an element to be $$$\ge 2$$$. No moves can be made, so it is impossible to reduce the array. In this case, we print $$$-1$$$.

Case 2: There exists at least one inner element $$$a_i \ge 2$$$ ($$$1 \lt i \lt n$$$). We can choose this inner core for our first operation. Because $$$x \ge 1$$$ and $$$y \ge 1$$$, we pass at least $$$1$$$ unit of mass to both its left and right neighbors. Since every core initially has a mass of at least $$$1$$$, these neighbors will now have a mass of at least $$$2$$$.

This means we can continue expanding outwards, exclusively operating on inner cores. We can reduce the entire array down to $$$2$$$ elements without ever losing mass to the environment. The only mass lost is the unavoidable $$$1$$$ unit at the very end. The answer is exactly $$$\sum_{i=1}^n a_i - 1$$$.

Case 3: All inner elements are $$$1$$$, but an edge element is $$$\ge 2$$$ (or $$$n = 2$$$). Because there are no valid inner cores to start with, we are forced to operate on an edge core. To minimize our losses, we split it into $$$1$$$ (which is lost to the void) and $$$a_i - 1$$$ (which is added to the adjacent inner $$$1$$$). That inner core now has a mass of $$$a_i \ge 2$$$ and effectively becomes the new edge of the remaining array. To clear out all $$$n-2$$$ inner $$$1$$$s, we must repeat this "rolling" process, paying a toll of exactly $$$1$$$ unit of mass for every inner element we consume. In total, we lose $$$n-2$$$ mass to clear the inner elements, plus the $$$1$$$ mass lost during the final merge. The total mass lost is $$$n-1$$$. The final mass is $$$\sum_{i=1}^n a_i - (n - 1) = a_1 + a_n - 1$$$.

Time Complexity: $$$\mathcal{O}(n)$$$.

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

int main(){

    int t;
    cin >> t;

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

        vector<int> a(n);
        for(auto& z : a) cin >> z;

        int sum = accumulate(a.begin(), a.end(), 0);
        if(sum == n) cout << -1 << '\n';
        else if(sum == n - 2 + a[0] + a[n - 1]) cout << a[0] + a[n - 1] - 1 << '\n';
        else cout << sum - 1 << '\n';
    }

    return 0;
}

• Best Problem
• Good Problem
• Okay Problem
• Bad Problem
• Didn't Solve

Let $$$b_1 \le b_2 \le \dots \le b_n$$$ be the sorted version of the initial array $$$a$$$. To make all elements equal, our goal is to reduce the gap $$$b_{i+1} - b_i$$$ to zero for all $$$1 \le i \lt n$$$.

To close the gap between $$$b_i$$$ and $$$b_{i+1}$$$ by $$$1$$$ unit, they must move closer relative to each other. Suppose we decide to increase $$$b_i$$$. If we do not also increase all elements to its left ($$$b_1 \dots b_{i-1}$$$), we will successfully close the gap on the right, but we will simultaneously widen the gaps within the left group. Therefore, to guarantee we never undo our progress or create new gaps, any time we shift elements to close a specific gap $$$b_{i+1} - b_i$$$, we must shift the entire group of elements on one side of that gap as a single rigid block.

Now, to reduce $$$b_{i+1} - b_i$$$ by $$$1$$$ unit, we only have two optimal choices:

1. Lock the prefix $$$b_1 \dots b_i$$$ (incurring a cost of $$$i$$$) and decrease the entire suffix $$$b_{i+1} \dots b_n$$$.
2. Lock the suffix $$$b_{i+1} \dots b_n$$$ (incurring a cost of $$$n-i$$$) and increase the entire prefix $$$b_1 \dots b_i$$$.

Since these choices are independent for every gap, we can greedily take the cheaper option. The minimum cost to close the gap $$$b_{i+1} - b_i$$$ by $$$1$$$ unit is exactly $$$\min(i, n-i)$$$. Summing this over all gaps in the array, the minimum possible total cost is exactly:

To find the minimum number of operations needed, note that in any single operation, an element's value changes by $$$+1, -1$$$, or $$$0$$$. Therefore, the absolute maximum distance in the array, which is initially $$$b_n - b_1$$$, can decrease by at most $$$1$$$ in a single operation. To make all elements equal, this distance must be reduced to $$$0$$$. Thus, we strictly need at least $$$b_n - b_1$$$ operations.

Observe that in any operation, we are either increasing some prefix by $$$1$$$ or decreasing some suffix by $$$1$$$. In any case, the value of $$$b_n - b_1$$$ decreases by $$$1$$$. This guarantees that the maximum span shrinks in every operation, achieving the minimum cost in exactly $$$b_n - b_1$$$ operations.

Time Complexity: $$$\mathcal{O}(n \log n)$$$.

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

int main(){

    int t;
    cin >> t;

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

        vector<int> a(n);
        for(auto& z : a) cin >> z;

        sort(a.begin(), a.end());
        
        long long cost = 0;
        for(int i = 0; i < n - 1; i++){
            cost += 1ll * (a[i + 1] - a[i]) * min(i + 1, n - i - 1);
        }

        cout << cost << ' ' << a[n - 1] - a[0] << '\n';
    }

    return 0;
}

• Best Problem
• Good Problem
• Okay Problem
• Bad Problem
• Didn't Solve

Let's define a new array $$$b$$$ such that $$$b_i = (-1)^{i-1} a_i$$$.

Now, let's take a look at how the given operation affects this new array $$$b$$$. If we apply the operation at index $$$i$$$, the new values in $$$a$$$ become $$$a'_i = -a_{i+1}$$$ and $$$a'_{i+1} = -a_i$$$. Observe the corresponding elements in $$$b$$$:

Surprisingly, the operation on $$$a$$$ translates to exactly swapping adjacent elements in $$$b$$$!

Since we can swap adjacent elements any number of times, we can rearrange $$$b$$$ into any permutation we want. This is the core idea of the problem. All that's left is just some math. Now, let's express the sum of the array $$$a$$$ in terms of $$$b$$$:

To maximize this total sum, we greedily place the smallest $$$\lfloor \frac{n}{2} \rfloor$$$ elements of the array $$$b$$$ at even indices and the largest $$$\lceil \frac{n}{2} \rceil$$$ elements at odd indices. The resulting alternating sum of the array $$$b$$$ is the required answer.

Time Complexity: $$$\mathcal{O}(n \log n)$$$.

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

int main(){

    int t;
    cin >> t;

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

        vector<int> a(n);
        for(auto& z : a) cin >> z;

        vector<int> b = a;
        for(int i = 1; i < n; i += 2) b[i] = -b[i];

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

        int i = 0;
        long long ans = 0;
        for(; i < n / 2; i++) ans -= b[i];
        for(; i < n; i++) ans += b[i];

        cout << ans << '\n';
    }

    return 0;
}

• Best Problem
• Good Problem
• Okay Problem
• Bad Problem
• Didn't Solve

For any two positive integers $$$x \ge y$$$, we can write $$$x \bmod y = x - k \cdot y$$$, where $$$k = \lfloor \frac{x}{y} \rfloor \ge 1$$$.

Let $$$k_i = \lfloor \frac{a_i}{a_{i+1}} \rfloor$$$. Since the array is non-increasing ($$$a_i \ge a_{i+1}$$$), we are guaranteed that $$$k_i \ge 1$$$. We can rewrite the modulo sum condition as:

Upon rearranging, we get:

Let's bound the right-hand side. We are given $$$a_1 \le m+2$$$ and $$$a_n \ge 1$$$. Thus, the maximum possible value for $$$a_1 - a_n - m$$$ is $$$(m+2) - 1 - m = 1$$$. Because $$$k_i \ge 1$$$ and $$$a_{i+1} \ge 1$$$, every term in the summation on the left is non-negative. This strictly bounds the sum to be either exactly $$$0$$$ or exactly $$$1$$$. Observe that this also imposes the additional constraints $$$a_n \le 2$$$ and $$$a_1 \ge m + 1$$$.

Now, if $$$a_n = 2$$$, we must have $$$a_1 = m + 2$$$. Note that this forces every $$$k_i$$$ to be exactly equal to $$$1$$$. So, we must have $$$a_{i+1} \le a_i \lt 2a_{i+1}$$$.

If $$$a_n = 1$$$, consider the exact step where the sequence drops to $$$1$$$ from some value $$$x \ge 2$$$. For this specific step, $$$a_j = x$$$ and $$$a_{j+1} = 1$$$. The quotient is $$$k_j = \lfloor \frac{x}{1} \rfloor = x$$$. See that if $$$x \ge 3$$$, the left-hand side is at least $$$2$$$, and this is not allowed. This forces the constraint $$$x \le 2$$$. Thus, we must have $$$x = 2$$$. This proves that if the sequence drops to $$$1$$$, it must drop exactly from the value $$$2$$$. This makes the left-hand side at least $$$1$$$, and consequently, the right-hand side of our equation must be exactly $$$1$$$, implying $$$a_1 = m + 2$$$. Similar to the previous case, every $$$k_i$$$ ($$$i \lt j$$$) is forced to be exactly equal to $$$1$$$. So, we must have $$$a_{i+1} \le a_i \lt 2a_{i+1}$$$.

Generalizing things, an array $$$a$$$ is good if and only if it satisfies all of the following conditions:

• $$$a_1 = m + 2$$$;
• $$$a_j = 2$$$ for some index $$$j \in [2, n]$$$;
• $$$a_k = 1$$$ for all $$$j + 1 \le k \le n$$$;
• $$$a_{i+1} \le a_i \lt 2a_{i+1}$$$ for all $$$1 \le i \lt j$$$.

To count the number of good arrays, we use 2D DP. Let $$$\text{dp}[i][v]$$$ ($$$1 \le i \le n$$$; $$$2 \le v \le m + 2$$$) denote the number of valid prefixes of length $$$i$$$ with an additional constraint $$$a_i = v$$$. The base case would be $$$\text{dp}[1][m+2] = 1$$$ and $$$\text{dp}[1][x] = 0$$$ for all $$$x \neq m + 2$$$. The transition is straightforward:

Any valid sequence that safely hits $$$2$$$ at length $$$i$$$ will just be padded with $$$1$$$s for the remaining $$$n-i$$$ elements. This padding is unique and deterministic. Therefore, to find the total number of good arrays of length $$$n$$$, we simply sum the number of ways to reach the value $$$2$$$ at any valid length $$$i$$$:

This DP has $$$\mathcal{O}(nm)$$$ states, and each transition requires a contiguous range sum of the previous row. By maintaining a prefix sum of the DP table, we can compute each state in constant time, yielding an optimal solution in $$$\mathcal{O}(nm)$$$ time and space. It is useful to note that one can also optimize the space complexity to $$$\mathcal{O}(m)$$$ (refer to the implementation below).

Time Complexity: $$$\mathcal{O}(nm)$$$.

#include<bits/stdc++.h>
using namespace std;
 
#define ll long long
const ll mod = 998'244'353;
 
int main(){
 
    int t;
    cin >> t;
 
    while(t--){
        int n, m;
        cin >> n >> m;
 
        vector<ll> dp(m + 3, 0);
        dp[m + 2] = 1;
 
        ll ans = 0;
 
        for(int i = 1; i < n; i++){
             
            ll sum = (dp[2] + dp[3]) % mod;
            int left = 2, right = 3;
 
            for(int j = 2; j < m + 3; j++){
 
                ll temp = sum;
 
                sum += (mod - dp[left]);
                left++;

                right++;
                if(right < m + 3) sum += dp[right];
                right++;
                if(right < m + 3) sum += dp[right];
 
                sum %= mod;
                dp[j] = temp;
            }
 
            ans += dp[2];
            ans %= mod;
        }
 
        cout << ans << '\n';
    }
 
    return 0;
}

• Best Problem
• Good Problem
• Okay Problem
• Bad Problem
• Didn't Solve

Observe the behavior of an injected energy pulse. If a node is at state $$$0$$$, it becomes $$$1$$$ and stops. If it is $$$1$$$, it becomes $$$0$$$ and sends a pulse to its children. Notice that this is exactly the mechanism of binary addition. Flipping from $$$0 \to 1$$$ is adding $$$1$$$ without a carry. Flipping from $$$1 \to 0$$$ and passing a pulse is adding $$$1$$$ and generating a carry to the next significant bit.

Consider a path from the root down to a node $$$v$$$ at depth $$$d$$$ (0-indexed). The initial states of the nodes on this path form a binary integer $$$X_v$$$, where the root represents the least significant bit (LSB) and $$$v$$$ represents the $$$d$$$-th bit. Because the carry rules are identical, injecting $$$K$$$ pulses at the root is mathematically equivalent to computing the sum $$$X_v + K$$$ for every path simultaneously.

The final state of node $$$v$$$ after $$$K$$$ pulses will simply be the $$$d$$$-th bit of the sum $$$X_v + K$$$. We require this final state to be exactly $$$y_v$$$.

Since $$$K$$$ is a single global integer, we can determine it bit by bit, level by level. Let $$$k_d$$$ be the $$$d$$$-th bit of $$$K$$$. Let $$$C_v$$$ be the incoming carry bit that node $$$v$$$ receives from its parent. For the root, $$$C_{\text{root}} = 0$$$.

For any node $$$v$$$ at depth $$$d$$$, the $$$d$$$-th bit of the sum $$$X_v + K$$$ is calculated as:

We need this to equal $$$y_v$$$. Rearranging the equation gives us the required $$$d$$$-th bit of $$$K$$$:

This creates a strict constraint: for a valid $$$K$$$ to exist, the required $$$k_d$$$ must evaluate to the exact same value for all nodes at depth $$$d$$$. If any two nodes at the same depth yield a different $$$k_d$$$, it is impossible to satisfy both simultaneously. We print $$$-1$$$ in this case.

If all nodes at depth $$$d$$$ agree on $$$k_d$$$, we lock in this bit for $$$K$$$. We then compute the outgoing carry that node $$$v$$$ will pass to its children for the next depth:

The final answer is computed by summing $$$2^d$$$ for all depths $$$d$$$ where $$$k_d = 1$$$. Since we process each node exactly once and only do constant-time bitwise operations, the complexity is linear.

Time Complexity: $$$\mathcal{O}(n)$$$.

#include<bits/stdc++.h>
using namespace std;
 
const int mod = 998'244'353;

const int MX = 200005;
vector<int> p2(MX, 1);
void init(){
    for(int i = 1; i < MX; i++) p2[i] = 2 * p2[i - 1] % mod;
}
 
int main(){

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

        vector<vector<int>> v(n + 1);
        for(int i = 1; i < n; i++){
            int x, y;
            cin >> x >> y;
            v[x].push_back(y);
            v[y].push_back(x);
        }

        string x, y;
        cin >> x >> y;
        x = "." + x;
        y = "." + y;

        vector<int> dep(n + 1, 0), par(n + 1, 0);

        function<void(int, int)> dfs = [&](int u, int p){
            for(auto& z : v[u]) if(z != p){
                par[z] = u;
                dep[z] = 1 + dep[u];
                dfs(z, u);
            }
        };

        dfs(1, -1);

        vector<int> carry(n + 1, 0);
        vector<vector<int>> nodes(n);
        for(int i = 1; i <= n; i++) nodes[dep[i]].push_back(i);

        int ans = 0;
        bool is = 1;
        for(int i = 0; i < n && is; i++){
            bool req[2] = {0, 0};
            for(auto& z : nodes[i]){
                int xb = x[z] - '0';
                int yb = y[z] - '0';
                int cb = carry[par[z]];
                int rb = xb ^ yb ^ cb;
                req[rb] = 1;
                if(xb + cb + rb > 1) carry[z] = 1;
            }
            if(req[0] && req[1]) is = 0;
            ans += req[1] * p2[i];
            ans %= mod;
        }

        if(!is) ans = -1;
        cout << ans << '\n';
    }
 
    return 0;
}

• Best Problem
• Good Problem
• Okay Problem
• Bad Problem
• Didn't Solve