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

TBA

TBA

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