If $$$n$$$ is odd, let $$$k=\frac{n+1}{2}$$$ be the width of the last block. It is possible to create a square of side length $$$k$$$ using every block as follows:

• Line $$$1$$$ contains a $$$1 \times k$$$ block;
• Line $$$2$$$ contains a $$$1 \times 1$$$ block and a $$$1 \times (k-1)$$$ block;
• Line $$$3$$$ contains a $$$1 \times 2$$$ block and a $$$1 \times (k-2)$$$ block;
• $$$\ldots$$$
• Line $$$i$$$ contains a $$$1 \times (i-1)$$$ block and a $$$1 \times (k-i+1)$$$ block;
• $$$\ldots$$$
• Line $$$k$$$ contains a $$$1 \times (k-1)$$$ block and a $$$1 \times 1$$$ block.

Since the area of this square is $$$k^2$$$, and the $$$n+1$$$-th block has a width of $$$k$$$ tiles, the total area of the first $$$n+1$$$ blocks is equal to $$$k^2+k \lt (k+1)^2$$$. Therefore, the answer for $$$n+1$$$ is also $$$k$$$.

In conclusion, the answer for each testcase is $$$\lfloor \frac{n+1}{2} \rfloor$$$.

Time complexity per testcase: $$$O(1)$$$.

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
void testcase(){
    ll n;
    cin>>n;
    cout<<(n+1)/2<<'\n';
}
int main()
{
    ll t; cin>>t; while(t--)
       testcase();
    return 0;
}

Good problem

Ok problem

Bad problem

Didn't solve it, idk

In a diverse string, there are at most $$$10$$$ distinct characters: '0', '1', $$$\ldots$$$, '9'. Therefore, each of these characters can appear at most $$$10$$$ times in a diverse string.

With all this in mind, the maximum possible length of a diverse string is $$$10^2=100$$$. To solve this problem, we only need to check whether each substring of length $$$l \le 100$$$ is diverse.

Time complexity per testcase: $$$O(n \cdot 10^2)$$$

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
void tc(){
    ll n;
    string s;
    cin>>n>>s;
    ll ans=0;

    for(ll i=0;i<s.size();i++){

        int fr[10]{}, distinct=0, max_freq=0;

        for(ll j=i;j<s.size() && (++fr[s[j]-'0'])<=10;j++){

            max_freq=max(max_freq,fr[s[j]-'0']);
            if(fr[s[j]-'0']==1) distinct++;

            if(distinct>=max_freq) ans++;
        }
    }
    cout<<ans<<'\n';
}
int main()
{

    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    ll t; cin>>t; while(t--) tc();
    return 0;
}

Good problem

Ok problem

Bad problem

Didn't solve it, idk

Let's consider the prefix sum array $$$s=[a_1,a_1+a_2,\ldots,a_1+a_2+\ldots+a_n]$$$.

For every index $$$i$$$ such that $$$a_i=0$$$, if we change the value of $$$a_i$$$ to $$$x$$$, then every element from the suffix $$$[s_i,s_{i+1},\ldots,s_n]$$$ will be increased by $$$x$$$. Therefore, if $$$a_{i_1}=a_{i_2}=\ldots=a_{i_k}=0$$$, we'll partition array $$$s$$$ into multiple subarrays:

• $$$[s_1,s_2,\ldots,s_{i_1-1}]$$$;
• $$$[s_{i_2},s_{i_2+1},\ldots,s_{i_3-1}]$$$;
• $$$\ldots$$$
• $$$[s_{i_k},s_{i_{k+1}},\ldots,s_n]$$$;

Since none of the elements from the first subarray can be changed, it will contribute with the number of occurences of $$$0$$$ in $$$[s_1,s_2,\ldots,s_{i_1-1}]$$$ towards the final answer.

For each of the other subarrays $$$[s_l,s_{l+1},\ldots,s_r]$$$, let $$$x$$$ be the most frequent element in the subarray, appearing $$$fr[x]$$$ times. Since $$$a_l=0$$$, we can change the value of $$$a_l$$$ to $$$-x$$$. In this case, every $$$x$$$ in this subarray will become equal to $$$0$$$, and our current subarray will contribute with $$$fr[x]$$$ towards the final answer.

Time complexity per testcase: $$$O(NlogN)$$$

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const ll MAXN=2e5+5;

ll a[MAXN];
map<ll,ll> freq;

void tc(){
    ll n;
    cin>>n;
    ll maxfr=0,current_sum=0,ans=0;
    bool found_wildcard=0;
    freq.clear();
    for(ll i=0;i<n;i++){
        cin>>a[i];

        if(a[i]==0){

            if(found_wildcard) ans+=maxfr;
            else ans+=freq[0];

            found_wildcard=1;

            maxfr=0,freq.clear();
        }

        current_sum+=a[i];
        maxfr=max(maxfr,++freq[current_sum]);
    }
    if(found_wildcard) ans+=maxfr;
    else ans+=freq[0];

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

int main()
{
    ios_base::sync_with_stdio(false), cin.tie(0);
    ll t; cin>>t; while(t--)
        tc();
    return 0;
}

Good problem

Ok problem

Bad problem

Didn't solve it, idk

Let $$$k=\text{lsb}(d)$$$, where $$$\text{lsb}(d)$$$ represents the least significant bit of $$$d$$$.

Since $$$a|x$$$ and $$$b|x$$$ are multiples of $$$d$$$, the last $$$k$$$ bits of $$$a$$$ and $$$b$$$ (and also $$$x$$$) must be equal to $$$0$$$.

Otherwise, there are no solutions and we can print $$$-1$$$.

To simplify the construction process, we will try to find some $$$x$$$ such that $$$a|x=b|x=x$$$. Since we already know that the last $$$k$$$ bits of $$$a$$$, $$$b$$$ and $$$x$$$ are $$$0$$$, we will consider that the other $$$30-k$$$ of the $$$30$$$ least significant bits of $$$x$$$ are equal to $$$1$$$:

This gives the following general formula for $$$x$$$:

Now, we'll try to find some $$$p$$$ for which $$$x$$$ is a multiple of $$$d=2^k \cdot d'$$$:

Time complexity per testcase: $$$O(log d)$$$

Note that if $$$a|b$$$ is already a multiple of $$$d$$$, we can consider $$$x=a|b$$$.

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
void tc(){
    ll a,b,d,k=0,inverse_of_2,total_inverse=1;
    cin>>a>>b>>d;
    a|=b;
    if(a%d==0){
        cout<<a<<'\n';
        return;
    }
    while(a%2==0 && d%2==0)
        a/=2,d/=2,k++;
    inverse_of_2=(d+1)/2;
    if(a%2==1 && d%2==0){
        cout<<"-1\n";
        return;
    }

    for(ll i=0;i<30-k;i++)
        total_inverse=total_inverse*inverse_of_2%d;

    cout<<((total_inverse<<(30-k))-1)*(1ll<<k)<<'\n';
}
int main()
{
    ios_base::sync_with_stdio(false), cin.tie(0);
    ll t; cin>>t; while(t--)
        tc();
}

Good problem

Ok problem

Bad problem

Didn't solve it, idk

Let $$$f(i,j)$$$ be the position of the leftmost maximum in the interval $$$(i;j)$$$, $$$1 \le i \le j \le n$$$.

Let's consider an interval $$$(l;r)$$$ such that $$$f(l,r)=m$$$. For the sake of simplicity, let's assume that $$$l \lt m \lt r$$$.

Let $$$p=f(l,m-1)$$$ and $$$p_2=f(m+1,r)$$$. Since $$$a_m$$$ is the leftmost maximum in $$$(l;r)$$$, $$$p \lt m$$$ and $$$p_2 \gt m$$$, the following conditions must hold for array $$$b$$$:

• $$$b_m \gt b_p$$$
• $$$b_m \ge b_{p_2}$$$

Let's consider a binary tree where the children of node $$$u=f(l,r)$$$ are nodes $$$p=f(l,u-1)$$$ and $$$p_2=f(u+1,r)$$$, for every $$$1 \le u \le n$$$.

Note that if $$$u=l$$$, $$$f(l,l-1)$$$ is not defined, and, as such, node $$$u$$$ will have no left child. Similarly, if $$$u=r$$$, then node $$$u$$$ will have no right child.

Let $$$dp[u][x]$$$ be equal to the number of ways to assign values to every element $$$b_v$$$ from the subtree rooted in $$$u$$$, if $$$b_u=x$$$.

• If $$$u$$$ has a left child and $$$x=1$$$, then $$$dp[u][x]=0$$$;
• Otherwise, if $$$u$$$ has two children, then $$$dp[u][x]=(\sum_{i=1}^{x-1}dp[p][i]) \cdot(\sum_{i=1}^{x}dp[p_2][i])$$$;
• If $$$u$$$ only has a left child, then $$$dp[u][x]=\sum_{i=1}^{x-1}dp[p][i]$$$;
• If $$$u$$$ only has a right child, then $$$dp[u][x]=\sum_{i=1}^{x}dp[p_2][i]$$$;
• If $$$u$$$ has no children, then $$$dp[u][x]=1$$$.

To optimise the transitions, we'll also need to compute $$$sum[u][x]=\sum_{i=1}^{x} dp[u][x]$$$ alongside our normal $$$dp$$$.

Intended time complexity per testcase: $$$O(n \cdot m+n \cdot log(n))$$$

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
const ll NMAX=2e5+5,LGMAX=18,MOD=1e9+7;
int n,m;

int leftmost_maximum[LGMAX][NMAX],msb[NMAX];
int v[NMAX];

vector<vector<ll>> dp,sum;

int leftmost_maximum_query(int l, int r){
    int bit=msb[r-l+1];
    if(v[leftmost_maximum[bit][l]]>=v[leftmost_maximum[bit][r-(1<<bit)+1]]) return leftmost_maximum[bit][l];
    else return leftmost_maximum[bit][r-(1<<bit)+1];
}
int divide(int l, int r){

    if(l>r) return -1;

    int mid=leftmost_maximum_query(l,r);

    int p=divide(l,mid-1),p2=divide(mid+1,r);

    for(int i=1;i<=m;i++){
        if(p!=-1 && i==1) dp[mid][1]=0;
        else dp[mid][i]=(p>=0?sum[p][i-1]:1ll)*(p2>=0?sum[p2][i]:1ll)%MOD;

        sum[mid][i]=(sum[mid][i-1]+dp[mid][i])%MOD;
    }
    return mid;
}
void tc(){

    cin>>n>>m;
    dp.resize(n),sum.resize(n);
    for(int i=0;i<n;i++){
        cin>>v[i];

        leftmost_maximum[0][i]=i;

        dp[i].resize(m+1),sum[i].resize(m+1);
        for(int j=0;j<=m;j++) dp[i][j]=sum[i][j]=0;
    }

    for(int bit=1;bit<LGMAX;bit++){
        for(int i=0;i+(1<<bit)<=n;i++){
            if(v[leftmost_maximum[bit-1][i]]>=v[leftmost_maximum[bit-1][i+(1<<(bit-1))]])
                leftmost_maximum[bit][i]=leftmost_maximum[bit-1][i];
            else
                leftmost_maximum[bit][i]=leftmost_maximum[bit-1][i+(1<<(bit-1))];
        }
    }

    divide(0,n-1);

    cout<<sum[leftmost_maximum_query(0,n-1)][m]<<'\n';
}
int main()
{
    for(int i=2;i<NMAX;i++)
        msb[i]=msb[i-1]+((i&(i-1))==0); /// msb = floor(log2)

    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int t; cin>>t; while(t--)
        tc();

    return 0;
}

Good problem

Ok problem

Bad problem

Didn't solve it, idk

If $$$m=dist(i,j)=((j+n-i) \mod n)$$$, $$$m \gt 0$$$ and $$$b_k=a_{(i+k) \mod n}$$$, let $$$f(i,j)$$$ be a sequence of operations that performs:

• $$$b_0 = b_0 \oplus b_{m-1}$$$;
• $$$b_1 = b_1 \oplus b_{m-2}$$$;
• $$$b_2 = b_2 \oplus b_{m-3}$$$;
• $$$\ldots$$$
• $$$b_{\lfloor\frac{m-1}{2} \rfloor } = b_{\lfloor \frac{m-1}{2} \rfloor} \oplus b_{\lfloor \frac{m+2}{2} \rfloor}$$$

If $$$n$$$ is even, we can reverse array $$$a$$$ by performing $$$f(0,n-1)$$$, $$$f(\frac{n}{2},\frac{n}{2}-1)$$$ and $$$f(0,n-1)$$$, in this order.

Otherwise, if $$$n$$$ is odd, we can perform $$$f(0,n-1)$$$, $$$f(\frac{n+1}{2},\frac{n-3}{2})$$$ and $$$f(0,n-1)$$$, in this order.

One possible way to construct $$$f(i,j)$$$ is as follows:

• Perform an operation on every $$$i$$$ from $$$m-1$$$ to $$$0$$$:

• Perform an operation on every $$$i$$$ from $$$1$$$ to $$$m-1$$$:

• Perform an operation on every $$$i$$$ from $$$m-2$$$ to $$$1$$$:

• Perform an operation on every $$$i$$$ from $$$2$$$ to $$$m-2$$$:

• $$$\ldots$$$

• The last step is to perform an operation on every $$$i$$$ from $$$0$$$ to $$$\lfloor\frac{m-2}{2}\rfloor$$$:

Here, $$$(l..r)$$$ denotes $$$b_l \oplus b_{l+1} \oplus \ldots \oplus b_r$$$.

The number of operations needed for $$$f(i,j)$$$ is equal to $$$m+(m-1)+\ldots+1+(\frac{m}{2})=\frac{m\cdot(m+1)}{2}+\frac{m}{2}=\frac{m^2+2\cdot m}{2}$$$, therefore the total number of operations needed to reverse the array is $$$\frac{3}{2} \cdot (m^2+2\cdot m)$$$. Since $$$m \le n-1$$$, $$$\frac{3}{2} \cdot (m^2+2\cdot m) \le \frac{3}{2} \cdot (399^2 + 2\cdot 399) \lt 250\,000$$$.

Time complexity per testcase: $$$O(N^2)$$$

#include <bits/stdc++.h>

using namespace std;

vector<int> ans;
int n;
void add_op(int pos){
    ans.push_back(pos%n);
}
void f(int l, int r){

    if(r<l) r+=n;

    int m=r-l,direction=0,start=l;
    r--;
    while(l<=r){

        if(direction==0){
            for(int i=r;i>=l;i--)
                add_op(i);
            l++;
        }
        else{
            for(int i=l;i<=r;i++)
                add_op(i);
            r--;
        }

        direction=1-direction;
    }
    for(int i=start;i<start+m/2;i++)
        add_op(i);
}
int main()
{
    ios_base::sync_with_stdio(false), cin.tie(0);
    cin>>n;

    f(0,n-1);

    f((n+1)/2,(n-2)/2);

    f(0,n-1);

    cout<<ans.size()<<'\n';

    for(auto it : ans) cout<<it<<' ';
}

Good problem

Ok problem

Bad problem

Didn't solve it, idk