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

For any two positive integers $$$x$$$ and $$$y$$$, observe that $$$x \times y \ge x + y$$$ when $$$x \gt 1$$$ and $$$y \gt 1$$$. Thus, it is never optimal to choose two elements that are more than $$$1$$$ in a single operation. Also, it is optimal to choose as many $$$1$$$'s as possible in a single operation.

Hence, we opt to choose subsequences of the form $$$[1, 1, \ldots, x]$$$ and delete them. Note that the cost for this operation is equal to $$$x$$$. Therefore, the answer is just the sum of elements that are more than $$$1$$$. But if the last element is $$$1$$$, it cannot be clubbed with any "more than $$$1$$$ element", and it adds $$$1$$$ to the answer.

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(int i = 0; i < n; i++) cin >> a[i];
 
        int ans = 0;
 
        for(int i = 0; i < n; i++) if(a[i] > 1) ans += a[i];
        if(a.back() == 1) ans++;
 
        cout << ans << '\n';
 
    }
}

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

For any array $$$a$$$, let $$$\text{g}$$$ denote the $$$\text{gcd}$$$ of all the elements in the array $$$a$$$. Note that every element in $$$a$$$ is a multiple of $$$\text{g}$$$. Let the maximum element be equal to $$$M \cdot \text{g}$$$ and the minimum element be equal to $$$m \cdot \text{g}$$$.

If array $$$a$$$ is good, the given condition simplifies to $$$M - m = 1$$$. This implies that $$$a$$$ must contain exactly two distinct elements, and they should be of the form $$$m \cdot \text{g}$$$ and $$$(m+1) \cdot \text{g}$$$.

Note that you are given a permutation rather than any array. Since all the elements in a permutation are distinct, any subarray that has length not equal to $$$2$$$ is guaranteed to be not good. Thus, we only need to check those subarrays that have a length equal to $$$2$$$.

This is trivial. For every $$$i$$$, check whether the array $$$[p_i, p_{i+1}]$$$ satisfies the given condition.

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(int i = 0; i < n; i++) cin >> a[i];
 
        int ans = 0;
        for(int i = 0; i < n - 1; i++) if(a[i] % (a[i] - a[i + 1]) == 0) ans++;
        
        cout << ans << '\n';
    }
 
    return 0;
}

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

For a fixed value of $$$x$$$ and varying $$$y$$$, let us analyze what values $$$x \, \bmod \, y$$$ can attain.

To start with, if $$$y \gt x$$$, $$$x \, \bmod \, y = x$$$. Otherwise, if $$$y \le x$$$, $$$x \, \bmod \, y$$$ will always be less than $$$\frac{x}{2}$$$. We can prove this by breaking down the condition $$$y \le x$$$ into two cases:

• $$$y \le \frac{x}{2}$$$: Since the remainder must be less than the divisor, we have $$$x \, \bmod \, y \lt y \le \frac{x}{2}$$$. Thus, $$$x \, \bmod \, y \lt \frac{x}{2}$$$.
• $$$\frac{x}{2} \lt y \le x$$$: In this case, note that $$$x \, \bmod \, y = x - y \lt x - \frac{x}{2} = \frac{x}{2}$$$. Thus, $$$x \, \bmod \, y \lt \frac{x}{2}$$$.

And finally, we note that $$$x \, \bmod \, y$$$ can be equal to $$$x$$$ (choose any $$$y$$$ greater than $$$x$$$) or it can attain any value $$$z \lt \frac{x}{2}$$$ (choose $$$y = x - z$$$).

Now, let us try to solve the given problem. Let us call an integer $$$k$$$ good if we can attain all the values $$$0, 1, 2, \ldots, k-1$$$ in the array $$$a$$$ after performing the operation. Note that the answer for this problem is the maximum integer $$$k$$$, which is good. Furthermore, observe that if a particular value $$$k$$$ is good, then $$$k-1$$$ is also guaranteed to be good. This monotonic behavior naturally leads to the use of binary search to determine the maximum such $$$k$$$.

The only thing left now is "given an integer value $$$k$$$, how do we check if it is good?" To check if $$$k$$$ is good, we need to check whether we can attain all the values $$$0, 1, 2, \ldots, k-1$$$ in the array by performing an operation. To attain a value $$$x$$$ ($$$0 \le x \lt k$$$), we need atleast one index $$$i$$$ that satisfies $$$a_i = x$$$ or $$$a_i \gt 2x$$$ (since $$$a_i \, \bmod \, b_i$$$ can be either $$$a_i$$$ or $$$ \lt \frac{a_i}{2}$$$). We must also make sure that every value is assigned to at most one position.

To handle this, let us process the required values in decreasing order, i.e., from $$$k-1$$$ to $$$0$$$. We maintain a multiset of all unused array elements. For a current value $$$x$$$, we do the following:

• If $$$x$$$ itself is present in the multiset, then we remove one occurrence of $$$x$$$.

• Otherwise, we need some unused value $$$a_i$$$ such that $$$a_i \gt 2x$$$. Among all such values, we can choose one.

If at some step neither of the above is possible, then the current value $$$x$$$ cannot be formed, and hence $$$k$$$ is not good.

The above strategy works because any value greater than $$$2x$$$ can always be reduced to $$$x$$$, and when both $$$x$$$ and some value $$$ \gt 2x$$$ are available, it is optimal to choose the smallest feasible value, since larger elements are more flexible and may still be needed to construct smaller values later.

Time Complexity: $$$\mathcal{O}(n \cdot \log^2 n)$$$

#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> a(n);
        for(int i = 0; i < n; i++) cin >> a[i];
 
        multiset<int> ms(a.begin(), a.end());
 
        int l = 0, r = n + 1;
        while(l < r){
            int md = (l + r) / 2;
 
            assert((int)ms.size() == n);
            
            bool is = 1;
            vector<int> removed;
 
            for(int i = md - 1; i >= 0; i--){
                if(ms.count(i)){
                    removed.push_back(i);
                    ms.erase(ms.find(i));
                    continue;
                }
                else{
                    int x = *ms.rbegin();
                    if(x < 2*i + 1){
                        is = 0;
                        break;
                    }
                    removed.push_back(x);
                    ms.erase(ms.find(x));
                }
            }
 
            for(auto& z : removed) ms.insert(z);
 
            if(is) l = md + 1;
            else r = md;
        }
 
        assert(l > 0);
        --l;
 
        cout << l << '\n';
    }
    
}

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

Let us consider odd and even values separately. If odd values can be sorted within themselves, and even values can be sorted within themselves, then it is easy to see that the whole array can be sorted eventually (we can just apply adjacent reversals by choosing segments of length $$$2$$$ of which one is even and one is odd).

Now, let us consider even values separately. Let the subsequence of even values be $$$[e_1, e_2, \ldots, e_m]$$$. For each $$$i$$$ from $$$1$$$ to $$$m$$$, we aim to make the prefix up to index $$$i$$$ sorted. That is, we try to place $$$e_i$$$ in its correct position in the sorted order, assuming that the prefix up to index $$$i-1$$$ is already sorted.

Let the sorted prefix up to index $$$i-1$$$ be $$$[E_1, E_2, \ldots, E_{i-1}]$$$, where $$$E_1 \le E_2 \le \cdots \le E_{i-1}$$$. If $$$e_i \ge E_{i-1}$$$, we can directly extend the prefix and proceed to index $$$i+1$$$. Otherwise, if $$$e_i \lt E_{i-1}$$$, we must change the relative order of $$$e_i$$$ and $$$E_{i-1}$$$. So, we must apply an operation involving both of them (otherwise, the relative order will not change). In order to apply such an operation, we must at least need an odd integer $$$z$$$ such that either $$$z \gt E_{i-1}$$$ or $$$z \lt e_i$$$. If we cannot find such $$$z$$$, we can instantly conclude that the array $$$a$$$ cannot be sorted.

If we can find such $$$z$$$, it is sufficient, and we can use it to change the relative order of $$$e_i$$$ and $$$E_{i-1}$$$ without changing the relative order of any other pair of elements having the same parity in the array $$$a$$$. Proof is as follows:

Let the values $$$e_i$$$, $$$E_{i-1}$$$, $$$z$$$ appear in the array $$$a$$$ in the following manner: $$$[\ldots, E_{i-1}, \ldots, e_i, \ldots, z, \ldots]$$$. Note that there won't be any even value in between $$$E_{i-1}$$$ and $$$e_i$$$. So, let's move all the odd values between them to the left of $$$E_{i-1}$$$ by making adjacent reversals. There can be both even and odd values between $$$e_i$$$ and $$$z$$$; we propagate all the even values to the right of $$$z$$$ and all the odd values to the left of $$$E_{i-1}$$$ by making adjacent reversals. Now, the array $$$a$$$ looks like: $$$[\ldots, E_{i-1}, e_i, z, \ldots]$$$. Finally, choose the segment with all three elements and reverse it, we get the desired order: $$$[\ldots, z, e_i, E_{i-1}, \ldots]$$$.

We follow the same idea with $$$E_{i-2}, E_{i-3} \ldots$$$. Finally, we place $$$e_i$$$ in its correct position in the sorted order. So, we check the existence of such $$$z$$$ for every inversion (can be easily done by storing the prefix maximum).

We follow the same process with odd values. To conclude, if we find any inversion within a parity and cannot find a valid $$$z$$$ of opposite parity, the answer is NO. Otherwise, the answer is YES.

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

#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> a(n);
        for(int i = 0; i < n; i++) cin >> a[i];
 
        vector<int> even, odd;
        for(auto& z : a){
            if(z % 2) odd.push_back(z);
            else even.push_back(z);
        }
 
        int even_min = 1e9;
        int even_max = -1e9;
        int odd_min = 1e9;
        int odd_max = -1e9;
 
        if(!even.empty()){
            for(auto& z : even){
                even_min = min(even_min, z);
                even_max = max(even_max, z);
            }
        }
 
        if(!odd.empty()){
            for(auto& z : odd){
                odd_min = min(odd_min, z);
                odd_max = max(odd_max, z);
            }
        }
 
        bool is = 1;
 
        if(even.size() > 1){
 
            int mx = even[0];
 
            for(int i = 1; i < even.size(); i++){
                if(mx > even[i]){
                    if(odd_min > even[i] && odd_max < mx){
                        is = 0;
                        break;
                    }
                }
                else{
                    mx = even[i];
                }
            }
        }
 
        if(odd.size() > 1){
            
            int mx = odd[0];
 
            for(int i = 1; i < odd.size(); i++){
                if(mx > odd[i]){
                    if(even_min > odd[i] && even_max < mx){
                        is = 0;
                        break;
                    }
                }
                else{
                    mx = odd[i];
                }
            }
        }
 
        if(is) cout << "YES\n";
        else cout << "NO\n";
 
    }
}

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

First, read the tutorial for the easy version of the problem.

Let's call a number $$$m$$$ fixed if for some $$$i$$$, we have $$$a_i=m$$$, and we choose $$$b_i \gt m$$$ (so that $$$a_i \operatorname{mod} b_i = a_i$$$). Recall that from the easy version, when we want to determine whether an answer $$$k$$$ is possible to achieve, we should greedily fix as many numbers under $$$k$$$ as possible, and then check if assigning the other numbers so that $$$a_i \gt 2(a_i \operatorname{mod} b_i)$$$ is possible.

Our first useful observation for the hard version is that the answer is monotonic in terms of prefix. That is, the answer for the prefix of size $$$i$$$ must be at least the answer for the prefix of size $$$i-1$$$. This motivates us to use two pointers on the prefix and the answer. That is, for each prefix, increment our answer as much as possible.

Unfortunately, both updating to a new prefix and incrementing the answer by $$$1$$$ is hard. For example, suppose our current answer is $$$3$$$, and we are trying to increment it to $$$4$$$. It is possible that for some $$$a_i=4$$$, we have $$$b_i=3$$$ (so we get $$$a_i \operatorname{mod} b_i=1$$$). When we incremented our answer to $$$4$$$, it is optimal to reassign the $$$b_i=5$$$ so that $$$4$$$ is fixed. This creates a chain of updates of assignments, and maintaining all updates directly is too slow.

Therefore, we need a way to check whether an assignment is possible efficiently. Call the multiset of values in $$$a$$$ that is not used to fix "offerers", and call the set of values of $$$a_i \operatorname{mod} b_i$$$ we need "receivers". Our job is to match each receiver to an offerer that is more than twice its value. Suppose we already fixed our set of receivers and offerers — how do we check whether a matching is possible? This is a classic result: we should loop through receivers from smallest to largest and match it to the smallest offerer remaining that it can match to.

Let's look at it a different way. Consider each prefix of receivers from largest to smallest. In order for it to be possible to match to only the largest receiver (call it $$$x$$$), we need an offerer of at least $$$2x+1$$$. What about it to be possible to match the largest two receivers? (call it $$$x,y$$$ for $$$x \gt y$$$). Then, we need at least two numbers of at least $$$2y+1$$$, and for the requirement for $$$x$$$ to be satisfied. Continuing this on, for a prefix of $$$p$$$ receivers with the smallest one being $$$q$$$, we need at least $$$p$$$ offerers of at least $$$2q+1$$$, and for the requirements of all prefixes before it to be satisfied.

Now, let's bring this set of requirements to a data structure. A segment tree is an appropriate choice. Define the segment tree such that the value at index $$$i$$$ is (number of offerers at least $$$2i+1$$$ — number of receivers at least $$$i$$$). To check whether the current answer is possible, we can query the minimum in the segment tree, and if it is nonnegative, then it is possible. Incrementing the prefix and answer can both be described as range additions. Thus, the problem is solved in $$$O(n\log n)$$$ time.

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

#include <bits/stdc++.h>
#define int long long
#define ll long long
#define pii pair<int,int>
#define fi first
#define se second 
using namespace std;
 
struct segtree {
    const static int INF = 1e18; 
    int l, r, v = 0, lz = 0; 
    segtree *lc, *rc; 
    segtree* getmem(); 
    segtree() : segtree(-1, -1) {}; 
    segtree(int l, int r) : l(l), r(r) {
        if (l==r) return; 
        int m=(l+r)/2; 
        lc=getmem(); *lc=segtree(l,m); 
        rc=getmem(); *rc=segtree(m+1,r); 
    }
    int getv() {
        return v+lz; 
    }
    int op(int a, int b) {
        return min(a,b); 
    }
    void upd(int i, int x) {
        add(i,i,x-q(i,i)); 
    }
    void add(int ql, int qr, int x) {
        if (r<ql||qr<l) return; 
        if (ql<=l&&r<=qr) {lz+=x; return;}
        lc->add(ql,qr,x); rc->add(ql,qr,x); 
        v=op(lc->getv(), rc->getv()); 
    }
    int q(int ql, int qr) {
        if (qr<l||r<ql) return INF; 
        if (ql<=l&&r<=qr) return getv(); 
        return op(lc->q(ql,qr), rc->q(ql,qr))+lz; 
    }
};
segtree mem[1000000]; int memsz=0; 
segtree* segtree::getmem() {
    return &mem[memsz++]; 
}
 
void solve() {
    int n; cin >> n;
    vector<int> v(n);
    unordered_map<int,int> m; 
    segtree st(0,n+2); 
    int i = 0; 
    st.upd(0,-1); 
    for (int &r:v) {
        cin >> r; 
        if (m[r]||r>i) {
            st.add(0,(r-1)/2,1); 
        } 
        else {
            st.upd(r,1e9); 
            st.add(0,r,1); 
        }
        m[r]++; 
        while (1) {
        // for (int j = 0; j < n; j++) cout << st.q(j,j) << " "; cout << "\n"; 
            if (st.q(0,i)<0) break; 
            i++; 
            st.add(0,i,-1); 
            if (m[i]) {
                st.upd(i,1e9); 
                st.add(0,(i-1)/2,-1); 
                st.add(0,i,1); 
            }
        }
        cout << i << " "; //cout << '\n'; 
    }
    cout << "\n"; 
}
 
int32_t main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int t=1; cin >> t;
    while (t--) solve(); 
}

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

The key observation lies in the symmetry

So for every value below $$$n$$$, replacing $$$x$$$ by $$$n-x$$$ keeps the $$$\gcd$$$ condition unchanged.

Now, let us focus on the values $$$1,2,\ldots,n-1$$$. If we take any valid arrangement of these values and replace every $$$x$$$ by $$$n-x$$$, then the arrangement is still valid. Also, for any pair of values $$$x, y \lt n$$$,

So every inversion becomes a non-inversion, and every non-inversion becomes an inversion. There are exactly $$$\binom{n-1}{2}$$$ pairs among the values $$$1,2,\ldots,n-1$$$. Therefore, in each complementary pair of valid permutations, the total number of inversions coming from these values is exactly $$$\binom{n-1}{2}$$$. Hence, the average contribution is

This is the core trick.

Now, let us try to count the number of valid permutations of $$$1, 2, \ldots, n - 1$$$. For a divisor $$$d \mid n$$$, let $$$\text{cnt}_d$$$ denote the number of integers $$$v \in [1,n]$$$ with $$$\gcd(v,n)=d$$$. So if currently $$$\text{cur}_d$$$ positions require $$$\gcd$$$ value $$$d$$$, then the number of ways to assign values to those positions is

Multiplying over all $$$d \lt n$$$ gives the number of ways to satisfy all nonzero constraints. Let this product be $$$B$$$. If for some $$$d$$$, we have $$$\text{cur}_d \gt \text{cnt}_d$$$, then there are no valid permutations.

Finally, we have to add the inversions contributed by $$$n$$$. If $$$n$$$ is placed at position $$$i$$$, then it contributes exactly $$$n-i$$$ inversions, since it is larger than every value to its right and smaller than none to its left.

So the whole answer is:

• the symmetric contribution of values $$$1,2,\ldots,n-1$$$,
• plus the position-based contribution of $$$n$$$.

The final formulas will be as follows.

Let $$$Z$$$ be the number of positions with $$$a_i=0$$$. Also define

We will have two cases depending on whether $$$n$$$ is fixed or not.

Case 1: one position is fixed to $$$n$$$

Suppose the position of $$$n$$$ is forced to be $$$pos_n$$$. Then the number of valid permutations is

The total inversion sum is

Case 2: no position is fixed to $$$n$$$

Then $$$n$$$ can be placed in any zero position. For a fixed position of $$$n$$$, the remaining values can be arranged in

ways.

So the total inversion sum is

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

#include<bits/stdc++.h>
using namespace std;
 
#define ll long long
const ll mod = 998'244'353;
 
ll power(ll x, ll y, ll z = LLONG_MAX){
    ll res = 1;
    while(y > 0){
        if(y % 2) res = (res * x) % z;
        y /= 2;
        if(y) x = (x * x) % z;
    }
    return res % z;
}
 
#define MX 2'000'007
ll fac[MX + 1], numInv[MX + 1], facNumInv[MX + 1];
 
void compfac(ll z){
    facNumInv[0] = facNumInv[1] = numInv[0] = numInv[1] = fac[0] = 1;
    for(ll i = 2; i <= MX; i++) numInv[i] = numInv[z % i] * (z - z / i) % z;
    for(ll i = 2; i <= MX; i++) facNumInv[i] = (facNumInv[i - 1] * numInv[i]) % z;
    for(ll i = 1; i <= MX; i++) fac[i] = (fac[i - 1] * i) % z;
    return;
}
 
ll nPrmod(ll n, ll r, ll z){
    if(r > n) return 0;
    return (fac[n] * facNumInv[n - r]) % z;
}
 
int main(){
 
    ios_base::sync_with_stdio(false); cin.tie(NULL);
 
    int t;
    cin >> t;
    compfac(mod);
 
    while(t--){
        ll n, q;
        cin >> n >> q;
 
        ll val = (n - 2) * (n - 1);
        val /= 2;
        val %= mod;
 
        val *= power(2, mod - 2, mod);
        val %= mod;
 
        vector<ll> cnt(n + 1, 0);
        for(ll i = 1; i <= n; i++) cnt[gcd(i, n)]++;
        cnt[0] = n;
 
        vector<ll> a(n, 0);
        vector<ll> cur(n + 1, 0);
        cur[0] = n - 1;
 
        ll zerocnt = 0;
        ll prod = 1;
 
        ll sum = n * (n - 1);
        sum /= 2;
        sum %= mod;
 
        while(q--){
            ll i, x;
            cin >> i >> x;
            --i;
            assert(n % x == 0);
            assert(a[i] == 0);
 
            cur[a[i]]--;
 
            a[i] = x;
            if(x == n) sum = n - 1 - i, cur[0]++;
            else if(cur[n] == 0) sum -= (n - i - 1);
 
            if(cur[0] < 0) zerocnt = 1;
 
            ll prev = nPrmod(cnt[a[i]], cur[a[i]], mod);
            prod *= power(prev, mod - 2, mod);
            prod %= mod;
 
            cur[a[i]]++;
 
            ll after = nPrmod(cnt[a[i]], cur[a[i]], mod);
            prod *= after;
            prod %= mod;
 
            if(cur[a[i]] > cnt[a[i]]) zerocnt = 1;
 
            ll mul = 1;
            if(cur[n] == 0) mul = cur[0] + 1;
 
            if(zerocnt > 0) cout << 0 << '\n';
            else cout << ((prod * fac[cur[0]]) % mod * (val * mul % mod + sum)) % mod << '\n';
        }
    }
 
    return 0;
}

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

#include <bits/stdc++.h>
#define int long long
#define ll long long
#define pii pair<int,int>
#define fi first
#define se second 
using namespace std;
 
vector<int> manacher_odd(vector<int> s) {
    int n = s.size();
    s.insert(s.begin(),-2); 
    s.push_back(-3); 
    vector<int> p(n + 2);
    int l = 0, r = 1;
    for(int i = 1; i <= n; i++) {
        p[i] = min(r - i, p[l + (r - i)]);
        while(s[i - p[i]] == s[i + p[i]]) {
            p[i]++;
        }
        if(i + p[i] > r) {
            l = i - p[i], r = i + p[i];
        }
    }
    return vector<int>(begin(p) + 1, end(p) - 1);
}
 
vector<int> manacher(vector<int> s) {
    vector<int> t;
    for(auto c: s) {
        t.push_back(-1);
        t.push_back(c); 
    }
    t.push_back(-1); 
    auto res = manacher_odd(t);
    return vector<int>(begin(res) + 1, end(res) - 1);
}
 
struct node {
    int count = 0; 
    unordered_map<int, node> m; 
    node() {
        count = 0; 
    }
};
 
void add(node &current, vector<int> &a, int d) {
    current.count++; 
    if (d>=a.size()) return; 
    if (current.m.find(a[d])!=current.m.end()) {
        add(current.m[a[d]],a,d+1);
    }
    else {
        node h;
        current.m[a[d]]=h; 
        add(current.m[a[d]],a,d+1); 
    }
}
 
const int mod = 998244353, MX=1e6+4; 
int F[MX]; 
unordered_map<int,int> counts; 
 
void init() {
    F[0]=1;
    for (int i = 1; i < MX; i++) F[i]=F[i-1]*i%mod; 
}
 
int pw(int b, int e=mod-2) {
    int x=1;
    while (e) {
        if (e%2) x=x*b%mod;
        b=b*b%mod;
        e/=2;
    }
    return x; 
}
 
void dfs(node &current, int cur, int d) {
    if (!d) {
        counts[cur]++;
        return; 
    }
    else (counts[cur]+=F[d-1]*(d-current.m.size()))%=mod; 
    for (auto [i, n]:current.m) {
        dfs(n, cur+n.count, d-1); 
    }
}
 
void solve() {
    int n, m; cin >> n >> m; 
    vector<int> v(n);
    for (int &r:v) cin >> r; 
    auto t=manacher(v); 
    // for (int r:t) cout << r << " "; cout << "\n"; 
    int cur=0;
    vector<int> prev(m+1,n), nxt(n); 
    for (int i = n-1; ~i; i--) {
        nxt[i]=prev[v[i]];
        prev[v[i]]=i; 
    }
    node head; 
    for (int i = 1; i < n; i++) {
        int k=t[2*i-1]/2;
        cur+=k;  
        if (k<n-i) continue; 
        vector<int> a; 
        for (int j = i-(n-i)-1; j >= 0; j--) {
            if (nxt[j]<=i-(n-i)-1) break;
            a.push_back(v[j]); 
        }
        add(head,a,0); 
    }
    vector<int> a; 
    for (int j = n-1; ~j; j--) {
        if (nxt[j]<n) break;
        a.push_back(v[j]);
    }
    add(head,a,0); 
    counts.clear(); 
    dfs(head,cur,m); 
    int ans=0;
    for (auto [i,c]:counts) {
        // cout << i << " " << c << "\n"; 
        ans=(ans+pw(c,i+1))%mod;
    }
    cout << ans << "\n"; 
}
 
int32_t main() {
    ios::sync_with_stdio(0); cin.tie(0);
    init(); 
    int t=1; cin >> t;
    while (t--) solve(); 
}

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

Let's say we have a sequence of numbers with an average equal to $$$k$$$.

Adding a number greater than $$$k$$$ increases the average, while adding a smaller one decreases it.

Therefore, the maximum average subarray is formed by taking the maximum element, since including anything smaller would only lower the average.

Hence, the final answer is the maximum element of the given array.

Time Complexity: $$$O(n)$$$ per testcase.

#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> a(n);
        for(int i = 0; i < n; i++) cin >> a[i];
 
        cout << *max_element(a.begin(), a.end()) << endl;
    }
 
    return 0;
}

We need to find a non-decreasing subsequence $$$p$$$ such that, after removing its characters from the string $$$s$$$, the remaining string $$$x$$$ becomes a palindrome.

Observe that if we choose $$$p$$$ to consist of all the $$$0$$$'s in $$$s$$$, then $$$x$$$ will contain only $$$1$$$'s, which always forms a palindrome. Similarly, if we take $$$p$$$ as all the $$$1$$$'s, then $$$x$$$ will contain only $$$0$$$'s, which is also a palindrome.

In both cases, $$$p$$$ is clearly a non-decreasing subsequence (since all its elements are equal).

Therefore, a valid solution always exists — we can simply output the indices of either all $$$0$$$'s or all $$$1$$$'s in the string.

Time Complexity: $$$O(n)$$$ per testcase.

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

        vector<int> pos;
        for(int i = 0; i < n; i++) if(s[i] == '0') pos.push_back(i + 1);

        cout << (int)pos.size() << '\n';
        for(auto& z : pos) cout << z << ' ';

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

We are allowed to choose any $$$x$$$ such that $$$0 \le x \le a$$$ and set $$$a := a \oplus x$$$. Our goal is to make $$$a$$$ equal to $$$b$$$.

Let's think of the binary representation of $$$a$$$. Consider the highest set bit (most significant bit) of $$$a$$$ and let's assume its position is $$$\operatorname{msb}(a)$$$.

At each operation, we are choosing $$$x \le a$$$, which implies that $$$\operatorname{msb}(x) \le \operatorname{msb}(a)$$$ (otherwise, we have $$$x \gt a$$$).

Now, we can surely say that $$$\operatorname{msb}(a \oplus x) \le \operatorname{msb}(a)$$$.

Thus, by performing the given operation, $$$\operatorname{msb}(a)$$$ will never increase. So, if $$$\operatorname{msb}(b) \gt \operatorname{msb}(a)$$$, the answer is $$$-1$$$.

Otherwise, we can always transform $$$a$$$ into $$$b$$$ in a constructive manner.

First, we set all bits below $$$\operatorname{msb}(a)$$$ one by one to ensure that every required bit can be manipulated. Then, for each bit that is $$$0$$$ in $$$b$$$, we unset it using an appropriate XOR operation.

By following this process, we can reach $$$b$$$ from $$$a$$$ in less than $$$60$$$ operations.

Time Complexity: $$$O(\log_2(a))$$$ per testcase.

#include<bits/stdc++.h>
using namespace std;
 
int main(){
 
    int t;
    cin >> t;
 
    while(t--){
        int a, b;
        cin >> a >> b;
        
        if(__builtin_clz(a) > __builtin_clz(b)) cout << "-1\n";
        else if(a == b) cout << "0\n";
        else{
            vector<int> val;
            for(int i = 0; i < 31; i++){
                int x = (1 << i);
                if(x <= a && (a & x) == 0) a += x, val.push_back(x);
            }
            for(int i = 0; i < 31; i++){
                int x = (1 << i);
                if(x <= a && (b & x) == 0) val.push_back(x);
            }
            cout << val.size() << '\n';
            for(auto z : val) cout << z << ' ';
            cout << '\n';
        }
    }
}

We denote

Now, let us try to find $$$l$$$ first.

Consider two additional arrays representing the prefix sums of the arrays $$$p$$$ and $$$a$$$, defined as follows:

Analysing these, we can say that $$$\text{pref_sum_a}[i] \ge \text{pref_sum_p}[i]$$$ for all $$$i$$$. In fact, the inequality holds true only when $$$l \le i \le n$$$.

Thus, we can binary search for $$$l$$$.

At each stage, we make $$$2$$$ queries $$$\operatorname{query}(1, 1, \text{mid})$$$ and $$$\operatorname{query}(2, 1, \text{mid})$$$, and by comparing these, we can adjust $$$\text{left}$$$ and $$$\text{right}$$$ in binary search.

We can also find $$$r$$$ by querying suffixes in a similar way, but that would take a total of $$$4 \cdot \lceil \log_2(n) \rceil$$$ queries. This exceeds the query limit.

Instead, we can query the whole array once and find $$$r$$$. In other words,

So, after finding $$$l$$$, we can find $$$r$$$ in $$$2$$$ queries. Total queries will be equal to $$$2 \cdot \lceil \log_2(n) \rceil + 2$$$ ($$$ \lt 40$$$).

Time Complexity: $$$O(\log_2(n))$$$ per testcase.

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

#define ll long long

ll query(int type, int l, int r){
    ll x;
    cout << type << ' ' << l << ' ' << r << flush << endl;
    cin >> x;
    return x;
}
 
int main(){
 
    int t;
    cin >> t;
 
    while(t--){
        
        int n;
        cin >> n;

        ll sum = query(2, 1, n);
        sum -= ((n * (n + 1)) / 2);

        ll diff = sum - 1;

        int l = 1, r = n;

        while(l < r){
            int md = (l + r) / 2;
            ll val1 = query(1, 1, md);
            ll val2 = query(2, 1, md);

            if(val1 < val2) r = md;
            else l = md + 1;
        }        

        cout << "!" << ' ' << l << ' ' << diff + l << flush << endl;

    }
}

Instead of carefully choosing all $$$k$$$ elements individually, it is sufficient to pick three distinct integers $$$x$$$, $$$y$$$, and $$$z$$$ and repeat them cyclically — that is, append

until we perform $$$k$$$ operations. For $$$n \ge 3$$$, we can always find such $$$x$$$, $$$y$$$, $$$z$$$ that add no extra palindromic subarrays.

Now let's try to find such integers $$$x$$$, $$$y$$$, $$$z$$$. There will be two cases.

Case 1: $$$a$$$ is a permutation of $$${1,2,3, \dots ,n}$$$.

If the array $$$a$$$ is a permutation, we can simply choose the first three elements of $$$a$$$ for the construction. That is, let $$$x = a_1$$$, $$$y = a_2$$$, and $$$z = a_3$$$. Since all elements in a permutation are distinct, these choices guarantee that $$$x$$$, $$$y$$$, and $$$z$$$ are distinct and add no extra palindromic subarrays.

Case 2: $$$a$$$ is not a permutation of $$${1,2,3, \dots ,n}$$$.

If the array $$$a$$$ is not a permutation, we can choose $$$x$$$ to be any integer that does not appear in $$$a$$$. Let $$$z$$$ be the last element of the array, and choose $$$y$$$ as any integer different from both $$$x$$$ and $$$z$$$. These three numbers will always be distinct and add no extra palindromic subarrays.

Time Complexity: $$$O(n + k)$$$ per testcase.

#include<bits/stdc++.h>
using namespace std;
 
int main(){
 
    int t;
    cin >> t;
 
    while(t--){
        
        int n, k;
        cin >> n >> k;

        vector<int> a(n), cnt(n + 1, 0);
        for(int i = 0; i < n; i++) cin >> a[i], cnt[a[i]]++;

        int x = -1;
        for(int i = 1; i <= n; i++) if(cnt[i] == 0){
            x = i;
            break;
        }

        if(x == -1){
            for(int i = 0; i < k; i++) cout << a[n - 3 + (i % 3)] << ' ';
            cout << '\n';
        }
        else{
            int y = -1;
            for(int i = 1; i <= n; i++) if(i != x && i != a[n - 1]){
                y = i;
                break;
            }
            vector<int> v = {x, y, a[n - 1]};
            for(int i = 0; i < k; i++) cout << v[i % 3] << ' ';
            cout << '\n';
        }

    }
}

Note that if $$$[0,2,1]$$$ is a subsequence of permutation $$$p$$$, any interval that includes $$$0$$$ and $$$1$$$ must also include $$$2$$$. This implies that $$$\operatorname{mex}$$$ of any interval will not be equal to $$$2$$$. So, $$$2 \notin M$$$. Hence, $$$\operatorname{mex}(M) \le 2$$$.

Thus, we can always ensure that $$$\operatorname{mex}(M) \le 2$$$. Now, we only need to check when $$$\operatorname{mex}(M) = 0$$$ and $$$\operatorname{mex}(M) = 1$$$ are possible.

For $$$\operatorname{mex}(M)$$$ to be equal to $$$0$$$, $$$\operatorname{mex}$$$ of every interval must be positive. So, every interval must include $$$0$$$. This is possible only when all intervals intersect at a common point — that is, there exists at least one point that lies within every interval. Then we place $$$0$$$ at some common point and fill the remaining permutation.

Otherwise, for $$$\operatorname{mex}(M)$$$ to be equal to $$$1$$$, $$$\operatorname{mex}$$$ of each interval must not be equal to $$$1$$$. To ensure this, we have to place $$$0$$$ and $$$1$$$ in such a way that if an interval includes $$$0$$$, it must also include $$$1$$$. This is possible if there exists a point that is not simultaneously the starting point of one interval and the ending point of another. In other words, we should be able to find a position that does not act as both a left and a right boundary. Then we place $$$0$$$ at such a point and $$$1$$$ adjacent to it.

Else, we place $$$[0,2,1]$$$ as a subsequence first and then build the remaining permutation.

Time Complexity: $$$O(n + m)$$$ per testcase.

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF (int)1e18

void Solve() 
{
    
    int n, m; cin >> n >> m;
    
    vector <int> l(m), r(m), f(n + 1), st(n + 1, 0), en(n + 1);
    for (int i = 0; i < m; i++){
        cin >> l[i] >> r[i];
        st[l[i]] = 1;
        en[r[i]] = 1;
        for (int j = l[i]; j <= r[i]; j++){
            f[j]++;
        }
    }
    
    vector <int> ans(n + 1, -1);
    
    auto fill = [&](){
        vector <bool> used(n, false);
        for (int i = 1; i <= n; i++) if (ans[i] != -1) used[ans[i]] = true;
        
        int p = 0;
        for (int i = 1; i <= n; i++){
            if (ans[i] == -1){
                while (used[p]) p++;
                
                ans[i] = p;
                used[p] = true;
            }
        }
        
        for (int i = 1; i <= n; i++){
            cout << ans[i] << " \n"[i == n];
        }
    };
    
    for (int i = 1; i <= n; i++){
        if (f[i] == m){
            int ptr = 1;
            ans[i] = 0;
            
            fill();
            return;
        }
    }
    
    for (int i = 1; i < n; i++){
        if (en[i] == 0){
            ans[i] = 0;
            ans[i + 1] = 1;
            fill();
            return;
        }
        
        if (st[i + 1] == 0){
            ans[i] = 1;
            ans[i + 1] = 0;
            fill();
            return;
        }
    }
    
    assert(n >= 3);
    ans[1] = 0;
    ans[2] = 2;
    ans[3] = 1;
    
    fill();
}

int32_t main() 
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
    cin >> t;
    for(int i = 1; i <= t; i++) 
    {
        Solve();
    }
    
    return 0;
}

We have to construct a tree with $$$n$$$ vertices such that $$$S = \sum_{{u, v} \in E} (u \cdot v)$$$ is a perfect square.

Instead of making it any random perfect square, let's try to make $$$S = (f(n))^2$$$ where $$$f(n)$$$ is an integer function of $$$n$$$.

Now, let's check if we can make $$$f(n) = n$$$. For $$$n = 5$$$, we can consider the following tree

where $$$S = 25 = (5)^2$$$.

Now that we know we have a tree $$$T$$$ with $$$n$$$ ($$$=5$$$) vertices having $$$S = n^2$$$. Using this, let's try to make a tree $$$T'$$$ with $$$n + 1$$$ vertices such that $$$S' = (n + 1)^2$$$. Note that $$$S' - S = 2n + 1$$$. So, while constructing $$$T'$$$, we have to add a new vertex $$$(n + 1)$$$ and also adjust this extra sum $$$2n + 1$$$.

We can achieve this in the following manner:

• add an edge between $$$1$$$ and $$$n + 1$$$,
• remove the edge between $$$1$$$ and $$$n$$$,
• add an edge between $$$2$$$ and $$$n$$$.

This analogy can be extended for all $$$n \ge 5$$$. Such trees have the following structure:

So, we can always make $$$S = n^2$$$ for all $$$n \ge 5$$$. For $$$n \lt 5$$$, we can just print sample outputs.

One can also assume $$$f(n) = n + 1$$$ and construct a similar solution with $$$S = (n + 1)^2$$$.

Time Complexity: $$$O(n)$$$ per testcase.

#include<bits/stdc++.h>
using namespace std;
 
int main(){
 
    int t;
    cin >> t;
 
    while(t--){
 
        int n;
        cin >> n;
        
        if(n == 2){
            cout << -1 << '\n';
            continue;
        }
 
        if(n == 3){
            cout << "1 3\n2 3\n";
            continue;
        }
 
        if(n == 4){
            cout << "1 2\n3 1\n4 1\n";
            continue;
        }
 
        cout << "1 2\n";
        cout << "2 3\n";
        cout << "3 4\n";
 
        cout << "1 " << n << '\n';
 
        for(int i = 5; i < n; i++) cout << 2 << ' ' << i << '\n';
    }
}

When the value of $$$f$$$ is 1 for $$$[l_i, r_i]$$$, all numbers in $$$[l_i, r_i]$$$ are either $$$\leq x$$$ or $$$\geq x$$$.

We observe that for each interval, we need to divide the intervals into S-intervals (smaller) and B-intervals (bigger). S-intervals can only contain numbers $$$\leq x$$$, and B-intervals can only contain numbers $$$\geq x$$$.

Assuming we have fixed the S-intervals and B-intervals. For each index $$$i$$$, there are 4 types:

• Type 1: $$$i$$$ is covered only by S-intervals;
• Type 2: $$$i$$$ is covered only by B-intervals;
• Type 3: $$$i$$$ is covered by both S-intervals and B-intervals;
• Type 4: $$$i$$$ is covered by neither S-intervals nor B-intervals.

Let $$$cnt_s$$$ be the number of values $$$ \lt x$$$, and $$$cnt_b$$$ be the number of values $$$ \gt x$$$.

When there are no type 4 indices, we only need to check whether:

• $$$cnt_s \leq$$$ (total number of type 1 indices)

• $$$cnt_b \leq$$$ (total number of type 2 indices)

When type 4 indices exist, we only need to make a slight modification to the condition (this modification is left to the reader).

Consider a simpler case: all intervals are non-overlapping. In this case, the problem reduces to a classic knapsack problem, where each interval becomes an independent item. We consider extending the idea of DP to the original problem.

We find that intervals that are contained within others are useless and can be removed. Then, the intervals can be sorted by their left endpoints. This way, for $$$i \lt j$$$, we can ensure $$$l_i \lt l_j$$$ and $$$r_i \lt r_j$$$. Then, we perform DP based on the order of the intervals.

We define:

$$$dp[i][j][k = 0 \text{ or } 1]$$$: For the first $$$i$$$ intervals, the total number of type 1 indices is $$$j$$$, and the last interval is an S-interval ($$$k = 0$$$) or a B-interval ($$$k = 1$$$), the maximum total number of type 2 indices obtained.

Let $$$inslen[i]$$$ be the length of the intersection between the $$$i$$$-th interval and the $$$(i-1)$$$-th interval.

Transitions:

• $$$dp[i][j][0] = \max(dp[i-1][j - inslen[i]][0], dp[i-1][j - inslen[i]][1] - inslen[i])$$$
• $$$dp[i][j][1] = \max(dp[i-1][j][1] + inslen[i], dp[i-1][j + inslen[i]][1] + inslen[i])$$$

Note: For intervals $$$(i-2)$$$, $$$(i-1)$$$, $$$i$$$, if the type of interval $$$(i-1)$$$ is different from both $$$(i-2)$$$ and $$$i$$$, and $$$r[i-2] \geq l[i]$$$, some overlapping parts may be subtracted repeatedly. However, we find that this does not affect the final answer because it is not better than the answer when all three intervals are of the same type. Here, a common DP idea is applied: if "incorrect" states are recorded but they cannot be optimal, the DP transitions can remain unchanged (a similar idea is used in: https://codeforces.me/contest/1859/problem/E).

State 1	State 2
)
Some overlapping parts (in the middle) are subtracted repeatedly.	Better because the value range of the middle positions is strictly larger.

Afterward, answering queries using the DP array is trivial. The time complexity is $$$O(n^2)$$$.

There is another DP approach. Let $$$b[i]$$$ be the smallest $$$j \leq i$$$ such that $$$j$$$ and $$$i$$$ are covered by the same interval. Then, if position $$$i$$$ is filled with a number $$$ \lt x$$$, we can deduce that all numbers in $$$a'[b[i], \ldots, i]$$$ must be $$$ \lt x$$$, and so on. This way, we can write a DP that transitions position by position, without pre-processing each interval.

For details, refer to Dominater069 's code.

#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <bitset>
#include <unordered_map>
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef double db;
typedef long long ll;
typedef unsigned long long ull;
const int N=3010;
const int LOGN=28;
const ll  TMD=0;
const ll  INF=100000000;
int T,n,m;
int a[N],cnt[N],mxr[N];
int dp[N][N][2];

/*
 * stuff you should look for
 * [Before Submission]
 * array bounds, initialization, int overflow, special cases (like n=1), typo
 * [Still WA]
 * check typo carefully
 * casework mistake
 * special bug
 * stress test
 */

//--------------------------------------------------------------------------

struct seg
{
	int l,r;

	seg() {}

	seg(int l,int r):l(l),r(r){}

	int len()
	{
	    return r-l+1;
	}
};

seg getins(seg x,seg y)
{
	if(x.l>y.l) swap(x,y);
	if(x.r<y.l) return seg(INF,INF);
	if(x.r<y.r) return seg(y.l,x.r);
	else return seg(y.l,y.r);
}

//--------------------------------------------------------------------------

void init()
{
    cin>>n>>m;
    for(int i=0;i<=n;i++)
        mxr[i]=0;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=1;i<=m;i++)
    {
        int l,r;
        cin>>l>>r;
        mxr[l]=max(mxr[l],r);
    }
    for(int i=0;i<=n+4;i++)
        for(int j=0;j<=n+4;j++)
            dp[i][j][0]=dp[i][j][1]=-INF;
}

void solve()
{
    int sz,cfree=0;
    vector<int> tag(n+4);
    vector<seg> vs;
    for(int i=1;i<=n;i++)
    {
        if(!mxr[i]) continue;
        if(vs.empty()||vs.back().r<mxr[i])
            vs.push_back(seg(i,mxr[i]));
    }
    sz=vs.size();
    dp[1][0][0]=vs[0].len();
    dp[1][vs[0].len()][1]=0;
    for(int i=2;i<=sz;i++)
    {
        seg cur=vs[i-1],ins=getins(vs[i-2],vs[i-1]);
        int len_ins=(ins.l==INF?0:ins.len());
        for(int j=0;j<=n;j++)
        {
            dp[i][j][0]=max(dp[i][j][0],dp[i-1][j][0]+cur.len()-len_ins);
            if(j+len_ins<=n)
                dp[i][j][0]=max(dp[i][j][0],dp[i-1][j+len_ins][1]+cur.len()-len_ins);
            if(j-(cur.len()-len_ins)>=0)
            {
                dp[i][j][1]=max(dp[i][j][1],dp[i-1][j-(cur.len()-len_ins)][1]);
                dp[i][j][1]=max(dp[i][j][1],dp[i-1][j-(cur.len()-len_ins)][0]-len_ins);
            }
        }
    }
    for(int i=0;i<vs.size();i++)
        for(int j=vs[i].l;j<=vs[i].r;j++)
            tag[j]=1;
    for(int i=1;i<=n;i++)
        if(!tag[i]) cfree++;
    for(int i=1;i<=n;i++)
    {
        int s=0,b=0;
        for(int j=1;j<=n;j++)
        {
            if(a[j]<i) s++;
            else if(a[j]>i) b++;
        }
        int flg=0;
        for(int j=0;j<=n;j++)
        {
            int need1=max(0,s-j),need2=max(0,b-max(dp[sz][j][0],dp[sz][j][1]));
            flg|=(cfree>=need1+need2);
        }
        cout<<flg;
    }
    cout<<"\n";
}

//-------------------------------------------------------

void gen_data()
{
    srand(time(NULL));
}

int bruteforce()
{
    return 0;
}

//-------------------------------------------------------

int main()
{
    fastio;

    cin>>T;
	while(T--)
	{
		init();
		solve();

		/*

		//Stress Test

		gen_data();
		auto ans1=solve(),ans2=bruteforce();
		if(ans1==ans2) printf("OK!\n");
		else
		{
			//Output Data
 		}

		*/
	}

	return 0;
}

#include <bits/stdc++.h>
using namespace std;
#define INF (int)1e9

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

void Solve() 
{
    // x <= min or x >= max 
    // min < x < max is bad 
    // => in range if both smaller and larger exists, cooked 
    // just spam smaller at one end, and larger at other end? 
    // i <-> j if there exists interval covering both 
    // if i <-> j, cannot have diff type on i and j 
    // dp[i][number of 0s] = max number of 1s, but also need to know what is the last 0 / 1 position 
    // we can extend last character always 
    // we can extend other character only after some gap 
    // prefmax?
    
    int n, m; cin >> n >> m;
    
    vector <int> a(n + 1), f(n + 1);
    for (int i = 1; i <= n; i++){
        cin >> a[i];
        f[a[i]]++;
    }
    
    vector <int> b(n + 1), c(n + 1);
    for (int i = 1; i <= n; i++){
        b[i] = c[i] = i;
    }
    for (int i = 1; i <= m; i++){
        int l, r; cin >> l >> r;
        for (int j = l; j <= r; j++){
            b[j] = min(b[j], l);
            c[j] = max(c[j], r);
        }
    }
    
    // vector dp(n + 1, vector(n + 1, vector <int>(2, -INF)));
    // vector pref(n + 1, vector(n + 1, vector <int>(2, -INF)));
    int dp[n + 1][n + 1][2];
    int pref[n + 1][n + 1][2];
    
    for (int i = 0; i <= n; i++){
        for (int j = 0; j <= n; j++){
            for (int k = 0; k < 2; k++){
                dp[i][j][k] = -INF;
                pref[i][j][k] = -INF;
            }
        }
    }
    
    dp[0][0][0] = dp[0][0][1] = 0;
    pref[0][0][0] = pref[0][0][1] = 0;
    
    for (int i = 1; i <= n; i++){
        for (int x = 0; x <= n; x++){
            for (int y = 0; y < 2; y++){
                for (int z = 0; z < 2; z++){
                    if (y == z){
                        int px = x - (y == 0);
                        if (px >= 0){
                            dp[i][x][y] = max(dp[i][x][y], pref[i - 1][px][z] + (y == 1));
                        }
                    } else {
                        int px = x - (y == 0);
                        int lim = b[i] - 1;
                        if (px >= 0){
                            dp[i][x][y] = max(dp[i][x][y], pref[lim][px][z] + (y == 1));
                        }
                    }
                }
                
                pref[i][x][y] = max(pref[i - 1][x][y], dp[i][x][y]);
            }
        }
    }
    
    for (int i = 1; i <= n; i++){
        int lower = 0;
        int upper = 0;
        for (int j = 1; j < i; j++) lower += f[j];
        for (int j = i + 1; j <= n; j++) upper += f[j];
        
        if (pref[n][lower][0] >= upper || pref[n][lower][1] >= upper){
            cout << "1";
        } else {
            cout << "0";
        }
    }
    cout << "\n";
}

int32_t main() 
{
    auto begin = std::chrono::high_resolution_clock::now();
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
    // freopen("in",  "r", stdin);
    // freopen("out", "w", stdout);
    
    cin >> t;
    for(int i = 1; i <= t; i++) 
    {
        //cout << "Case #" << i << ": ";
        Solve();
    }
    auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
    return 0;
}