A — The Ultimate Square
Authors: Gheal
If $$$n$$$ is odd, it is possible to create a square using all $$$n$$$ blocks.
If $$$n$$$ is even, it is possible to create a square using only the first $$$n-1$$$ blocks, since $$$n-1$$$ is odd. Can we use the last block to create a larger square?
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;
}
B — Balanced Substrings
Author: Gheal
What is the maximum number of distinct characters in a diverse string?
What is the maximum frequency of a character in a diverse string?
What is the maximum possible length a diverse string?
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;
}
C — Zero Sum Prefixes
What is the answer if $$$a_1=0$$$ and $$$a_i \neq 0$$$ for all $$$2 \le i \le n$$$?
What is the answer if $$$a_i=0$$$ and $$$a_j \neq 0$$$ for all $$$1 \le j \le n$$$, $$$j \neq i$$$?
What is the answer if there are only two indices $$$i$$$ and $$$j$$$ for which $$$a_i=a_j=0$$$?
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;
}
D — ConstructOR
Author: Gheal
If at least one of $$$a$$$ and $$$b$$$ is odd, and $$$d$$$ is even, then there are no solutions.
Without loss of generality, we will only consider the case when $$$a$$$ is odd and $$$d$$$ is even. Since the last bit of $$$a$$$ is $$$1$$$, then the last bit of $$$a|x$$$ must also be $$$1$$$.
Therefore, $$$a|x$$$ cannot be a multiple of $$$d$$$, as $$$a|x$$$ is odd, while $$$d$$$ is even.
Note that there are more cases in which no solutions exist, however they are more generalised versions of this case.
If a triplet ($$$a,b,d$$$) has no solutions, then ($$$a\cdot 2,b\cdot 2,d\cdot 2$$$) has no solutions as well.
Combined with the first hint, we can say that a triplet ($$$a,b,d$$$) has no solutions if $$$min(\text{lsb}(a),\text{lsb}(b)) \lt \text{lsb}(d)$$$.
Since both $$$a|x$$$ and $$$b|x$$$ must be divisible by $$$d$$$, we should choose an $$$x$$$ for which $$$a|x=b|x$$$.
If $$$d$$$ is odd, since $$$a,b \lt 2^30$$$, we can ensure that $$$a|x=b|x$$$ by setting the last $$$30$$$ bits of $$$c$$$ to $$$1$$$.
If $$$d$$$ is even, then the last $$$\text{lsb}(d)$$$ bits of $$$x$$$ should be set to $$$0$$$, while the other bits from the last $$$30$$$ bits should be set to $$$1$$$.
Let $$$k=\text{lsb}(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)$$$
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
void tc(){
ll a,b,c,k=0,inverse_of_2,total_inverse=1;
cin>>a>>b>>c;
a|=b;
if(a%c==0){
cout<<a<<'\n';
return;
}
while(a%2==0 && c%2==0)
a/=2,c/=2,k++;
inverse_of_2=(c+1)/2;
if(a%2==1 && c%2==0){
cout<<"-1\n";
return;
}
for(ll i=0;i<30;i++)
total_inverse=total_inverse*inverse_of_2%c;
cout<<((total_inverse<<30)-1)*(1ll<<k)<<'\n';
}
int main()
{
ios_base::sync_with_stdio(false), cin.tie(0);
ll t; cin>>t; while(t--)
tc();
}
E — Three Days Grace
Author: tibinyte
We can see that in the final multiset, each number $$$A_i$$$ from the initial multiset will be assigned to a subset of values $$$x_1, x_2,....,x_k$$$ such that their product is $$$A_i$$$. Every such multiset can be created. Also let $$$vmax$$$ be the maximum value in the initial multiset.
Consider iterating through the minimum value. To get the best maximum value that has this minimum we fixed, one can use dynamic programming $$$dp[i][j] = $$$the best possible maximum if we had number $$$i$$$ and the minimum value in the product is $$$j$$$, $$$j$$$ is a divisor of $$$i$$$. This dp can be calculated in $$$O(vmax \cdot log^2(vmax))$$$ for all values. We can also process all updates when incrementing the minimum and keeping the result with a total effort of $$$O(vmax \cdot log^2(vmax))$$$. Thus we have a total time complexity of $$$O(vmax \cdot log^2(vmax))$$$. However, this ( we hope ) won't pass.
Here is a way more elegant solution ( thanks to valeriu ):
To get things straight, we observe that when we decompose a number, we just actually write it as a product of numbers. We still consider fixing the minimum value used in our multiset, call it $$$L$$$. We will further consider that we iterate $$$L$$$ from the greatest possible value (i.e. $$$vmax$$$) to $$$1$$$, and as such, we try at each iteration to calculate the minimum possible value which will appear in any decomposition as the maximum value in said decomposition.
We shall now retain for each element the minimal maximum value in a decomposition where the minimum of that decomposition is $$$L$$$, let's say for element $$$i$$$, this value will be stored in $$$dp[i]$$$. Naturally, after calculating this value for every number, we now try to tweak the calculated values as to match the fact that, after this iteration concluded, we will decrease $$$L$$$. For further simplicity, we denote $$$L' = L - 1$$$.
So, we changed the minimum value allowed. What changes now? Well, it is easy to see that any element that is not divisible by $$$L'$$$ won't be affected by this modification, as much as it is impossible to include $$$L'$$$ in any decomposition of said number. So it remains to modify the multiples of $$$L'$$$. Let's take a such number, $$$M$$$. How can we modify $$$dp[M]$$$? Well, we can include $$$L'$$$ in the decomposition as many times as we want, and then when we decide to stop including it, we remain with a number which needs to be further decomposed. The attributed maximum of this value should already be calculated, so we can consider it as a new candidate for the update of $$$dp[M]$$$. This idea could be implemented simpler by going through multiples of $$$L'$$$, and for an element, updating $$$dp[i]$$$ with $$$dp[i / L']$$$ (by taking the minimum of either)
We now need for each iteration to keep track of the attributed maximums of each element that actually appears in our initial list. This can be done by keeping a frequency of all these elements, and after all updates, taking the (already known) maximum of the previous iteration and decreasing it until we find another element that actually appears in our set (this can be verified by simply checking the frequency). This is correct, as much as all the values gradually decrease as $$$L$$$ decreases, so their maximum would have to decrease as well.
Final time complexity: $$$O(vmax * log(vmax))$$$
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int nmax = 5e6 + 5;
int appear[nmax];
int mxval[nmax];
int toggle[nmax];
int main()
{
cin.tie(nullptr)->sync_with_stdio(false);
int t;
cin >> t;
while (t--)
{
int n, m, mn = nmax, mx = 0;
cin >> n >> m;
for (int i = 0; i <= m; ++i)
{
appear[i] = toggle[i] = mxval[i] = 0;
}
for (int i = 0, x; i < n; i++)
{
cin >> x;
appear[x] = 1;
toggle[x] = 1;
mn = min(mn, x);
mx = max(mx, x);
}
for (int i = 0; i <= mx; i++)
{
mxval[i] = i;
}
int ptr = mx, smax = mx - mn;
for (int i = mx; i >= 1; i--)
{
for (ll j = (ll)i * i; j <= mx; j += i)
{
if (appear[j])
toggle[mxval[j]]--;
mxval[j] = min(mxval[j], mxval[j / i]);
if (appear[j])
toggle[mxval[j]]++;
}
while (toggle[ptr] == 0)
ptr--;
if (i <= mn)
smax = min(smax, ptr - i);
}
cout << smax << '\n';
}
}
If there is anything wrong or unclear in this editorial, feel free to ping me or any of the other setters in the comments.