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

TBA

Good problem

Ok problem

Bad problem

Didn't solve it, idk

TBA

TBA

Good problem

Ok problem

Bad problem

Didn't solve it, idk