Thank you for your participation! I hope you liked atleast one problem from the set (:
Idea: satyam343
Editorial: Non-origination
Selecting the smallest two elements on the whiteboard is a good choice in the first move.
Let $$$b$$$ denote the sorted array $$$a$$$. Assume that $$$b$$$ contains only distinct elements for convenience. We prove by induction on $$$n$$$ that the maximum final score is $$$b_1 + b_3 + \ldots + b_{2n-1}$$$.
For the base case $$$n = 1$$$, the final and only possible score that can be achieved is $$$b_1$$$.
Now let $$$n > 1$$$.
Claim: It is optimal to choose $$$b_{1}$$$ with $$$b_{2}$$$ for some move.
Suppose that in some move, $$$b_{1}$$$ is choosen with $$$b_i$$$ and $$$b_{2}$$$ is choosen with $$$b_j$$$, for some $$$2 < i,j < 2n, i \not = j$$$.
The contribution to the score according to these choices is $$$\min(b_{1}, b_{i}) + \min(b_{2}, b_{j}) = b_{1} + b_{2}$$$.
However, if we had chosen $$$b_{1}$$$ and $$$b_{2}$$$ in one move, and $$$b_i$$$ and $$$b_j$$$ in the other move, the score according to these choices is $$$\min(b_{1}, b_{2}) + \min(b_{i}, b_{j}) = b_{1} + \min(b_{i}, b_{j})$$$.
As $$$i, j > 2$$$, $$$b_i > b_{2}$$$ and $$$b_j > b_{2} \implies \min(b_{i}, b_{j}) > b_2$$$. Thus, we can achieve a strictly larger score by choosing $$$b_1$$$ with $$$b_2$$$ in some move.
The choice of selecting $$$b_1$$$ and $$$b_2$$$ contributes a value of $$$b_1$$$ to the score. The maximum score that can achieved for the remaining numbers $$$[b_3, b_4, \ldots, b_{2n}]$$$ on the whiteboard in the remaining moves is $$$b_3 + b_5 + b_7 + \ldots b_{2n-1}$$$ by the induction hypothesis.
Note that we can extend the arguments for the case where $$$a$$$ has duplicate elements.
#include <bits/stdc++.h>
using namespace std;
#define ll long long
void solve(){
ll n; cin>>n;
vector<ll> a(2*n);
ll ans=0;
for(auto &it:a){
cin>>it;
}
sort(a.begin(),a.end());
for(ll i=0;i<2*n;i+=2){
ans+=a[i];
}
cout<<ans<<"\n";
return;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
freopen("error.txt", "w", stderr);
#endif
ll test_cases=1;
cin>>test_cases;
while(test_cases--){
solve();
}
cout<<fixed<<setprecision(10);
cerr<<"Time:"<<1000*((double)clock())/(double)CLOCKS_PER_SEC<<"ms\n";
}
Idea: satyam343
Editorial: satyam343
For integers $$$x$$$ ($$$\lfloor \frac{n}{2} \rfloor < x \leq n$$$), there does not exist integer $$$y$$$ ($$$y > x$$$) such that $$$y$$$ is divisible by $$$x$$$.
Consider the permutation $$$p$$$ such that $$$p=[1, n, 2, n - 1, \ldots \lceil \frac{n+1}{2} \rceil]$$$. It is valid. Why?
We have $$$\max(p_a, p_{a+1}) > \lfloor \frac{n}{2} \rfloor$$$ for all $$$1 \leq a < n - 1$$$. So we cannot ever have a pair of integers ($$$a,b$$$) such that:
- $$$1 \leq a < n - 1$$$
- $$$1 \leq b < n$$$
- $$$a \neq b$$$
- $$$p_a$$$ divides $$$p_b$$$ and $$$p_{a+1}$$$ divides $$$p_{b+1}$$$
Now, we just need to check for $$$a = n - 1$$$. First of all, notice that $$$p_a$$$ does not divide $$$p_1$$$.
There does not exist an integer $$$b$$$ ($$$2 \leq b < n - 1$$$) such that $$$p_{a+1}$$$ divides $$$p_{b+1}$$$ as $$$2 \cdot p_{a+1} \ge n$$$ and $$$p_{c+1} < n$$$ for all $$$c$$$ ($$$2 \leq c < n - 1$$$).
Note that we covered all possible pairs of indices and did not find two distinct indices $$$i$$$ and $$$j$$$ ($$$1 \leq i, j < n$$$; $$$i \neq j$$$) such that $$$p_i$$$ divides $$$p_j$$$ and $$$p_{i+1}$$$ divides $$$p_{j+1}$$$.
#include <bits/stdc++.h>
using namespace std;
#define ll long long
void solve(){
ll n; cin>>n;
ll l=1,r=n;
for(ll i=1;i<=n;i++){
if(i&1){
cout<<l<<" ";
l++;
}
else{
cout<<r<<" ";
r--;
}
}
cout<<"\n";
return;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
freopen("error.txt", "w", stderr);
#endif
ll test_cases=1;
cin>>test_cases;
while(test_cases--){
solve();
}
cout<<fixed<<setprecision(10);
cerr<<"Time:"<<1000*((double)clock())/(double)CLOCKS_PER_SEC<<"ms\n";
}
1930C - Lexicographically Largest
Idea: satyam343
Editorial: Non-origination and satyam343
Consider an array $$$c$$$ of length $$$n$$$ such that $$$c_i :=$$$ number of indices smaller than $$$i$$$ which were chosen before index $$$i$$$.
So set $$$S$$$ will be a collection of $$$a_i + i - c_i$$$ over all $$$1 \leq i \leq n$$$.
Now one might wonder what type of arrays $$$c$$$ is it possible to get.
First, it is easy to see that we should have $$$0 \leq c_i < i$$$ for all $$$i$$$. Call an array $$$c$$$ of length $$$n$$$ good, if $$$0 \leq c_i < i$$$ for all $$$1 \leq i \leq n$$$. The claim is that all good arrays of length $$$n$$$ can be obtained.
We can prove it by induction on $$$n$$$.
$$$c_1 = 0$$$ always holds. Now $$$c_2$$$ can either be $$$0$$$ or $$$1$$$. We can obtain $$$c_2 = 0$$$ by deleting the element at index $$$2$$$ before the element at index $$$1$$$. We can also obtain $$$c_2 = 1$$$ by deleting it after deleting the element at index $$$1$$$. Thus, all good arrays of length 2 can be obtained.
Now assume that it is possible to obtain all good arrays of length atmost $$$k$$$. Choose an integer $$$x$$$ ($$$0 \leq x \leq k$$$) arbitrarily. Consider the following sequence for the order of deletion:
- The elements at indices $$$1, 2, \ldots, x$$$ in the same order.
- The element at index $$$k$$$.
- The elements at indices $$$x + 1, \ldots, k - 1$$$ in the same order.
It is easy to see that the array obtained on performing the above sequence of operations is a good array of length $$$k + 1$$$ with $$$c_{k+1} = x$$$. Hence we can establish a bijection between the sequence of order of deletion and the number of good arrays.
So we have the following subproblem. We have a set $$$S$$$. We will iterate $$$i$$$ from $$$1$$$ to $$$n$$$, select an integer $$$c_i$$$ ($$$0 \leq c_i \leq i - 1$$$) and insert $$$a_i + i - c_i$$$ into set $$$S$$$ and move to $$$i + 1$$$. Now using exchange arguments, we can prove that it is never bad if we select the smallest integer $$$v$$$ ($$$0 \leq v \leq i - 1$$$) such that $$$a_i + i - v$$$ is not present in the set $$$S$$$, and assign it to $$$c_i$$$. Note that as we have $$$i$$$ options for $$$v$$$, and we would have inserted exactly $$$i-1$$$ elements before index $$$i$$$, there always exists an integer $$$v$$$ ($$$0 \leq v \leq i - 1$$$) such that $$$a_i + i - v$$$ is not present in the set $$$S$$$. You can refer to the attached submission to see how to find $$$v$$$ efficiently for each $$$i$$$.
#include <bits/stdc++.h>
using namespace std;
#define ll long long
void solve(){
ll n; cin>>n;
set<ll> used,not_used;
vector<ll> ans;
for(ll i=1;i<=n;i++){
ll x; cin>>x; x+=i;
if(!used.count(x)){
not_used.insert(x);
}
ll cur=*(--not_used.upper_bound(x)); //find the largest element(<= x) which is not in set "used"
not_used.erase(cur);
ans.push_back(cur);
used.insert(cur);
if(!used.count(cur-1)){
not_used.insert(cur-1);
}
}
sort(ans.begin(), ans.end());
reverse(ans.begin(), ans.end());
for(auto i:ans){
cout<<i<<" ";
}
cout<<"\n";
return;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
freopen("error.txt", "w", stderr);
#endif
ll test_cases=1;
cin>>test_cases;
while(test_cases--){
solve();
}
cout<<fixed<<setprecision(10);
cerr<<"Time:"<<1000*((double)clock())/(double)CLOCKS_PER_SEC<<"ms\n";
}
1930D1 - Sum over all Substrings (Easy Version)
Idea: satyam343
Editorial: satyam343
To find $$$f(s)$$$, we can partition $$$s$$$ into multiple independent substrings of length atmost $$$3$$$ and find best answer for them separately.
There always exists a string $$$g$$$ such that:
- $$$g$$$ is $$$s-good$$$
- there are $$$f(s)$$$ number of $$$\mathtt{1} $$$s in $$$g$$$
- $$$g$$$ is of the form $$$b_1 + b_2 + \ldots b_q$$$, where $$$b_i$$$ is either equal to $$$\mathtt{0}$$$ or $$$\mathtt{010}$$$.
First of all, append $$$n$$$ $$$\mathtt{0} $$$ s to the back of $$$s$$$ for our convenience. Note that this does not change the answer.
Now let us call a binary string $$$p$$$ of size $$$d$$$ nice if:
there exists a positive integer $$$k$$$ such that $$$d = 3k$$$
$$$p$$$ is of form $$$ f(\mathtt{0} , k) + f(\mathtt{1} , k) + f(\mathtt{0} , k) $$$, where $$$f(c, z)$$$ gives a string containing exactly $$$z$$$ characters equal to $$$c$$$.
Suppose binary string $$$t$$$ is one of the $$$s-good$$$ strings such that there are exactly $$$f(s)$$$ $$$\mathtt{1} $$$ s in $$$t$$$.
We claim that for any valid $$$t$$$, there always exists a binary string $$$t'$$$ such that:
- $$$t'$$$ is permutation of $$$t$$$
- $$$t'$$$ is $$$s-good$$$
- $$$t'$$$ is of the form $$$f(\mathtt{0}, d_1) + z_1 + f(\mathtt{0}, d_2) + z_2 + f(\mathtt{0}, d_3) + \ldots + z_g + f(\mathtt{0}, d_{g+1}) $$$, where $$$z_1, z_2, \ldots z_g$$$ are nice binary strings and $$$d_1, d_2, \ldots d_{g+1}$$$ are non-negative integers.
Initially, all the $$$\mathtt{1} $$$s in $$$s$$$ are unmarked. We will mark all of them and modify the string $$$t$$$ in the process.
We will do the following recursive process unless all the $$$\mathtt{1} $$$ s in $$$s$$$ are marked.
Find the index of leftmost unmarked $$$\mathtt{1} $$$ in $$$s$$$. Suppose its index is $$$x$$$. Now suppose $$$y$$$ is the largest index such that there are an equal number of $$$\mathtt{0} $$$ s and $$$\mathtt{1} $$$ s in substring $$$t[x, y]$$$. Note that $$$y$$$ will always exist as we appended some extra $$$\mathtt{0} $$$s in the starting. Now we can rearrange the characters in substring $$$t[x,y]$$$, as they will still contain an equal number of $$$\mathtt{0} $$$ s and $$$\mathtt{1} $$$ s and $$$\mathtt{1} $$$ will still be the mode of substring $$$t[x,y]$$$. Obviously rearranging the characters in $$$t[x,y]$$$ to $$$\mathtt{0} \ldots \mathtt{0} \mathtt{1} \ldots \mathtt{1}$$$ is the best we can do. We will mark all the $$$\mathtt{1} $$$ s in substring $$$s[x,y]$$$. Suppose $$$y-x+1 = 2v$$$. Now $$$t[y+1,y+v]$$$ might contain some $$$\mathtt{1} $$$ s. Say there are $$$z$$$ $$$\mathtt{1} $$$ s in $$$t[y+1,y+v]$$$ initially. We will do the following operation exactly $$$z$$$ times.
- Find the leftmost $$$\mathtt{1} $$$ in substring $$$t[y+1,y+v]$$$. Find the leftmost $$$\mathtt{0} $$$ in substring $$$t[y+v+1,2n]$$$. Swap both characters.
Now note that $$$t[x,x+3v-1]$$$ will be of form $$$f(\mathtt{0}, v) + f(\mathtt{1}, v) + f(\mathtt{0}, v)$$$. It is easy to verify that in the updated $$$t$$$, there won't be any index $$$i$$$ for which there does not exist two indices $$$1 \le l \le i \le r \le 2n$$$ such that $$$s_i$$$ is mode of $$$t[l,r]$$$.
Now we can mark all the $$$\mathtt{1} $$$ s in substring $$$s[x+2v,x+3v-1]$$$ too, as $$$t[x+v,x+3v-1]$$$ contain equal number of $$$\mathtt{0} $$$ s and $$$\mathtt{1} $$$ s.
It is not hard to conclude that the updated $$$t$$$ will be of form $$$f(\mathtt{0}, d_1) + z_1 + f(\mathtt{0}, d_2) + z_2 + f(\mathtt{0}, d_3) + \ldots + z_g + f(\mathtt{0}, d_{g+1}) $$$, where $$$z_1, z_2, \ldots z_g$$$ are nice binary strings and $$$d_1, d_2, \ldots d_{g+1}$$$ are non-negative integers.
Note that the $$$\mathtt{1}$$$ s in $$$t[x, x + 3v - 1]$$$ won't help the $$$\mathtt{1}$$$ s in $$$s[x + 3v, 2n]$$$. So, we can solve for $$$s[x + 3v, 2n]$$$ independently.
Let $$$t'$$$ be the updated $$$t$$$.
Now, carefully observe the structure of $$$t'$$$. We can replace all the substrings of the form $$$ f(\mathtt{0} , k) + f(\mathtt{1} , k) + f(\mathtt{0} , k) $$$ in $$$t'$$$ with $$$ \mathtt{0} \mathtt{1} \mathtt{0} \mathtt{0} \mathtt{1} \mathtt{0} \ldots \mathtt{0} \mathtt{1} \mathtt{0} \mathtt{0} \mathtt{1} \mathtt{0}$$$.
So the updated $$$t'$$$(say $$$t"$$$) will be of form $$$b_1 + b_2 + \ldots b_q$$$, where $$$b_i$$$ is either equal to $$$\mathtt{0}$$$ or $$$\mathtt{010}$$$.
So whenever we need to find $$$f(e)$$$ for some binary string $$$e$$$, we can always try to find a string of form $$$t"$$$ using as few $$$\mathtt{1} $$$s as possible. Notice that we can construct $$$t"$$$ greedily. You can look at the attached code for the implementation details. Also, we don't need to actually append the $$$\mathtt{0} $$$s at the back of $$$s$$$. It was just for proof purposes.
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair
#define nline "\n"
#define f first
#define s second
#define pll pair<ll,ll>
#define all(x) x.begin(),x.end()
const ll MOD=1e9+7;
const ll MAX=500500;
ll f(string s){
ll len=s.size(),ans=0,pos=0;
while(pos<len){
if(s[pos]=='1'){
ans++;
pos+=2;
}
pos++;
}
return ans;
}
void solve(){
ll n,ans=0; cin>>n;
string s; cin>>s;
for(ll i=0;i<n;i++){
string t;
for(ll j=i;j<n;j++){
t.push_back(s[j]);
ans+=f(t);
}
}
cout<<ans<<nline;
return;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
freopen("error.txt", "w", stderr);
#endif
ll test_cases=1;
cin>>test_cases;
while(test_cases--){
solve();
}
cout<<fixed<<setprecision(10);
cerr<<"Time:"<<1000*((double)clock())/(double)CLOCKS_PER_SEC<<"ms\n";
}
1930D2 - Sum over all Substrings (Hard Version)
Idea: satyam343
Editorial: satyam343
We can use the idea of D1 and dynamic programming to solve in $$$O(n)$$$.
Suppose $$$dp[i][j]$$$ denotes $$$f(s[i,j])$$$ for all $$$1 \le i \le j \le n$$$.
Performing the transition is quite easy.
If $$$s_i = \mathtt{1}$$$, $$$dp[i][j]=1+dp[i+3][j]$$$, otherwise $$$dp[i][j]=dp[i+1][j]$$$. Note that $$$dp[i][j] = 0$$$ for if $$$i > j$$$.
So if we fix $$$j$$$, we can find $$$dp[i][j]$$$ for all $$$1 \le i \le j$$$ in $$$O(n)$$$, and the original problem in $$$O(n^2)$$$.
Now, we need to optimise it.
Suppose $$$track[i] = \sum_{j=i}^{n} dp[i][j]$$$ for all $$$1 \le i \le n$$$, with base condition that $$$track[i] = 0$$$ if $$$i > n$$$.
There are two cases:
- $$$s_i = \mathtt{0}$$$ :
- $$$track[i] = \sum_{j=i}^{n} dp[i][j]$$$
- $$$track[i] = dp[i][i] + \sum_{j=i+1}^{n} dp[i][j]$$$
- $$$track[i] = dp[i][i] + \sum_{j=i+1}^{n} dp[i+1][j]$$$
- $$$track[i] = track[i+1]$$$ as $$$dp[i][i]=0$$$
- $$$s_i = \mathtt{1}$$$ :
- $$$track[i] = \sum_{j=i}^{n} dp[i][j]$$$
- $$$track[i] = \sum_{j=i}^{n} 1 + dp[i+3][j]$$$
- $$$track[i] = n - i + 1 + \sum_{j=i+3}^{n} dp[i+3][j]$$$ as $$$dp[i+3][i]=dp[i+3][i+1]=dp[i+3][i+2]=0$$$
- $$$track[i] = n - i + 1 + \sum_{j=i+3}^{n} dp[i+3][j]$$$
- $$$track[i] = n - i + 1 + track[i+3]$$$
So, the answer to the original problem is $$$\sum_{i=1}^{n} track[i]$$$, which we can do in $$$O(n)$$$.
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair
#define nline "\n"
#define f first
#define s second
#define pll pair<ll,ll>
#define all(x) x.begin(),x.end()
const ll MOD=1e9+7;
const ll MAX=500500;
void solve(){
ll n,ans=0; cin>>n;
string s; cin>>s; s=" "+s;
vector<ll> dp(n+5,0);
for(ll i=n;i>=1;i--){
if(s[i]=='1'){
dp[i]=dp[i+3]+n-i+1;
}
else{
dp[i]=dp[i+1];
}
ans+=dp[i];
}
cout<<ans<<nline;
return;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
freopen("error.txt", "w", stderr);
#endif
ll test_cases=1;
cin>>test_cases;
while(test_cases--){
solve();
}
cout<<fixed<<setprecision(10);
cerr<<"Time:"<<1000*((double)clock())/(double)CLOCKS_PER_SEC<<"ms\n";
}
1930E - 2..3...4.... Wonderful! Wonderful!
Idea: satyam343
Editorial: satyam343
Suppose you are given some array $$$b$$$ of length $$$m$$$ and a positive integer $$$k$$$. How to check whether we can get the array $$$b$$$ if we start with an array $$$a$$$ of length $$$n$$$ such that $$$a_i = i$$$ for all $$$i$$$ ($$$1 \leq i \leq n$$$)?
First of all, array $$$b$$$ should be a subsequence of $$$a$$$. Now consider an increasing array $$$c$$$ (possibly empty) such that it contains all the elements of $$$a$$$ which are not present in $$$b$$$. Now look at some trivial necessary conditions.
The length of array $$$c$$$ should divisible by $$$2k$$$, as exactly $$$2k$$$ elements were deleted in one operation.
There should be atleast one element $$$v$$$ in $$$b$$$ such that there are atleast $$$k$$$ elements smaller than $$$v$$$ in the array $$$c$$$, and alteast $$$k$$$ elements greater than $$$v$$$ in the array $$$c$$$. Why? Think about the last operation. We can consider the case of empty $$$c$$$ separately.
In fact, it turns out that these necessary conditions are sufficient (Why?).
Now, we need to find the number of possible $$$b$$$. We can instead find the number of binary strings $$$s$$$ of length $$$n$$$ such that $$$s_i = 1$$$ if $$$i$$$ is present in $$$b$$$, and $$$s_i=0$$$ otherwise.
For given $$$n$$$ and $$$k$$$, let us call $$$s$$$ good if there exists some $$$b$$$ which can be achieved from $$$a$$$.
Instead of counting strings $$$s$$$ which are good, let us count the number of strings which are not good.
For convenience, we will only consider strings $$$s$$$ having the number of $$$\mathtt{0}$$$'s divisible by $$$2k$$$.
Now, based on the conditions in hint $$$2$$$, we can conclude that $$$s$$$ is bad if and only if there does not exist any $$$1$$$ between the $$$k$$$-th $$$0$$$ from the left and the $$$k$$$-th $$$0$$$ from the right in $$$s$$$.
Let us compress all the $$$\mathtt{0}$$$'s between the $$$k$$$-th $$$0$$$ from the left and the $$$k$$$-th $$$0$$$ from the right into a single $$$0$$$ and call the new string $$$t$$$. Note that $$$t$$$ will have exactly $$$2k - 1$$$ $$$\mathtt{0}$$$'s. We can also observe that for each $$$t$$$, a unique $$$s$$$ exists. This is only because we have already fixed the parameters $$$n$$$ and $$$k$$$. Thus the number of bad $$$s$$$ having exactly $$$x$$$ $$$\mathtt{1}$$$'s is $$${{x + 2k - 1} \choose {2k - 1}}$$$ as there are exactly $$${{x + 2k - 1} \choose {2k - 1}}$$$ binary strings $$$t$$$ having $$$2k - 1$$$ $$$\mathtt{0}$$$'s and $$$x$$$ $$$\mathtt{1}$$$'s.
Finally, there are exactly $$$\binom{n}{x} - \binom{x + 2k - 1}{2k - 1}$$$ good binary strings $$$s$$$ having $$$x$$$ $$$\mathtt{1}$$$'s and $$$n-x$$$ $$$\mathtt{0}$$$'s. Now, do we need to find this value for each $$$x$$$ from $$$1$$$ to $$$n$$$? No, as the number($$$n-x$$$) of $$$\mathtt{0}$$$'s in $$$s$$$ should be a multiple of $$$2k$$$. There are only $$$O(\frac{n}{2k})$$$ useful candidates for $$$x$$$.
Thus, our overall complexity is $$$O(n \log(n))$$$ (as $$$\sum_{i=1}^{n} O(\frac{n}{i}) = O(n \log(n))$$$).
#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
#define ll long long
const ll INF_ADD=1e18;
#define pb push_back
#define mp make_pair
#define nline "\n"
#define f first
#define s second
#define pll pair<ll,ll>
#define all(x) x.begin(),x.end()
const ll MOD=998244353;
const ll MAX=5000500;
vector<ll> fact(MAX+2,1),inv_fact(MAX+2,1);
ll binpow(ll a,ll b,ll MOD){
ll ans=1;
a%=MOD;
while(b){
if(b&1)
ans=(ans*a)%MOD;
b/=2;
a=(a*a)%MOD;
}
return ans;
}
ll inverse(ll a,ll MOD){
return binpow(a,MOD-2,MOD);
}
void precompute(ll MOD){
for(ll i=2;i<MAX;i++){
fact[i]=(fact[i-1]*i)%MOD;
}
inv_fact[MAX-1]=inverse(fact[MAX-1],MOD);
for(ll i=MAX-2;i>=0;i--){
inv_fact[i]=(inv_fact[i+1]*(i+1))%MOD;
}
}
ll nCr(ll a,ll b,ll MOD){
if(a==b){
return 1;
}
if((a<0)||(a<b)||(b<0))
return 0;
ll denom=(inv_fact[b]*inv_fact[a-b])%MOD;
return (denom*fact[a])%MOD;
}
ll n,k;
ll ways(ll gaps,ll options){
gaps--;
ll now=nCr(gaps+options-1,options-1,MOD);
return now;
}
void solve(){
cin>>n;
for(ll k=1;k<=(n-1)/2;k++){
ll ans=1;
for(ll deleted=2*k;deleted<=n-1;deleted+=2*k){
ll options=2*k,left_elements=n-deleted;
ans=(ans+ways(left_elements+1,deleted+1)-ways(left_elements+1,options)+MOD)%MOD;
}
cout<<ans<<" ";
}
cout<<nline;
return;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
freopen("error.txt", "w", stderr);
#endif
ll test_cases=1;
cin>>test_cases;
precompute(MOD);
while(test_cases--){
solve();
}
cout<<fixed<<setprecision(10);
cerr<<"Time:"<<1000*((double)clock())/(double)CLOCKS_PER_SEC<<"ms\n";
}
1930F - Maximize the Difference
Idea: satyam343
Editorial: satyam343
For an array $$$b$$$ consiting of $$$m$$$ non-negative integers, $$$f(b) = \max\limits_{p=1}^{m} ( \max\limits_{i = 1}^{m} (b_i | b_p) - \min\limits_{i = 1}^{m} (b_i | b_p))$$$. In other, we can get the maximum possible value by choosing $$$x=b_p$$$ for some $$$p$$$ ($$$1 \leq p \leq m$$$).
$$$f(b)$$$ is the maximum value of $$$b_i \land $$$ ~ $$$b_j$$$ over all pairs of ($$$i,j$$$) ($$$1 \leq i,j \leq m$$$), where $$$\land$$$ is the bitwise AND operator, and ~ is the bitwise One's complement operator.
Let us see how to find $$$f(b)$$$ in $$$O(n \log(n))$$$ first. We will focus on updates later. Let us have two sets $$$S_1$$$ and $$$S_2$$$ such that
- $$$S_1$$$ contains all submasks of $$$b_i$$$ for all $$$1 \leq i \leq m$$$
- $$$S_2$$$ contains all submasks of ~$$$b_i$$$for all $$$1 \leq i \leq m$$$
We can observe that $$$f(b)$$$ is the largest element present in both sets $$$S_1$$$ and $$$S_2$$$.
Now, we can insert all submasks naively. But it would be pretty inefficient. Note that we need to insert any submask atmost once in either of the sets.
Can you think of some approach in which you efficiently insert all the non-visited submasks of some mask?
insert_submask(cur, S){
return if mask cur is present in S
add mask cur to the set S
vec = list of all the set bits of the mask cur
for i in vec:
insert_submask(cur - 2^i)
}
Note that the above pseudo code inserts all the all submasks efficiently. As all the masks will be visited atmost once, the amortised complexity will be $$$O(n \log(n)^2)$$$. Note that instead of using a set, we can use a boolean array of size $$$n$$$ to reduce the complexity to $$$O(n \log(n))$$$.
Thus, we can use the above idea to find $$$f(b)$$$ in $$$O(n \log(n))$$$. For each $$$i$$$ from $$$1$$$ to $$$m$$$, we can insert all submasks of $$$b_i$$$ into set $$$S_1$$$ and insert all the submasks of ~$$$b_i$$$ into set $$$S_2$$$.
The above idea hints at how to deal with updates. If we need to append an element $$$z$$$ to $$$b$$$, we can just insert all submasks of $$$z$$$ into set $$$S_1$$$ and insert all the submasks of ~$$$z$$$ into set $$$S_2$$$.
Hence, the overall complexity is $$$O(n \log(n))$$$.
#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair
#define nline "\n"
#define f first
#define s second
#define pll pair<ll,ll>
#define all(x) x.begin(),x.end()
const ll MAX=100100;
void solve(){
ll n,q; cin>>n>>q;
ll till=1,len=1;
while(till<n){
till*=2;
len++;
}
ll ans=0;
vector<vector<ll>> track(2,vector<ll>(till+5,0));
auto add=[&](ll x,ll p){
queue<ll> trav;
if(track[p][x]){
return;
}
trav.push(x); track[p][x]=1;
while(!trav.empty()){
auto it=trav.front();
trav.pop();
if(track[0][it]&track[1][it]){
ans=max(ans,it);
}
for(ll j=0;j<len;j++){
if(it&(1<<j)){
ll cur=(it^(1<<j));
if(!track[p][cur]){
track[p][cur]=1;
trav.push(cur);
}
}
}
}
};
ll supermask=till-1;
vector<ll> a(q+5);
for(ll i=1;i<=q;i++){
ll h; cin>>h;
a[i]=(h+ans)%n;
add(a[i],0);
add(supermask^a[i],1);
cout<<ans<<" \n"[i==q];
}
return;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
freopen("error.txt", "w", stderr);
#endif
ll test_cases=1;
cin>>test_cases;
while(test_cases--){
solve();
}
cout<<fixed<<setprecision(10);
cerr<<"Time:"<<1000*((double)clock())/(double)CLOCKS_PER_SEC<<"ms\n";
}
1930G - Prefix Max Set Counting
Idea: satyam343
Editorial: satyam343
Consider some subsequence $$$S$$$ of $$$[1,2, \ldots n]$$$ such that there exists atleast one pre-order $$$a$$$ such that $$$F(a)=S$$$. Look for some non-trivial properties about $$$S$$$. Node $$$S_i$$$ will be visited before the node $$$S_{i+1}$$$.
Assume $$$|S|=k$$$. First of all, we should $$$S_1=1$$$ and $$$S_k = n$$$. There cannot exists there distinct indices $$$a, b$$$ and $$$c$$$ ($$$1 \leq a < b < c \leq |k|$$$) such that $$$S_c$$$ lies on the path from $$$S_a$$$ to $$$S_b$$$. Assume $$$LCA_i$$$ is the lowest common ancestor of $$$S_i$$$ and $$$S_{i+1}$$$. For all $$$i$$$($$$1 \leq i <k$$$), the largest value over all the nodes on the unique path from $$$S_i$$$ to $$$S_{i+1}$$$ should be $$$S_{i+1}$$$.
Suppose $$$nax_p$$$ is the maximum value in the subtree of $$$p$$$. There is one more important restriction if $$$S_i$$$ does not lie on the path from $$$S_{i+1}$$$ to $$$1$$$. Suppose $$$m$$$ is the child of $$$LCA_i$$$, which lies on the path from $$$S_i$$$ to $$$LCA_i$$$. We should have $$$S_{i+1} > nax_m$$$. In fact, if you observe carefully you will realise that we should have $$$S_i = nax_m$$$.
Let us use dynamic programming. Suppose $$$dp[i]$$$ gives the number of valid subsequences(say $$$S$$$) such that the last element of $$$S$$$ is $$$i$$$. Note that the answer to our original problem will be $$$dp[n]$$$.
Suppose $$$nax(u,v)$$$ denotes the maximum value on the path from $$$u$$$ to $$$v$$$(including the endpoints).
Let us have a $$$O(n^2)$$$ solution first.
We have $$$dp[1]=1$$$.
Suppose we are at some node $$$i$$$($$$i > 1$$$), and we need to find $$$dp[i]$$$. Let us consider some node $$$j$$$($$$1 \le j < i$$$) and see if we can append $$$i$$$ to all the subsequences which end with node $$$j$$$. If we can append, we just need to add $$$dp[j]$$$ to $$$dp[i]$$$.
But how do we check if we can append $$$i$$$ to all the subsequences that end with node $$$j$$$?
Check hints 2 and 3.
So, we have a $$$n^2$$$ solution now.
We need to optimise it now.
We will move in the increasing value of the nodes(from $$$2$$$ to $$$n$$$) and calculate the $$$dp$$$ values.
Suppose $$$nax(1, par_i) = v$$$, where $$$par_i$$$ denotes the parent of $$$i$$$.
Assume we go from node $$$j$$$($$$j < i$$$) to node $$$i$$$.
There are two cases:
$$$j$$$ lies on the path from $$$1$$$ to $$$i$$$: This case is easy, as we just need to ensure that $$$nax(j,par_i) = j$$$. We can add $$$dp[j]$$$ to $$$dp[i]$$$ if we have $$$nax(j,par_i) = j$$$. Note that there exists only one node(node $$$v$$$) for which might add $$$dp[v]$$$ to $$$dp[i]$$$
$$$j$$$ does not lie on the path from $$$1$$$ to $$$i$$$ : We will only consider the case in which $$$dp[j]$$$ will be added to $$$dp[i]$$$. Suppose $$$lca$$$ is the lowest common ancestor of $$$j$$$ and $$$i$$$, and $$$m$$$ is the child of $$$lca$$$, which lies on the path from $$$j$$$ to $$$lca$$$. Notice that the largest value in the subtree of $$$m$$$ should be $$$j$$$. This observation is quite helpful. We can traverse over all the ancestors of $$$i$$$. Suppose that we are at ancestor $$$u$$$. We will iterate over all the child(say $$$c$$$) of $$$u$$$ such that $$$nax_c < i$$$, and add $$$dp[nax_c]$$$ to $$$dp[i]$$$ if $$$nax(u,par_i) < nax_c$$$. Suppose $$$track[u][i]$$$ stores the sum of $$$dp[nax_c]$$$ for all $$$c$$$ such that $$$nax_c < i$$$. So we should add $$$track[u][i]$$$ to $$$dp[i]$$$. But there is a catch. This way, $$$dp[nax_c]$$$ will also get added $$$dp[i]$$$ even when $$$nax_c < nax(u, par_i)$$$. So, we need to subtract some values, which is left as an exercise for the readers. Now, $$$track[u][d] = track[u][d-1] + dp[nax_c]$$$ if $$$nax_c = d$$$. So, instead of keeping a two-dimensional array $$$track$$$, we can just maintain a one-dimensional array $$$track$$$. Note that we will only need the sum of $$$track[u]$$$ for all the ancestors of $$$i$$$, which we can easily calculate using the euler tour.
You can look at the attached code for the implementation details.
The intended time complexity is $$$O(n \cdot \log(n))$$$.
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair
#define nline "\n"
#define f first
#define s second
#define pll pair<ll,ll>
#define all(x) x.begin(),x.end()
const ll MOD=998244353;
const ll MAX=1000100;
struct FenwickTree{
vector<ll> bit;
ll n;
FenwickTree(ll n){
this->n = n;
bit.assign(n, 0);
}
FenwickTree(vector<ll> a):FenwickTree(a.size()){
ll x=a.size();
for(size_t i=0;i<x;i++)
add(i,a[i]);
}
ll sum(ll r) {
ll ret=0;
for(;r>=0;r=(r&(r+1))-1){
ret+=bit[r];
ret%=MOD;
}
return ret;
}
ll sum(ll l,ll r) {
if(l>r)
return 0;
ll val=sum(r)-sum(l-1)+MOD;
val%=MOD;
return val;
}
void add(ll idx,ll delta) {
for(;idx<n;idx=idx|(idx+1)){
bit[idx]+=delta;
bit[idx]%=MOD;
}
}
};
vector<vector<ll>> adj;
vector<ll> tin(MAX,0),tout(MAX,0);
vector<ll> parent(MAX,0);
vector<ll> overall_max(MAX,0);
ll now=1;
vector<ll> jump_to(MAX,0),sub(MAX,0);
void dfs(ll cur,ll par){
parent[cur]=par;
tin[cur]=now++;
overall_max[cur]=cur;
for(auto chld:adj[cur]){
if(chld!=par){
jump_to[chld]=max(jump_to[cur],cur);
dfs(chld,cur);
overall_max[cur]=max(overall_max[cur],overall_max[chld]);
}
}
tout[cur]=now++;
}
vector<ll> dp(MAX,0);
void solve(){
ll n; cin>>n;
adj.clear();
adj.resize(n+5);
for(ll i=1;i<=n-1;i++){
ll u,v; cin>>u>>v;
adj[u].push_back(v);
adj[v].push_back(u);
}
now=1;
dfs(1,0);
ll ans=0;
FenwickTree enter_time(now+5),exit_time(now+5);
overall_max[0]=MOD;
dp[0]=1;
for(ll i=1;i<=n;i++){
ll p=jump_to[i];
dp[i]=(enter_time.sum(0,tin[i])-exit_time.sum(0,tin[i])-sub[p]+dp[p]+MOD+MOD)%MOD;
if(p>i){
dp[i]=0;
}
ll node=i;
while(overall_max[node]==i){
node=parent[node];
}
enter_time.add(tin[node],dp[i]);
exit_time.add(tout[node],dp[i]);
sub[i]=(enter_time.sum(0,tin[i])-exit_time.sum(0,tin[i])+MOD)%MOD;
}
cout<<dp[n]<<nline;
return;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
freopen("error.txt", "w", stderr);
#endif
ll test_cases=1;
cin>>test_cases;
while(test_cases--){
solve();
}
cout<<fixed<<setprecision(10);
cerr<<"Time:"<<1000*((double)clock())/(double)CLOCKS_PER_SEC<<"ms\n";
}
Idea: satyam343
Editorial: satyam343
$$$\operatorname{MEX}$$$ of the path from $$$u$$$ to $$$v$$$ will be the minimum value over all the nodes of $$$T$$$ which do not lie on the path from $$$u$$$ to $$$v$$$.
$$$p_1$$$ and $$$p_2$$$ are associated with the Euler tour
$$$p_1$$$ is the permutation of $$$[1,2, \ldots n]$$$ sorted in increasing order on the basis on $$$tin$$$ time observed during Euler tour. Similarly, $$$p_2$$$ is the permutation of $$$[1,2, \ldots n]$$$ sorted in increasing order based on $$$tout$$$ time. Note that any Euler tour is fine.
Now we have $$$p_1$$$ and $$$p_2$$$ with us. Suppose we need to find $$$\operatorname{MEX}$$$ of the path from $$$u$$$ to $$$v$$$. Assume that $$$tin_u < tin_v$$$ for convenience. Assume $$$T'$$$ is the forest we get if we remove all the nodes on the path from $$$u$$$ to $$$v$$$ from $$$T$$$. Our goal is to find the minimum value over all the nodes in $$$T'$$$. Assume that $$$T'$$$ is non-empty, as $$$\operatorname{MEX}$$$ will be $$$n$$$ if $$$T'$$$ is empty. Assume $$$LCA$$$ is the lowest common ancestor of $$$u$$$ and $$$v$$$. Suppose $$$m$$$ is the child of $$$LCA(u,v)$$$, which lies on the path from $$$v$$$ to $$$LCA(u,v)$$$.
Let us consider some groups of nodes $$$p$$$ such that.
- $$$tout_p < tin_u$$$
- $$$tin_u < tin_p < tin_m$$$
- $$$tin_m < tout_p < tin_v$$$
- $$$tin_v < tin_p$$$
- $$$tout_{LCA} < tout_p$$$
Note that we have precisely $$$5$$$ groups, with the $$$i$$$-th group consisting of only those nodes which satisfy the $$$i$$$-th condition.
Here comes the interesting claim. All nodes in $$$T'$$$ are present in atleast one of the above $$$5$$$ groups. There does not exist a node $$$p$$$ such that $$$p$$$ is on the path from $$$u$$$ from $$$v$$$ and $$$p$$$ is present in any of the groups.
Now, it is not hard to observe that if we consider the nodes of any group, they will form a continuous segment in either $$$p_1$$$ or $$$p_2$$$. So we can cover each group in a single query. Hence, we can find the $$$\operatorname{MEX}$$$ of the path in any round using atmost $$$5$$$ queries.
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
#define ll long long
const ll INF_ADD=1e18;
#define pb push_back
#define mp make_pair
#define nline "\n"
#define f first
#define s second
#define pll pair<ll,ll>
#define all(x) x.begin(),x.end()
const ll MOD=998244353;
const ll MAX=200200;
vector<ll> adj[MAX];
ll now=0,till=20;
vector<ll> tin(MAX,0),tout(MAX,0),depth(MAX,0);
vector<vector<ll>> jump(MAX,vector<ll>(till+1,0));
void dfs(ll cur,ll par){
jump[cur][0]=par;
for(ll i=1;i<=till;i++)
jump[cur][i]=jump[jump[cur][i-1]][i-1];
tin[cur]=++now;
for(ll chld:adj[cur]){
if(chld!=par){
depth[chld]=depth[cur]+1;
dfs(chld,cur);
}
}
tout[cur]=++now;
}
bool is_ancestor(ll a,ll b){
if((tin[a]<=tin[b])&&(tout[a]>=tout[b]))
return 1;
return 0;
}
ll lca(ll a,ll b){
if(is_ancestor(a,b))
return a;
for(ll i=till;i>=0;i--){
if(!is_ancestor(jump[a][i],b))
a=jump[a][i];
}
return jump[a][0];
}
void solve(){
ll n; cin>>n;
ll m; cin>>m;
vector<ll> a(n+5);
for(ll i=1;i<=n-1;i++){
ll u,v; cin>>u>>v;
adj[u].push_back(v);
adj[v].push_back(u);
}
now=1;
dfs(1,1);
vector<ll> p(n),q(n);
for(ll i=0;i<n;i++){
p[i]=q[i]=i+1;
}
sort(all(p),[&](ll l,ll r){
return tin[l]<tin[r];
});
sort(all(q),[&](ll l,ll r){
return tout[l]<tout[r];
});
for(auto it:p){
cout<<it<<" ";
}
cout<<endl;
for(auto it:q){
cout<<it<<" ";
}
cout<<endl;
auto query_p=[&](ll l,ll r){
ll left_pos=n+1,right_pos=-1;
for(ll i=0;i<n;i++){
ll node=p[i];
if((tin[node]>=l) and (tin[node]<=r)){
left_pos=min(left_pos,i);
right_pos=i;
}
}
ll now=n+5;
if(right_pos!=-1){
left_pos++,right_pos++;
cout<<"? 1 "<<left_pos<<" "<<right_pos<<endl;
cin>>now;
}
return now;
};
auto query_q=[&](ll l,ll r){
ll left_pos=n+1,right_pos=-1;
for(ll i=0;i<n;i++){
ll node=q[i];
if((tout[node]>=l) and (tout[node]<=r)){
left_pos=min(left_pos,i);
right_pos=i;
}
}
ll now=n+5;
if(right_pos!=-1){
left_pos++,right_pos++;
cout<<"? 2 "<<left_pos<<" "<<right_pos<<endl;
cin>>now;
}
return now;
};
while(m--){
ll u,v; cin>>u>>v;
if(tout[u]>tout[v]){
swap(u,v);
}
ll lca_node=lca(u,v);
ll ans=n;
if(lca_node==v){
ans=min(ans,query_q(1,tin[u]));
ans=min(ans,query_p(tin[u]+1,tout[v]));
ans=min(ans,query_q(tout[v]+1,now));
cout<<"! "<<ans<<endl;
ll x; cin>>x;
continue;
}
ans=min(ans,query_q(1,tin[u]));
ll consider=v;
for(auto it:adj[lca_node]){
if(is_ancestor(lca_node,it) and is_ancestor(it,v)){
consider=it;
}
}
ans=min(ans,query_p(tin[u]+1,tin[consider]-1));
ans=min(ans,query_q(tin[consider],tin[v]));
ans=min(ans,query_p(tin[v]+1,tout[lca_node]));
ans=min(ans,query_q(tout[lca_node]+1,now));
cout<<"! "<<ans<<endl;
ll x; cin>>x;
}
for(ll i=1;i<=n;i++){
adj[i].clear();
}
return;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
freopen("error.txt", "w", stderr);
#endif
ll test_cases=1;
cin>>test_cases;
while(test_cases--){
solve();
}
cout<<fixed<<setprecision(10);
cerr<<"Time:"<<1000*((double)clock())/(double)CLOCKS_PER_SEC<<"ms\n";
}
Idea: satyam343
Full Solution: Elegia
Editorial: errorgorn
It is convinient here to assign weights to $$$\mathtt{0} \to -1$$$ and $$$\mathtt{1} \to 1$$$.
Given a string $$$t$$$, we can define the prefix sum $$$p$$$ of it's weights. For example, if $$$t=\mathtt{0010111}$$$, then $$$p=[0,-1,-2,-1,-2,-1,0,1]$$$. So that if $$$t$$$ is bad and $$$i$$$ is a index that violates the definition, then $$$\max(p_0,p_1,\ldots,p_{i-1}) < \min(p_i,p_{i+1},\ldots,p_n)$$$ if $$$s_i = \mathtt{0}$$$ or $$$\min(p_0,p_1,\ldots,p_{i-1}) > \max(p_i,p_{i+1},\ldots,p_n)$$$ if $$$s_i = \mathtt{1}$$$.
Naturally, it is convinient to assume that $$$p_0 < p_n$$$. All string with $$$p_0 = p_n$$$ are clearly good and $$$p_0 > p_n$$$ is handled similarly. For strings with $$$p_0 < p_n$$$, the condition can only be violated on an index with $$$s_i = \mathtt{0}$$$.
The solution works using PIE. Let us fix a set of positions $$$I$$$ that are bad, so that if $$$i \in I$$$, then $$$s_i =\mathtt{0}$$$ and $$$\max(p_0,p_1,\ldots,p_{i-1}) < \min(p_i,p_{i+1},\ldots,p_n)$$$. Then we need to count the number of ways to construct $$$p$$$ satisfying these conditions and then add it to the answer multiplied by $$$(-1)^{|I|}$$$.
Suppose that $$$I = i_1,i_2,\ldots,i_k$$$. $$$t[1,i_1]$$$ and $$$t[i_k,n]$$$ need to be a ballot sequence of length $$$i_1-1$$$ and $$$n-i_k$$$ respectively (A001405, denote it as $$$f(n)$$$) while $$$t[i_j,i_{j+1}]$$$ needs to be bidirectional ballot sequence of length $$$i_{j+1}-i_j-1$$$ (A167510, denote it as $$$g(n)$$$). Note that in our definition of ballot sequence, we are do not require that prefixes and suffixes have strictly more $$$\mathtt{1}$$$ s thatn $$$\mathtt{0}$$$ s. It is the same sequence, but note that we need to shift it by a few places when refering to OEIS.
The first $$$n$$$ terms of $$$f$$$ is easily computed in linear time. We will focus on how to compute the first $$$n$$$ terms of $$$g$$$ in $$$O(n \log^2 n)$$$.
Computing $$$g(n)$$$ Firstly, let us consider the number of bidirectional sequences with $$$\frac{n+k}{2}$$$ $$$\mathtt{1}$$$ s and $$$\frac{n-k}{2}$$$ $$$\mathtt{0}$$$ s. We will imagine this as lattice walks from $$$(0,0)$$$ to $$$(n,k)$$$ where $$$\mathtt{1} \to (1,1)$$$ and $$$\mathtt{0} \to (1,-1)$$$. If we touch the lines $$$y=-1$$$ or $$$y=k+1$$$, the walk is invalid.
We can use the reflection method here, similar to a proof of Catalan. The number of valid walks is $$$#(*) - #(T) + #(TB) - #(TBT) ..... - #(B) + #(BT) - #(BTB) + .....$$$ where $$$#(BTB)$$$ denotes the number of walks that touch the bottom line, then the top line, then the bottom line, and then may continue to touch the top and bottom line after that.
We have $$$#(*) =$$$ $$$\binom{n}{\frac{n+k}{2}}$$$, $$$#(T) =$$$ $$$ \binom{n}{\frac{n+k+2}{2}}$$$, $$$#(TB) =$$$ $$$ \binom{n}{\frac{n+3k+4}{2}}$$$, $$$#(TBT) =$$$ $$$ \binom{n}{\frac{n+3k+6}{2}}$$$, $$$\ldots$$$, $$$#(B) = $$$ $$$\binom{n}{\frac{n+k+2}{2}}$$$, $$$#(BT) =$$$ $$$ \binom{n}{\frac{n+k+4}{2}}$$$, $$$#(BTB) =$$$ $$$ \binom{n}{\frac{n+3k+6}{2}}$$$, $$$\ldots$$$
This already gives us a method to compute $$$g(n)$$$ in $$$O(n \log n)$$$ since for a fixed $$$k$$$, we can compute the above sum in $$$O(\frac{n}{k})$$$, since only the first $$$O(\frac{n}{k})$$$ terms are not $$$0$$$.
First, notice that we can aggregate them sums without iterating on $$$k$$$, for some fixed $$$j$$$, we can find the coefficient $$$c_j$$$ of $$$\binom{n}{\frac{n+j}{2}}$$$ across all $$$k$$$. Notice that this coefficient is independent across all $$$n$$$, so we only need to compute $$$c$$$ once.
Now, note that $$$\binom{n}{\frac{n+z}{2}} = [x^z] (x^{-1} + x) ^ n$$$. So that $$$g(n) = [x^0] C \cdot (x^{-1} + x)^n$$$, where $$$C$$$ is the ogf of $$$c$$$.
From this formulation, we can describe how to compute the first $$$n$$$ terms of $$$g$$$ in $$$O(n \log^2 n)$$$ using Divide and Conquer.
$$$DnC(l,r,V)$$$ computes the $$$g(l) \ldots g(r)$$$ where $$$V$$$ is the coefficents between $$$[l-r,r-l]$$$ of $$$C \cdot (x^{-1} + x)^l$$$. $$$DnC(l,r,V)$$$ will call $$$DnC(l,m,V)$$$ and $$$DnC(m+1,r,V \cdot (x^{-1}+x)^{m-l+1})$$$. We have the reccurence $$$T(n) = 2 T(\frac{n}{2}) + O(n \log n)$$$ so $$$T(n) = O(n \log^2 n)$$$.
Of course, for constant time speedup, you can choose to split the odd and even coefficients, but that is not needed.
It is possible to compute the first $$$n$$$ of $$$g$$$ in $$$O(n \log n)$$$ but it does not improve the overall complexity of the solution.
Final Steps
Now that we obtained the $$$n$$$ terms of $$$f$$$ and $$$g$$$, let us return to the origial problem.
If $$$s_i =\mathtt{0}$$$, define $$$dp_i = f(i-1) - \sum\limits_{s_j = \mathtt{0}} dp_j \cdot g(j-i-1)$$$. Then this contributes $$$f(n-i) \cdot dp_i$$$ to the number of bad strings.
Again, we will use Divide and Conquer to perform this quickly.
Briefly, $$$DnC(l,r)$$$ will compute the values of $$$dp[l,r]$$$ given that contributions from $$$dp[1,l-1]$$$ has been transferred to $$$dp[l,r]$$$ already.
We will call $$$DnC(l,m)$$$, compute the contribution from $$$dp[l,m]$$$ to $$$dp[m+1,r]$$$ using FFT and then call $$$DnC(m+1,r)$$$. The complexity of this is $$$O(n \log^2 n)$$$.
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define ii pair<int,int>
#define iii tuple<int,int,int>
#define fi first
#define se second
#define endl '\n'
#define debug(x) cout << #x << ": " << x << endl
#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define lb lower_bound
#define ub upper_bound
#define rep(x,start,end) for(int x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
const int MOD=998244353;
ll qexp(ll b,ll p,int m){
ll res=1;
while (p){
if (p&1) res=(res*b)%m;
b=(b*b)%m;
p>>=1;
}
return res;
}
ll inv(ll i){
return qexp(i,MOD-2,MOD);
}
ll fix(ll i){
i%=MOD;
if (i<0) i+=MOD;
return i;
}
ll fac[1000005];
ll ifac[1000005];
ll nCk(int i,int j){
if (i<j) return 0;
return fac[i]*ifac[j]%MOD*ifac[i-j]%MOD;
}
const ll mod = (119 << 23) + 1, root = 62; // = 998244353
// For p < 2^30 there is also e.g. 5 << 25, 7 << 26, 479 << 21
// and 483 << 21 (same root). The last two are > 10^9.
typedef vector<ll> vl;
void ntt(vl &a) {
int n = sz(a), L = 31 - __builtin_clz(n);
static vl rt(2, 1);
for (static int k = 2, s = 2; k < n; k *= 2, s++) {
rt.resize(n);
ll z[] = {1, qexp(root, mod >> s, mod)};
rep(i,k,2*k) rt[i] = rt[i / 2] * z[i & 1] % mod;
}
vector<int> rev(n);
rep(i,0,n) rev[i] = (rev[i / 2] | (i & 1) << L) / 2;
rep(i,0,n) if (i < rev[i]) swap(a[i], a[rev[i]]);
for (int k = 1; k < n; k *= 2)
for (int i = 0; i < n; i += 2 * k) rep(j,0,k) {
ll z = rt[j + k] * a[i + j + k] % mod, &ai = a[i + j];
a[i + j + k] = ai - z + (z > ai ? mod : 0);
ai += (ai + z >= mod ? z - mod : z);
}
}
vl conv(const vl &a, const vl &b) {
if (a.empty() || b.empty()) return {};
int s = sz(a) + sz(b) - 1, B = 32 - __builtin_clz(s), n = 1 << B;
int inv = qexp(n, mod - 2, mod);
vl L(a), R(b), out(n);
L.resize(n), R.resize(n);
ntt(L), ntt(R);
rep(i,0,n) out[-i & (n - 1)] = (ll)L[i] * R[i] % mod * inv % mod;
ntt(out);
return {out.begin(), out.begin() + s};
}
int n;
string s;
int c[100005];
int f[100005];
void calc(int l,int r,vector<int> v){
while (sz(v)>(r-l)*2+1) v.pob();
if (l==r){
f[l]=v[0];
return;
}
int m=l+r>>1;
calc(l,m,vector<int>(v.begin()+(r-m),v.end()));
vector<int> a;
int t=m-l+1;
rep(x,0,t+1) a.pub(nCk(t,x)),a.pub(0);
v=conv(v,a);
calc(m+1,r,vector<int>(v.begin()+(2*t),v.end()));
}
int ans[100005];
void solve(int l,int r){
if (l==r) return;
int m=l+r>>1;
solve(l,m);
auto a=conv(vector<int>(ans+l,ans+m+1),vector<int>(f,f+(r-l)));
rep(x,m+1,r+1) if (s[x]=='0') ans[x]=fix(ans[x]-a[x-1-l]);
solve(m+1,r);
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin.exceptions(ios::badbit | ios::failbit);
fac[0]=1;
rep(x,1,1000005) fac[x]=fac[x-1]*x%MOD;
ifac[1000004]=inv(fac[1000004]);
rep(x,1000005,1) ifac[x-1]=ifac[x]*x%MOD;
rep(x,1,100005){
c[x]++;
int curr=x;
while (curr<100005){
if (curr+2<100005) c[curr+2]-=2;
if (curr+4<100005) c[curr+4]++;
if (curr+2*x+4<100005) c[curr+2*x+4]++;
curr+=2*x+4;
}
}
cin>>n;
cin>>s;
vector<int> v;
rep(x,n+1,1) v.pub(fix(c[x]+(x>=2?c[x-2]:0LL)));
calc(1,n,v);
f[0]=1;
int fin=qexp(2,n,MOD);
rep(_,0,2){
rep(x,0,n) ans[x]=(s[x]=='0')?nCk(x,x/2):0LL;
solve(0,n-1);
rep(x,0,n) if (s[x]=='0') fin=fix(fin-ans[x]*nCk((n-x-1),(n-x-1)/2));
for (auto &it:s) it^=1;
}
cout<<fin<<endl;
}
My solution to problem C is very brief, maybe it could help: https://codeforces.me/contest/1930/submission/246846484
Can you please explain, How it works ?
Think about the simplest situation: select numbers from the end of the array to the front. This can ensure that the resulting S is the lexicographically largest but not necessarily the longest because some elements might be repeated. It can be proven that you can always, in some ways, reduce those repeated elements to the ones that haven't appeared in the set. You can do the reduction through a simple iteration through the sorted array b: since the element after must be smaller than the element front, b[i]=min(b[i],b[i-1]-1), which can ensure all elements appear at most once and are lexicographically largest.
this is so much simpler lol and intuitive
I did the same thing. Don't know why they are using upper_bound to find largest element everytime when the sequence can be found beforehand.
when I did this problem, I also first came up with using upper_bound, but I felt it was too complicated for me so I came up with this way
Nice contest!
I believe my solution for C is slightly different from the editorial, and imo cleaner.
Let $$$b_i = a_i + i$$$
Now the claim is that if all the elements of $$$b$$$ are distinct, then the descending order of $$$b$$$ is the answer. Try to prove why this might be the case yourself, its not hard. I'd recommend taking some examples and trying to figure it out. ;)
The other case to handle is when there are duplicates.
Let the value $$$x$$$ repeat at least twice in $$$b$$$. Then we can always make the values $$$x$$$ and $$$x - 1$$$ instead of $$$x$$$ and $$$x$$$.
Assume that $$$a_i + i = x$$$ and $$$a_j + j = x$$$ for $$$i < j$$$.
Then to construct the values $$$x$$$ and $$$x - 1$$$ we can first delete the index $$$i$$$, resulting in $$$x$$$, and then we can delete index $$$j$$$ resulting in the value $$$x - 1$$$.
We may now repeat the above operation multiple times until all the elements of $$$b$$$ are distinct.
These observations are enough to solve the problem.
Here is my code: 246841577
Well, I thought of a similar logic & proof while contest time, but I wasn't fully convinced. Looking at your proof, to me it feels like your logic is a bit incomplete. It's obvious that if x appears n times in {y | y = ai + i}, then x, x — 1, ... , x — (n — 1) can be made. But is it really possible to make x, x — 1, ..., x — (n — 1) while not influencing other numbers? (i.e. let's say array a is {5, 4, 2} and if you take a[0] first, the result would be {6, 5, 3} but answer would be {6, 5, 4}.) So basically, my question is "is it guaranteed that such sequence of operation exists? how can you prove it?"
The point is, I'm worried about the case where your logic "Then to construct the values x and x−1 we can first delete the index i, resulting in x, and then we can delete index j resulting in the value x−1." influencing other indexs such that ai + i == x does not hold. Maybe it's just obvious and I'm just being dumb, but I thought about this for 2 hours but couldn't prove it. So if someone can prove this, I would be really greatful. Thanks in advance.
Hmmm... You're right about my proof being incomplete, and actually maybe incorrect as well.
for instance my proof idea would be incorrect for the following example -
And while the answer is
101 100 6 4
, its not because of the reason I mentioned. Its because you first delete index 3, then 4, then 2 and finally 1.So indeed my proof is incorrect, thanks for pointing it out!
But now that I think about it, our goal is to only reduce the value of index $$$j$$$ by one, and it doesn't matter how exactly we do it.
So in order to reduce the value of index $$$j$$$, let us look at index $$$j - 1$$$. If we do not wish to reduce index $$$j - 1$$$ by any value, then we can simply delete it and we managed to reduce the value of index $$$j$$$ by 1. However, if we wanted to decrease $$$j - 1$$$ as well, then we look at $$$j - 2$$$ and so on. If this keeps on happening, then eventually we will hit index $$$i$$$ which by definition we do not wish to decrease. Therefore we can delete index $$$i$$$ and the process stops. This way we have decreased the value of index $$$j$$$ without impacting any of the other numbers in between (since the in between numbers had to be decreased as well)
I hope I didn't mess up anything this time. Incase I did, kindly correct me once again :P
EDIT: Another thing that I forgot to mention is that we will start decreasing the value starting from the right-most element. If it is already at the required value, then we can simply delete it. Otherwise we do the process mentioned above. This ensures that the deletion process doesn't impact any numbers after index $$$j$$$.
I'm still not convinced. Let's call the value we want a result want[0], ..., want[n — 1]. In order your logic to work, I think you should also prove that for every i, 0 <= a[i] + i — want[i] <= i. i.e. is it possible to prove that the difference between ai + i and want[i] is not bigger than i? if this is proved, i think the claim is quite obvious.
I'll use the terminology I used above, ie. $$$b_i = a_i + i$$$
The claim is that $$$want[i] >= b_i - (i - 1)$$$, ie. I'll decrease $$$b_i$$$ by $$$i - 1$$$ times at most before deleting it. (Also note that we can't decrease $$$b_i$$$ by more than $$$i - 1$$$ since there are only $$$i - 1$$$ elements before it)
And since there are at most $$$i - 1$$$ distinct values before $$$b_i$$$, whereas the number of options for the $$$i^{th}$$$ value is $$$i$$$ (since we can decrease by $$$0, 1, 2, ..., i -1$$$) we can always find a suitable $$$want[i]$$$ such that $$$want[i] >= b_i - (i - 1)$$$
This should prove what you're asking for.
I've rarely written proofs so I really apologise for not being thorough in my proof,
I was also worried about the same thing and it turns out that there is always a way to preserve other elements while decreasing duplicate elements but I don't know how to prove this claim.
In the contest I ended of solving C with dynamic fenwick tree(?) which can answer k'th none existing integer in O(log^2(n)). O(logn) is also possible with DST, but I really didn't want to implement DST so I went for dynamic fenwick tree. My solution is O(nlog^2(n)) and it almost got TLE. For those who are interested (although I'm certain no one will be. just look at the struct fwtree part) -> https://codeforces.me/contest/1930/submission/246865035
Can you please explain your code? Even I am unable to convince myself that the elements between 2 x's will remain unchanged
you can approach this problem by greedy. if you think about it, a[0] can be a[0] + 1 ~ a[0] + 1, a[1] can be a[1] + 1 ~ a[1] + 2, ... a[n — 1] can be a[n — 1] + 1 ~ a[n — 1] + n now, we pick one numbers from each range. If there is a integer such that it is in the range a[i] + 1 ~ a[i] + i + 1, pick the biggest one. Greedy solution that chooses from small ranges (i = 0) to big ranges (i = n — 1) is correct, but I don't know why it is correct
Can you explain how your fenwick tree is finding the kth non existing number. It would be great if you could provide any reference for this. Thanks
ps:I am familiar with fenwick trees.
It's similar to binary search. what we want is the maximum index i s.t. the # numbers before i (inclusive) is smaller than k. than i + 1 would be the kth number. If size of N = 1000: initialize res = -1. you first try 512 if # numbers before 511 (== # of numbers between [0, 511]) is less than k, you add 512 to res and subtract (== # of numbers between [0, 511]) from k. than you try 256, 128, 64, ... , 1.
I was also thinking along the same lines that we should look at the first occurrence of maxiumum value in the array ai+i for every i . Then all the values after that will be subtracted by one . Then again we look for the first occurrence of maximum value and continue in the fashion. I thought of a variation in segment tree which gives the maximum and also updates the range. Can we do this question using this variation of segment tree as i haven't used this type yet. Ignore this i found the flaw in my logic
I was aware of this solution. In fact, the model solution on polygon is exactly the same.
I just included that particular solution in the editorial, as I found it easiest to explain, and it also uses a nice technique, which I liked.
A is similar to AGC001A
Damn i dont know why my code is failing in second test case all I am doing is picking the minimum and adding it with the answer how can I spot that sorting is required here?
"Instead of counting strings s which are good, let us count the number of strings which are not bad."
Shouldn't this be, the number of strings which are bad?
what he meant is,
fixed, thanks!
satyam343 orz
How to prove that it is optimal to partition s into substrings of length 3 in problem D?
D is crazy
I could not even understand the problem statement for D problem , like how does it calculate the min no of 1s required in p-good string can someone explain?
Nice choice of title for problem E. The football match played 13 years ago was the last thing I was thinking about before this round :)
why iterator in problem c need --?
need help on 1930D1 - Sum over all Substrings (Easy Version), my submission 246919948
I'm really unsure where I lost, but clearly something wrong with calc
Take a look at Ticket 17387 from CF Stress for a counter example.
Can someone explain the editorial of C? i don't understand this "The elements at indices 1,2,…,x in the same order. The element at index k . The elements at indices x+1,…,k−1 in the same order." part.
Hmm, yeah, this part looks strange... I suppose they mean the following. We have some order of deletion for array of length k. For the array of length k + 1, let's delete first k elements in the same order, but also delete k+1-st element after x deletions. Then we obtain the same good array, but with x appended to the end.
Well, I suppose your explanation makes sense. so thank you. The editorial is so bad that it is almost impossible to understand.
Btw, in problem F there is a good way to think about efficient insertions of bitmasks. Consider the graph whose vertices are all possible bitmasks, and each bitmask is connected by directed edge with all submasks that can be obtained from it by switching one bit from 1 to 0. Then the sumbasks of a mask are just vertices reachable from this mask. So we can traverse this graph in order to find all submasks. And the pseudocode in the editorial is just dfs of this graph.
I will add the editorial of D and G after waking up.
Oh no, seems like he's fallen into a coma
LOL
well, until mr satyam343 wakes up from his coma you can read the solution for G here
Never trust strangers' words on the internet
Unfortunately, I am a bit busy with my University examinations.
It is not that I am studying that much, but I will use it as an excuse.
Meanwhile, you can go through WeaponizedAutist's blog for problem G.
E is really similar to https://codeforces.me/problemset/problem/1468/H. The hints mentioned in the editorial for E is exactly the solution to this problem.
The setup of problem E is indeed the same as the problem you mentioned. It is indeed a coincidence.
We still need to do the counting part, which a good amount of participants found non-trivial.
Interestingly, our team participated in that round. My teammate solved that problem. But when I asked him to solve the problem E of my round, he didn't remember that gym problem.
Hello,
I received a notification regarding the similarity between my solution 246886924 to Problem 1930C and Yarab_Master/246865178to the same problem. While I acknowledge that our solutions may share similarities, it's important to clarify that we didn't exchange or share code intentionally. We're not acquainted, and we haven't communicated or shared solutions with each other.
I believe it's unfair to assume cheating solely based on similar approaches to problem-solving. Our solutions might align closely due to our thought processes or coding styles, but that doesn't imply rule violation.
I appreciate the efforts of the Codeforces team in implementing a system to detect potential plagiarism, but I would like to emphasize that in this case, it's a coincidence rather than deliberate copying.
I'm open to providing any additional information or clarification needed to address this matter. Thank you for organizing the round and presenting challenging problems.
Best regards, Vishal Sharma(vsvishalsharma777)
I still wait D solution -_-
For F I can't get the hints. Please can someone explain why the maximum difference will be find in that way:
For an array b consiting of m non-negative integers, f(b)=max(max(bi|bp)−min(bi|bp))
f(b) is the maximum value of bi ∧ ~ bj over all pairs
Just fix , i and j. so all we want to pick is an x , which maximizes (b[i] | x) — (b[j] | x). Now look at a particular bit of b[i] and b[j]. There are 4 cases (1,1) ; (0,0) ; (1,0) and (0,1). (1,1) and (0,0) contributes nothing. In (1,0) take the corresponding bit of x as 0 and in (0,1) take corresponding bit of x as 1. From this you shall be able to deduce f(b) = b[i] ^ ~b[j]. Hope this helps. (Note that we dont need to prove "f(b)=max(max(bi|bp)−min(bi|bp))" ).
Thanks, I did the truth table, and it's seen immediately
satyam343 please update the solutions.
satyam343 Hello? When will the solution be added?
satyam343 WHERE ARE SOLUTIONS???
Thank you for fast editorial
shit
am i the only one finding the editorial for E not understandable ?
"
Let us compress all the 0 's between the k -th 0 from the left and the k -th 0 from the right into a single 0 and call the new string t . Note that t will have exactly 2k−1 0 's. We can also observe that for each t , a unique s exists. This is only because we have already fixed the parameters n and k . Thus the number of bad s having exactly x 1 's is (x+2k−12k−1) as there are exactly (x+2k−12k−1) binary strings t having 2k−1 0 's and x 1 's."
its not necessary that in the string t we'll have exactly 2k — 1 0s
lets take this example 010100 and k is 1 if we compress the 0s inbetween the 1st zero from the left and the first zero from the right it'll become 01010 which has 3 zeros ?
also where did the x 1s come from ?? i really cant understand this tutorial
ok after afew tries i realized that in order for the idea in the tutorial to work you also have to compress the k-th zero from the left and the k-th zero from the right into the compressed segment to form a string of length (2k — 1) zeros + (n — k*2 * L) ones and another thing u'll always need to keep that we dont have a solution when and only when there is no atleast one 1 in the segment between the k-th zero from the left and the k-th zero from the right
...
Did anyone else use Small to Large Merge in Problem C? The solution runs for 700+ms but It gets Accepted!
Can you explain the idea behind this solution.
For anyone finding the editorial to Problem $$$C$$$ to be a little hard to understand, you could try to read the following a little more detailed explanation of mine:
For each $$$1 <= i <= n$$$, define $$$c_i$$$ to be the number of elements before the $$$i$$$th element in the array that are removed before the $$$i$$$th element in the process. Apparently, $$$0 <= c_i < i$$$ for all $$$1 <= i <= n$$$. Let's call the array $$$(c_i)_{i = 1} ^ n$$$ good if for each $$$1 <= i <= n$$$, the condition $$$0 <= c_i <= i - 1$$$ holds. Notice that now the problem can be rephrased as inserting the values of $$$a_i + i - c_i$$$ in some order of $$$i$$$, where $$$1 <= i <= n$$$. We now introduce and prove an interesting claim.
$$$\text{Lemma:}$$$ Given a length $$$n$$$, all good arrays $$$(c_i)_{i = 1} ^ n$$$ are achievable in the process described in the problem.
$$$\text{Proof:}$$$ Note that $$$c_1 \equiv 0$$$. Consider $$$c_2$$$: if we want $$$c_2 = 0$$$, we could simply delete the second element before deleting the first element. On the other hand, if we want $$$c_2 = 1$$$, we can just delete the first element before the second. Thus, it is clear that all good arrays of length $$$n <= 2$$$ are achievable.
Now, assume that all good arrays of length $$$n$$$ are achievable, where $$$n >= 2$$$. We now show that this implies all good arrays of length $$$n + 1$$$ are achievable. Notice that all good arrays of length $$$n + 1$$$ are formed by appending a value $$$x$$$ with $$$0 <= x <= n$$$ at the end of a good array of length $$$n$$$. For a specific good array of length $$$n$$$, and a particular value of $$$x$$$, we can make this possible by doing the following:
$$$\quad$$$ 1. delete the first $$$x$$$ values in the deletion sequence corresponding to the good array of length $$$n$$$;
$$$\quad$$$ 2. delete the $$$(n + 1)$$$ th element;
$$$\quad$$$ 3. delete the rest of the element in the deletion sequence corresponding to the good array of length $$$n$$$.
Notice how the second step doesn't affect the previous good array, and how $$$c_{n + 1}$$$ is now equal to $$$x$$$. The the good array of length $$$n + 1$$$ formed by the given good array of length $$$n$$$ appending $$$x$$$ is achievable.
Thus, by induction, for all positive integer $$$n$$$, all good arrays of length $$$n$$$ can be obtained in the process described in the problem. $$$\square$$$
We claim that the algorithm:
iterating $$$i$$$ from $$$1$$$ to $$$n$$$, insert the largest integer $$$a_i + i - c_i$$$, where $$$0 <= c_i <= i - 1$$$, that is not yet contained in $$$S$$$.
produces the lexicographically largest answer.
$$$\text{Proof:}$$$ If we are now inserting the $$$i$$$th element of the original array, it is obviously the best to choose the largest integer $$$a_i + i - c_i$$$, where $$$0 <= c_i <= i - 1$$$, that is not yet contained in $$$S$$$.
So what now remains to be proved is why the order of iteration from $$$1$$$ to $$$n$$$ gives the lexicographically largest answer.
Note that if we assume that during the process we don't face the scenario where when we want to delete element $$$i$$$, there's no available value in the range $$$[a_i + 1, a_i + i]$$$, then the resultant answer array is the same for all orders of deletions.
This is proved by consider all values of $$$a_i + i$$$, which is the best choice for each $$$i$$$ at the beginning. Of course, there might be duplicates, so we have to continue decreasing the values of those duplicated $$$a_i + i$$$ until no more duplicates are made. This actually fixes the final answer. For instance, if the values of $$$a_i + i$$$ gives one $$$2$$$ and three $$$5$$$'s, it apparently only corresponds to the answer $$$2, 3, 4, 5$$$, where one original $$$5$$$ is decreased by $$$1$$$, and the other repeated $$$5$$$ is decreased by $$$2$$$.
Moreover, when such a collision scenario occurs, the answer array that is decreased in length apparently doesn't grow lexicographically larger, because collisions are equivalent to removing some answers from the optimal answer array.
Thus, we now only have to show that our algorithm actually gives the longest possible answer sequence.
But this is obvious. Following the order from $$$1$$$ to $$$n$$$, when we arrive at $$$i$$$, there are $$$i$$$ possible choices in the range $$$[a_i + 1, a_i + i]$$$ for us to choose, but the given algorithm implies that at most $$$(i - 1)$$$ of these $$$i$$$ available values are taken by the time we get to $$$i$$$, so there is always a possible choice.
Thus, the correctness of the algorithm is proved. $$$\square$$$