The operation allows us to choose a divisor $$$z$$$ of $$$x$$$ and update $$$x := \frac{x}{z}$$$.

Since $$$z$$$ is a divisor of $$$x$$$, the resulting value $$$\frac{x}{z}$$$ is strictly an integer and is also a divisor of $$$x$$$. Because we can freely choose any valid $$$z$$$, a single operation effectively allows us to replace $$$x$$$ with any of its divisors.

Applying this operation multiple times does not yield any additional numbers, because a divisor of a divisor is still just a divisor of the original $$$x$$$. Therefore, the set of all possible numbers reachable from $$$x$$$ is strictly limited to its divisors.

Therefore, to solve the problem:

• If $$$y$$$ is a divisor of $$$x$$$ (i.e., $$$x \bmod y = 0$$$), we output YES. We can reach $$$y$$$ in at most $$$1$$$ operation by choosing $$$z = \frac{x}{y}$$$.
• If $$$y$$$ is not a divisor of $$$x$$$, we output NO, as it is impossible to reach.

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

#include<bits/stdc++.h>
using namespace std;
 
int main(){
 
    int tt;
    cin >> tt;
 
    while(tt--){
        int x, y;
        cin >> x >> y;
        
        cout << (x % y == 0 ? "YES" : "NO") << '\n';
    }
 
    return 0;
}

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

Let $$$d$$$ be the number of digits of $$$x$$$, and choose $$$y = 10^d + 1$$$. The number $$$y$$$ contains only the digits $$$0$$$ and $$$1$$$, so $$$y$$$ is good. Also,

Since $$$x \lt 10^d$$$, multiplying by $$$10^d$$$ simply shifts $$$x$$$ by $$$d$$$ positions. Therefore, $$$x \cdot y$$$ is exactly the decimal concatenation of $$$x$$$ with itself. Hence, the set of digits appearing in $$$x \cdot y$$$ is the same as in $$$x$$$. Since $$$x$$$ is good, $$$x \cdot y$$$ is good as well.

Thus, for every test case, one of the possible answers is simply

The construction always satisfies $$$2 \le y \le 10^9$$$.

Time Complexity: $$$\mathcal{O}(\log_{10}(x))$$$.

#include<bits/stdc++.h>
using namespace std;
 
int main(){
 
    int tt;
    cin >> tt;
 
    while(tt--){
        int x;
        cin >> x;
 
        int y = 1;
 
        while(x > 0){
            y *= 10;
            x /= 10;
        }
 
        cout << y + 1 << '\n';
    }
 
    return 0;
}

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

Let $$$c$$$ be the number of positions $$$i$$$ such that $$$s_i \ne s_{i+1}$$$.

If $$$c=0$$$, all characters are equal. The whole string is always a palindrome, so we can repeatedly delete characters until only one remains.

If $$$c=1$$$, the string consists of exactly two contiguous blocks of equal characters. Any palindrome of length at least $$$2$$$ must be contained entirely inside one of these blocks, so every operation only shortens a block and can never remove it completely. Therefore, both blocks remain nonempty, and the minimum possible length is $$$2$$$.

If $$$c\ge 2$$$, then the string has at least three blocks. First, we can shrink every block to length $$$1$$$, because any block of equal characters is itself a palindrome of length at least $$$2$$$ as long as its length is at least $$$2$$$. So we may assume the string becomes alternating.

Now consider an alternating string of length at least $$$3$$$. Its last three characters are always of the form $$$010$$$ or $$$101$$$; hence, they form a palindrome. Deleting the last character of this palindrome shortens the string by $$$1$$$, and the remaining string is still alternating. Repeating this step, we can reduce the string to length $$$3$$$. Then the whole string is a palindrome, and deleting its middle character gives two equal characters, which can be reduced to length $$$1$$$ in one more move.

Hence, the answer is $$$2$$$ iff $$$c=1$$$, and $$$1$$$ otherwise.

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

#include<bits/stdc++.h>
using namespace std;
 
int main(){
 
    int tt;
    cin >> tt;
 
    while(tt--){
        int n;
        string s;
        cin >> n >> s;
 
        int count = 0;
        for(int i = 0; i < n - 1; i++) if(s[i] != s[i + 1]) count++;
 
        cout << (count == 1 ? 2 : 1) << '\n';
    }
 
    return 0;
}

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

Let

The key is to look at prefix sums. One operation on segment $$$[l,r]$$$ adds the pattern $$$+1,-1,+1,-1,\dots$$$ starting from the left end. Therefore, the prefix sum of the modified array changes by $$$1$$$ on some prefixes and by $$$0$$$ on the others, so no prefix sum can ever decrease.

Now take the special segment $$$[i,i+1]$$$. It adds $$$+1$$$ to $$$a_i$$$ and $$$-1$$$ to $$$a_{i+1}$$$, so only the $$$i$$$-th prefix sum increases by $$$1$$$, while all other prefix sums stay unchanged. Also, $$$[n,n]$$$ increases only the $$$n$$$-th prefix sum by $$$1$$$.

So every prefix sum can be increased independently and never decreased. Hence, the transformation is possible iff

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

An alternative way to solve the problem is to first understand which operations are actually useful.

Consider an operation on a subarray of length greater than $$$2$$$. Its effect is exactly the sum of the operations on consecutive subarrays of length $$$2$$$ inside it (partitioning the subarray into consecutive pairs; if its length is odd, the last element is treated as a subarray of length $$$1$$$). Therefore, every operation on a longer subarray can be decomposed into operations on length-$$$2$$$ subarrays, so it is sufficient to consider only these.

Now there are only two useful operations:

• applying the operation on $$$[i,i]$$$, which increases $$$a_i$$$ by $$$1$$$;
• applying the operation on $$$[i-1,i]$$$, which decreases $$$a_i$$$ by $$$1$$$ and increases $$$a_{i-1}$$$ by $$$1$$$.

We process the array from right to left. Suppose we are currently at position $$$i$$$.

• If $$$a_i \lt b_i$$$, we simply apply the first operation $$$b_i-a_i$$$ times, increasing only $$$a_i$$$ until it becomes $$$b_i$$$.
• If $$$a_i \gt b_i$$$, we apply the second operation $$$a_i-b_i$$$ times. Each application decreases $$$a_i$$$ by $$$1$$$ while increasing $$$a_{i-1}$$$ by $$$1$$$, so after these operations we have $$$a_i=b_i$$$. Any excess is pushed one position to the left.

Notice that after finishing position $$$i$$$, no later operation can change it again. Hence, every position except the first can always be fixed independently. After processing all positions from $$$n$$$ down to $$$2$$$, the only remaining value is $$$a_1$$$. Since every operation can only increase $$$a_1$$$, the transformation is possible if and only if

Thus, the algorithm is simply to process the array backwards as described above and finally check whether $$$a_1\le b_1$$$.

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

#include<bits/stdc++.h>
using namespace std;
 
int main(){
 
    int tt;
    cin >> tt;
 
    while(tt--){
        int n;
        cin >> n;
 
        vector<long long> a(n), b(n);
 
        for(int i = 0; i < n; i++) cin >> a[i];
        for(int i = 0; i < n; i++) cin >> b[i];
        for(int i = 1; i < n; i++) a[i] += a[i - 1];
        for(int i = 1; i < n; i++) b[i] += b[i - 1];
 
        bool is = 1;
        for(int i = 0; i < n; i++) if(a[i] > b[i]) is = 0;
 
        if(is) cout << "YES\n";
        else cout << "NO\n";
    }
 
    return 0;
}

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

For any two vertices $$$x$$$ and $$$y$$$, let us denote $$$P(x, y)$$$ as the simple path from $$$x$$$ to $$$y$$$.

Now, let us fix an unordered triplet of vertices $$${u,v,w}$$$. We claim that there is exactly one vertex (say $$$c$$$) that belongs to all three paths $$$P(u,v)$$$, $$$P(v,w)$$$, and $$$P(w,u)$$$, and every other vertex is counted $$$0$$$ or $$$2$$$ times.

Therefore, for the product

every vertex contributes an even exponent except $$$c$$$, whose exponent is $$$3$$$. Hence, the product is a perfect square iff $$$a_c$$$ is a perfect square.

So now we only need to count, for every vertex $$$x$$$ with $$$a_x$$$ a perfect square, how many triplets have $$$x$$$ as the unique common vertex. Remove $$$x$$$, and let the component sizes be $$$s_1,s_2,\dots,s_k$$$.

A valid triplet is of two types:

• $$$x$$$ is one of the chosen vertices. Then the other two vertices must come from two different components, so the count is

• $$$x$$$ is not chosen. Then the three chosen vertices must come from three different components, so the count is

Both values can be computed in one scan over the components:

and for each component size $$$s$$$:

Then the contribution of $$$x$$$ is $$$\text{pairs}+\text{triples}$$$.

To get the component sizes for every $$$x$$$, root the tree once and store subtree sizes. For a vertex $$$x$$$, its components after deletion are all child subtrees of $$$x$$$, plus the parent-side component of size $$$n-\mathrm{sz}[x]$$$ if it exists.

So the solution is:

• root the tree and compute subtree sizes;
• for every vertex $$$x$$$, build the sizes of components of $$$T-x$$$;
• if $$$a_x$$$ is a perfect square, add $$$\text{pairs}+\text{triples}$$$ to the answer.

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

#include<bits/stdc++.h>
using namespace std;
 
#define ll long long
 
int main(){
 
    int tt = 1;
    cin >> tt;
 
    while(tt--){
        ll n;
        cin >> n;
 
        vector<ll> a(n);
        for(ll i = 0; i < n; i++) cin >> a[i];
 
        vector<vector<ll>> v(n);
        for(ll i = 1; i < n; i++){
            ll x, y;
            cin >> x >> y;
            x--;
            y--;
            v[x].push_back(y);
            v[y].push_back(x);
        }
 
        ll ans = 0;
        vector<ll> ss(n, 1);
 
        function<void(ll, ll)> dfs = [&](ll u, ll par){
 
            vector<ll> val;
            for(auto& z : v[u]) if(z != par){
                dfs(z, u);
                val.push_back(ss[z]);
                ss[u] += ss[z];
            }
 
            val.push_back(n - ss[u]);
            assert(accumulate(val.begin(), val.end(), 0ll) == n - 1);
 
            if((ll)sqrtl(a[u]) * (ll)sqrtl(a[u]) < a[u]) return;
 
            ll sum = 0;
            ll pairs = 0;
            ll triplets = 0;

            for(auto& z : val){
                triplets += pairs * z;
                pairs += sum * z;
                sum += z;
            }

            ans += pairs;
            ans += triplets;
        };
 
        dfs(0, -1);
 
        cout << ans << '\n';
    }
 
    return 0;
}

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

One common way to solve these kinds of games is to first identify the losing states and then generalize their structure.

Let's first consider the states where the current player has no valid moves. An obvious example is a binary string consisting entirely of 0s or entirely of 1s. Since a player may delete any subsequence with an odd number of inversions, there is a lot of freedom in choosing a move. So instead of analyzing every possible move, let us ask a simpler question: When can Alice win immediately by deleting all 0s or all 1s?

Suppose Alice wants to delete all 1s. Then the chosen subsequence must have an odd number of inversions. This is possible iff it contains at least one 0 that is preceded by an odd number of 1s in the original string. Similarly, if Alice wants to delete all 0s, then the chosen subsequence must contain at least one 1 that is followed by an odd number of 0s. Both conditions can be checked in $$$\mathcal{O}(n)$$$ using prefix (or suffix) parity.

Now let us consider the strings that satisfy neither of these conditions. Such strings must have the form

where each $$$X_i$$$ is either 00 or 11. The leading 0 and trailing 1 are optional. Since these endpoint characters can never affect any inversion parity, we may simply ignore them. We claim that every string of this form is a losing state.

Therefore, Alice wins iff the initial string does not have the above form. Checking this structure is straightforward.

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

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

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
 
    int tt = 1;
    cin >> tt;
 
    while(tt--){
        ll n;
        cin >> n;
 
        string s;
        cin >> s;

        bool is = 1;
        int left = 0, right = n - 1;

        while(left < n && s[left] == '0') left++;
        while(right >= 0 && s[right] == '1') right--;

        if(left > right){
            cout << "Bob\n";
            continue;
        }

        int count = 1;
        for(int i = left; i < right; i++){
            if(s[i + 1] == s[i]) count++;
            else{
                if(count % 2 == 1) is = 0;
                count = 1;
            }
        }

        if(count % 2 == 1) is = 0;

        cout << (is ? "Bob\n" : "Alice\n");
    }
 
    return 0;
}

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

Let us look at what one operation really means.

Suppose we are working with a subarray $$$[l,r]$$$, and let $$$x=a_l$$$. The first element is special because it never changes: every operation only uses earlier values to modify later positions, so the leftmost value stays fixed forever.

Now the only thing that matters is how much freedom we have for the next elements. This is where $$$\text{gcd}$$$ enters naturally. If the current prefix has $$$\text{gcd}$$$ equal to $$$g$$$, then we claim that the next element can be changed by any multiple of $$$g$$$.

Now let us focus on subarrays starting at index $$$l$$$.

As long as every element to the right of $$$a_l$$$ is divisible by $$$a_l$$$, the $$$\text{gcd}$$$ of the processed prefix remains exactly $$$a_l$$$ — because all seen values are multiples of $$$a_l$$$, and $$$a_l$$$ itself is present. So every such element can be moved by multiples of $$$a_l$$$, which means each of them can be made equal to $$$a_l$$$. Therefore, if the subarray never contains an element not divisible by $$$a_l$$$, then the whole subarray can be made constant, and the value of $$$f$$$ is $$$0$$$.

Now define $$$\text{next[l]}$$$ as the first position $$$t \gt l$$$ such that $$$a_t$$$ is not divisible by $$$a_l$$$. If no such position exists, set $$$\text{next[l]=n+1}$$$.

If such a position exists, we write

Since $$$t$$$ is the first such position, the $$$\text{gcd}$$$ of everything before it is still $$$a_l$$$, so the value at position $$$t$$$ can only move inside its residue class modulo $$$a_l$$$. Hence, the closest it can get to $$$a_l$$$ is

So the spread of the subarray can never go below $$$d$$$.

The key observation is that the first non-divisible element already fixes the answer. The lower bound $$$d$$$ obtained from this element is tight, and no later element can increase it. Therefore, once this position appears, every longer subarray starting at $$$l$$$ has the same answer $$$d$$$.

Hence, for a fixed $$$l$$$:

• for every $$$r \lt \text{next}[l]$$$, we have $$$f([a_l,\dots,a_r])=0$$$;
• for every $$$r\ge \text{next}[l]$$$, we have

So, once $$$\text{next[l]}$$$ is found, all longer subarrays starting at $$$l$$$ contribute the same value. That makes counting easy. The number of subarrays starting at $$$l$$$ that contain this position is $$$n-t+1$$$. So the contribution from index $$$l$$$ is

Now we only need to find $$$\text{next[l]}$$$ for every $$$l$$$. This can be done with a monotonic stack while scanning from left to right. The stack stores indices whose first non-divisible element has not been found yet. In detail, when we are at position $$$i$$$, if

then we have $$$i = \text{next[top]}$$$. Why? Because if any earlier position had already broken divisibility for that index, it would already have been removed from the stack. So we can finalize its contribution immediately and pop it. This way, each index is pushed once and popped once, so the whole procedure is linear.

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

Note that one can also find $$$\text{next[l]}$$$ for every index $$$l$$$ by performing binary search using a sparse table to store $$$\text{gcd}$$$, leading to an $$$\mathcal{O}(n \cdot \log n \cdot \log a)$$$ solution. These implementations are also intended to pass.

#include<bits/stdc++.h>
using namespace std;
 
#define ll long long
typedef __int128 int128;

std::ostream& operator<<(std::ostream& os, int128 t) {
    if (t == 0) return os << "0";
    if (t < 0) {
        os << "-";
        t = -t;
    }
    int a[50], i = 0;
    while (t > 0) {
        a[i++] = t % 10;
        t /= 10;
    }
    for (int j = i - 1; j >= 0; j--) {
        os << (char)(a[j] + '0');
    }
    return os;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
 
    int tt = 1;
    cin >> tt;
 
    while(tt--){
        ll n;
        cin >> n;
 
        vector<ll> a(n);
        for(auto& z : a) cin >> z;

        int128 ans = 0;
        stack<ll> s;

        for(int i = 0; i < n; i++){
            while(!s.empty() && a[i] % a[s.top()] > 0){
                ans += (int128)1 * (n - i) * min(a[i] % a[s.top()], a[s.top()] - a[i] % a[s.top()]);
                s.pop();
            }
            s.push(i);
        }

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

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