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://mirror.codeforces.com/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;
}