Thank you for participation! I hope you liked atleast one problem from the set (:

We tried hard to have an interesting problemset.

It is sad to see people disliking the round only because some problems were hard. Please read the intended solutions to know why we decided to put the problems(especially D) at current positions.

Idea:satyam343

**Hint 1**

If sum is even, answer is $$$0$$$. Otherwise we need to change parity of atleast one element of $$$a$$$.

**Hint 2**

It it optimal to change parity of atmost one element.

**Hint 3**

Answer can be atmost $$$20$$$, as we need to divide any integer $$$x$$$ ($$$1 \leq x \leq 10^6$$$) atmost $$$20$$$ times to change its parity.

**Solution**

We are assuming initial sum is odd. Suppose $$$f(x)(1 \leq x \leq 10^6)$$$ gives the minimum number of operations needed to change parity of $$$x$$$.

Iterate from $$$i=1$$$ to $$$n$$$ and calculate $$$f(a_i)$$$ for each $$$i$$$.

Answer is minimum among all the calculated values.

Time complexity is $$$O(n \cdot log(A_{max}))$$$.

**Code**

```
#include <bits/stdc++.h>
using namespace std;
#define ll long long
void solve(){
ll n; cin>>n;
ll sum=0,ans=21;
vector<ll> a(n);
for(auto &it:a){
cin>>it;
sum+=it;
}
if(sum&1){
for(auto &it:a){
ll cur=it,now=0;
while(!((cur+it)&1)){
now++;
cur/=2;
}
ans=min(ans,now);
}
}
else{
ans=0;
}
cout<<ans<<"\n";
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll t; cin>>t;
while(t--){
solve();
}
}
```

Idea:satyam343

**Hint 1**

Suppose we have a prime number $$$p$$$. Suppose there are two perfect powers of $$$p$$$ — $$$l$$$ and $$$r$$$. Now it is easy to see $$$\max(l,r)$$$ is divisible by $$$\min(l,r)$$$.

**Hint 2**

So now we need to choose some prime number $$$p$$$. Let us start with the smallest prime number $$$p=2$$$.

**Hint 3**

Here is one interesting fact. There always exists a power of $$$2$$$ in the range $$$[x,2x]$$$ for any positive integer $$$x$$$.

**Solution**

Suppose $$$f(x)$$$ gives the smallest power of $$$2$$$ which is greater than $$$x$$$.

Iterate from $$$i=1$$$ to $$$n$$$ and change $$$a_i$$$ to $$$f(a_i)$$$ by adding $$$f(a_i)-a_i$$$ to $$$i$$$-th element.

Time complexity is $$$O(n \cdot log(A_{max}))$$$.

**Code**

```
#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll f(ll x){
ll cur=1;
while(cur<=x){
cur*=2;
}
return cur;
}
void solve(){
ll n; cin>>n;
cout<<n<<"\n";
for(ll i=1;i<=n;i++){
ll x; cin>>x;
cout<<i<<" "<<f(x)-x<<"\n";
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll t; cin>>t;
while(t--){
solve();
}
}
```

1762C - Binary Strings are Fun

Idea:satyam343

**Hint 1**

Let us first find $$$f(s[1,n])$$$.

**Hint 2**

$$$f(s[1,n])=2^{len-1}$$$ where $$$len$$$ is the length of longest suffix of $$$s$$$ in which all characters are same.

**Hint 3**

How to prove the result in hint $$$2$$$?

First of all it is easy to see if all characters of $$$s$$$ are same, $$$f(s[1,n])=2^{n-1}$$$ as median is always $$$s_i$$$.

Now we assume that $$$s$$$ contains distinct characters.

Suppose $$$t$$$ is one good extension of $$$s$$$. Assume we are index $$$i$$$. If there exists an index $$$j(j>i)$$$ such that $$$s_i \neq s_j$$$, we should have $$$t_{2i} \neq s_i$$$.

Why? Assume $$$k$$$ is the smallest index greater than $$$i$$$ such that $$$s_i \neq s_k$$$. Now if we have $$$t_{2i} = s_i$$$, $$$s_k$$$ can never be median of subarray $$$t[1,2k-1]$$$. So if longest suffix of $$$s$$$ having same characters of starts at index $$$i$$$, $$$t_{2j} \neq s_j$$$ for all $$$j(1 \leq j < i)$$$ and $$$t_{2j}$$$ can be anything(either $$$0$$$ or $$$1$$$) for all $$$j(i \leq j < n)$$$.

**Solution**

Now we know how to solve for whole string $$$s$$$.

We can similarly solve for all prefixes.

To find $$$f(s[1,i])$$$, we need to find the longest suffix of $$$s[1,i]$$$ containing same character.

We can easily calculate this all prefixes while moving from $$$i=1$$$ to $$$n$$$.

Time complexity is $$$O(n)$$$.

**Code**

```
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll MOD=998244353;
void solve(){
ll n; cin>>n;
string s; cin>>s; s=" "+s;
ll ans=0,cur=1;
for(ll i=1;i<=n;i++){
if(s[i]==s[i-1]){
cur=(2*cur)%MOD;
}
else{
cur=1;
}
ans=(ans+cur)%MOD;
}
cout<<ans<<"\n";
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll t; cin>>t;
while(t--){
solve();
}
}
```

Idea:amurto Prepared by:errorgorn

**Hint 1**

Intended solution uses $$$2 \cdot (n-2)$$$. You are allowed to guess two indices. Doesn't this hint towards something?

**Hint 2**

If we can eliminate $$$n-2$$$ elements that cannot be $$$0$$$ for sure, we are done.

**Hint 3**

Suppose we have three distinct indices $$$i$$$, $$$j$$$ and $$$k$$$. Is it possible to remove one index(say $$$x$$$) out of these three indices such that $$$p_x \neq 0$$$ for sure. You are allowed to query two times.

**Solution**

So suppose we have three distinct indices $$$i$$$, $$$j$$$ and $$$k$$$.

Let us assume $$$l=query(i,k)$$$ and $$$r=query(j,k)$$$

Now we have only three possibilities.

- $$$l=r$$$ In this case, $$$p_k$$$ cannot be $$$0$$$. Why? $$$p_i$$$ and $$$p_j$$$ are distinct, and we have $$$\gcd(0,x) \neq \gcd(0,y)$$$ if $$$x \neq y$$$

- $$$l > r$$$ In this case, $$$p_j$$$ cannot be $$$0$$$. Why? Note $$$\gcd(0,p_k)=p_k$$$ and $$$\gcd(m,p_k)$$$ can be atmost $$$p_k$$$ for any non negative integer. If $$$l > r$$$, this means $$$r$$$ cannot be $$$p_k$$$. Thus $$$p_r \neq 0$$$ for sure

- $$$l < r$$$ In this case, $$$p_i$$$ cannot be $$$0$$$. Why? Refer to the above argument.

This we can eliminate one index on using $$$2$$$ queries. We will perform this operation $$$n-2$$$ times. Refer to attached code for details.

Time complexity is $$$O(n)$$$.

**Code**

```
#include <bits/stdc++.h>
using namespace std;
#define ll long long
void solve(){
ll n; cin>>n;
ll l=1,r=2;
for(ll i=3;i<=n;i++){
ll ql,qr;
cout<<"? "<<l<<" "<<i<<endl;
cin>>ql;
cout<<"? "<<r<<" "<<i<<endl;
cin>>qr;
if(ql>qr){
r=i;
}
else if(ql<qr){
l=i;
}
}
cout<<"! "<<l<<" "<<r<<endl;
ll check; cin>>check;
assert(check==1);
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll t; cin>>t;
while(t--){
solve();
}
}
```

Idea:satyam343 Improved by:TheScrasse

**Hint 1**

There does not exist any good tree of size $$$n$$$ if $$$n$$$ is odd.

How to prove it? Suppose $$$f(v)$$$ gives the product of weight of edges incident to node $$$v$$$ in a good tree. We know that $$$f(i)=-1$$$ as if tree is good. Now $$$\prod_{i=1}^{n} f(i) = -1$$$ if $$$n$$$ is odd.

There is another way to find $$$\prod_{i=1}^{n} f(i)$$$. Look at contribution of each edge. Each edge contribitues $$$1$$$ to $$$\prod_{i=1}^{n} f(i)$$$, no matter what the weight of this edge is, as it gets multiplied twice. Thus we get $$$\prod_{i=1}^{n} f(i) = 1$$$. We got contradiction. Thus no good tree of size $$$n$$$ exists.

**Hint 2**

Now assume $$$n$$$ is even.

Here is an interesting claim.

For any unweighted tree,there exists exactly **one** assignment of weight of edges which makes it good.

Thus there are $$$n^{n-2}$$$ distinct edge-weighted trees.

**Hint 3**

How to prove the claim in hint $$$2$$$?

Arbitrarily root the tree at node $$$1$$$.

Now start from leaves and move towards root and assign the weight of edges in the path.

First of all the edge incident to any leaf node will have $$$-1$$$ as the weight. While moving towards root, it can be observed that weight of edge between $$$u$$$ and parent of $$$u$$$ depends on the product of weight of edges between $$$u$$$ and its children.

As we are moving from leaves towards root, weight of edges between $$$u$$$ and its children are already fixed. Weight of edge between $$$u$$$ and parent $$$u$$$ is $$$-1 \cdot \prod_{x \in C(u)}{pw(x)}$$$, where $$$pw(x)$$$ gives the weight of edge between $$$x$$$ and its parent, and $$$C(u)$$$ denotes the set of children of $$$u$$$.

**Solution**

Time for one more interesting claim. The weight of edge $$$e$$$ is $$$(-1)^{l}$$$ if there are $$$l$$$ nodes on one side and $$$n-l$$$ nodes on other side of $$$e$$$, irrespective of the structure of tree.

We can prove this claim by induction, similar to what we did in hint $$$3$$$.

To find answer we will look at contribution of each edge.

Here's detailed explanation on how to dot it.

In total, we have $$$n^{n-2} \cdot (n-1)$$$ edges.

Suppose for some edge(say $$$e$$$), we have $$$l$$$ nodes(including node $$$1$$$) on left side and $$$r$$$ nodes(including node $$$n$$$) on right side.

Among $$$n^{n-2} \cdot (n-1)$$$ edges, how many possibilities do we have for $$$e$$$?

It is $$${{n-2} \choose {l-1}} \cdot l \cdot r \cdot l^{l-2} \cdot r^{r-2}$$$. Why? First we select $$$l-1$$$ nodes(as node $$$1$$$ is fixed to be on left side) to be on left side, we get $$${{n-2} \choose {l-1}}$$$ for this.

Now we have $$$l$$$ nodes on left side and $$$r$$$ nodes on right side. Edge $$$e$$$ will connect one among $$$l$$$ nodes on left and one among $$$r$$$ nodes on right. So edge $$$e$$$ will exist between $$$l \cdot r$$$ pairs. We know that number of distinct trees having $$$x$$$ nodes is $$$x^{x-2}$$$.

Now on selecting one node from left and one from right, we have fixed the root of subtree on left side, and have also fixed the root of subtree on right side. So, number of distinct subtrees on left side is $$$l^{l-2}$$$, and number of distinct subtrees on right side is $$$r^{r-2}$$$.

Thus, on mutliplying all(since they are independent), we get $$${n \choose l} \cdot l \cdot r \cdot l^{l-2} \cdot r^{r-2}$$$ possibilities for $$$e$$$.

Now this edge lies on the path from $$$1$$$ to $$$n$$$ as both lie on opposite sides of this node.

So this edge contributes $$$(-1)^l \cdot {{n-2} \choose {l-1}} \cdot l \cdot r \cdot l^{l-2} \cdot r^{r-2}$$$ to answer.

Hence $$$d(1,n)=\sum_{l=1}^{n-1} (-1)^l \cdot {{n-2} \choose {l-1}} \cdot l \cdot r \cdot l^{l-2} \cdot r^{r-2}$$$ where $$$l+r=n$$$. Note that we assumed that we are always going from left subtree to right subtree while calculating contribution. As we have tried all possibilties for l, all cases get covered. We used left and right subtrees just for our own convention.

Time complexity is $$$O(n \cdot \log(n))$$$.

**Code**

```
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll MOD=998244353;
const ll MAX=500500;
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<0)||(a<b)||(b<0))
return 0;
ll denom=(inv_fact[b]*inv_fact[a-b])%MOD;
return (denom*fact[a])%MOD;
}
void solve(){
ll n,ans=0; cin>>n;
if(n&1){
cout<<0;
return;
}
ll sgn=1;
for(ll i=1;i<n;i++){
sgn*=-1;
ll r=n-i,l=i;
ll fix_l=nCr(n-2,l-1,MOD); //fixing l nodes on left side
ll fix_root=(l*r)%MOD; //fixing roots of subtrees on both sides
ll trees=(binpow(l,l-2,MOD)*binpow(r,r-2,MOD))%MOD; //counting no of subtrees
ll no_of_e=(((fix_l*fix_root)%MOD)*trees)%MOD; //no of possibilities for e
ans=(ans+sgn*no_of_e)%MOD;
}
ans=(ans+MOD)%MOD;
cout<<ans;
return;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
precompute(MOD);
ll t=1;
//cin>>t;
while(t--){
solve();
}
}
```

Idea:satyam343

**Hint 1**

We should have $$$|a_{i_j}-a_{i_{j+1}}| \leq k$$$. This seems a bit hard, as we can have $$$a_{i_{j+1}}$$$ greater than, smaller than or equal to $$$a_{i_j}$$$.

Why not solve the easier version first?

A pair $$$(l,r)$$$ is *good* if there exists a sequence of indices $$$i_1, i_2, \dots, i_m$$$ such that

- $$$i_1=l$$$ and $$$i_m=r$$$;
- $$$i_j < i_{j+1}$$$ for all $$$1 \leq j < m$$$; and
- $$$0 < a_{i_j}-a_{i_{j+1}} \leq k$$$ for all $$$1 \leq j < m$$$.

Suppose $$$F(a,k)$$$ number of pairs $$$(l,r)$$$ ($$$1 \leq l < r \leq n$$$) that are good.

Find $$$F(a,k)$$$.

**Hint 2**

To solve the problem in hint $$$1$$$, let us define $$$dp_i$$$ as the number of pairs $$$j(i<j)$$$ such that $$$(i,j)$$$ is good.

Let us move from $$$i=n$$$ to $$$1$$$. To find $$$dp_i$$$, let us first find the smallest index $$$j$$$ such that $$$a_j$$$ lies in range $$$[a_i+1,a_i+k]$$$.

We can observe that $$$dp_i=dp_j+f(i,a_i+1,a_j)$$$, where $$$f(i,l,r)$$$ gives us the number of indices $$$x$$$ among last $$$i$$$ elements of $$$a$$$ such that $$$a_x$$$ lies in the range $$$[l,r]$$$. We can use fenwik tree or ordered set to find $$$f(i,l,r)$$$.

**Hint 3**

Now let us get back to original problem.

First let us count number of pairs $$$(i,j)(1 \leq i \leq j)$$$ such that $$$a_i=a_j$$$. Assume $$$cnt$$$ is number of such pairs.

Time for another cool claim!

For our original problem, answer is $$$cnt+F(a,k)+F(rev(a),k)$$$, where $$$rev(a)$$$ denotes the array $$$a$$$ when it is reversed.

**Solution**

How to prove the claim in hint $$$3$$$?

Suppose we have a good pair $$$(l,r)$$$ such that $$$a_l \neq a_r$$$. Now using exchange arguments we can claim that there always exists a sequence(say $$$s$$$) starting at index $$$l$$$ and ending at index $$$r$$$

- such that difference between adjacent elements of $$$a$$$ is atmost $$$k$$$
- strictly increasing if $$$a_l < a_r$$$
- strictly decreasing if $$$a_l > a_r$$$

Thus $$$(l,r)$$$ will be counted in $$$F(a,k)$$$ if $$$a_l < a_r$$$ and $$$(l,r)$$$ will be counted in $$$F(rev(a),k)$$$ if $$$a_l > a_r$$$.

Time complexity is $$$O(n \cdot \log(n))$$$.

**Code**

```
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll MAX=1000100;
class ST{
public:
vector<ll> segs;
ll size=0;
ll ID=MAX;
ST(ll sz) {
segs.assign(2*sz,ID);
size=sz;
}
ll comb(ll a,ll b) {
return min(a,b);
}
void upd(ll idx, ll val) {
segs[idx+=size]=val;
for(idx/=2;idx;idx/=2){
segs[idx]=comb(segs[2*idx],segs[2*idx+1]);
}
}
ll query(ll l,ll r) {
ll lans=ID,rans=ID;
for(l+=size,r+=size+1;l<r;l/=2,r/=2) {
if(l&1) {
lans=comb(lans,segs[l++]);
}
if(r&1){
rans=comb(segs[--r],rans);
}
}
return comb(lans,rans);
}
};
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];
return ret;
}
ll sum(ll l,ll r) {
if(l>r)
return 0;
return sum(r)-sum(l-1);
}
void add(ll idx,ll delta) {
for(;idx<n;idx=idx|(idx+1))
bit[idx]+=delta;
}
};
FenwickTree freq(MAX);
ST segtree(MAX);
vector<ll> dp(MAX,0);
ll solve(vector<ll> a,ll n,ll k){
ll now=0;
for(ll i=n-1;i>=0;i--){
ll j=segtree.query(a[i]+1,a[i]+k);
if(j<n){
dp[i]=dp[j]+freq.sum(a[i]+1,a[j]);
}
else{
dp[i]=0;
}
now+=dp[i];
segtree.upd(a[i],i);
freq.add(a[i],1);
}
for(auto it:a){
segtree.upd(it,MAX);
freq.add(it,-1);
}
return now;
}
void solve(){
ll n,k; cin>>n>>k;
vector<ll> a(n);
ll ans=0;
map<ll,ll> cnt;
for(auto &it:a){
cin>>it;
cnt[it]++;
ans+=cnt[it];
}
ans+=solve(a,n,k);
reverse(a.begin(),a.end());
ans+=solve(a,n,k);
cout<<ans<<"\n";
return;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll t=1;
cin>>t;
while(t--){
solve();
}
}
```

1762G - Unequal Adjacent Elements

Idea:satyam343

**Hint 1**

Answer is NO only when there exists an element of $$$a$$$ which occurs more that $$$\lceil \frac{n}{2} \rceil$$$ times.

**Hint 2**

Let us say an array $$$b$$$ is beautiful if length of $$$b$$$ is odd and mode(say $$$x$$$) of $$$b$$$ occurs exactly $$$\lceil \frac{n}{2} \rceil$$$ times.

If $$$a$$$ is beautiful, there exists only one permutation.

We have rearrange such that $$$x$$$ occupies all the odd indices and keep the elements at even indices such that condition $$$2$$$ in satisfied.

**Hint 3**

To solve the original problem, we will divide the array $$$a$$$ into multiple beautiful subarrays and arrange the elements in those subarrays.

**Solution**

Let us continue from where we left off.

So our motivation is to break the original array into multiple beautiful subarrays and the elements in those subarrays, as mentioned before. Now for condition $$$1$$$ to be satisfied, we should not have two adjacent subarrays such that the elements at the end positions of both subarrays(after rearranging the elements) are the same.

Here is one construction using which we can achieve our goal.

Suppose $$$l$$$ denotes the leftmost point of our concerned subarray.

If $$$a_l \neq a_{l+1}$$$, we move forward, as subarray $$$a[l,l]$$$ is good.

Otherwise, we keep moving towards the right till index $$$r$$$(here, $$$r$$$ should be the smallest possible) such that the subarray $$$a[l,r]$$$ is beautiful and $$$a_l \neq a_{r+1}$$$. So it is easy to notice the following observations about the subarray $$$a[l,r]$$$

length of this subarray is odd

$$$a_l$$$ occurs exactly $$$\lceil \frac{r-l+1}{2} \rceil$$$ times in this subarray

Now we can rearrange the elements of this subarray $$$a[l,r]$$$.

Do note that the subarray $$$a[1,r]$$$ satisfies both the conditions stated in the statement.

So our task is to make the subarray $$$a[r+1,n]$$$ good now.

We can now update $$$l=r+1$$$ and continue searching for the corresponding $$$r$$$ and so on.

Now it might be the case that we did not get a valid $$$r$$$ for the last search.

From here, I assume we did not get valid $$$r$$$ for the last search. We could print the obtained permutation if we got it, as $$$a$$$ would satisfy both conditions.

Assume that we had started at $$$pos=l$$$ and couldn't find $$$r$$$.

Subarray $$$a[1,pos-1]$$$ is already good.

To fix this issue, we will do a similar search that we did before.

We start from the back(from index $$$n$$$) and move towards left till index $$$m$$$ such that

- $$$m < pos$$$
- $$$a[m,n]$$$ is beautiful
- $$$a_{pos}$$$ occurs exactly $$$\lceil \frac{n-m+1}{2} \rceil$$$ times in this subarray
- $$$a_{pos} \neq a_{m-1}$$$

Now we arrange elements of this subarray in the same fashion that we did before.

Are we done?

No. First, we must prove that we will always get some $$$m$$$.

Let us have function $$$f(a,l,r,x)$$$, which denotes the score of the subarray $$$a[l,r]$$$ for the element $$$x$$$. $$$f(a,l,r,x)=freq_x-(r-l+1-freq_x)$$$, where $$$freq_x$$$ denotes the frequency of element $$$x$$$ in the subarray $$$a[l,r]$$$

It is easy to note that $$$f(a,pos,n,a_{pos}) > 1$$$

(Hint $$$ — $$$ Prove that $$$f(a,pos,r,a_{pos}) \neq 0$$$ for $$$pos \leq r \leq n$$$. Why?(If it does then $$$a[pos,r-1]$$$ would be beautiful ))

Now we start from the back and move towards the right to find $$$m$$$ with $$$n$$$ as our right endpoint of the concerned subarray.

Note that $$$f(a,1,n,a_{pos}) \leq 1$$$ (Why? $$$a_{pos}$$$ would have occurred at most $$$\lceil \frac{n}{2} \rceil$$$ times in $$$a$$$)

So while moving from $$$pos$$$ to $$$1$$$ we will indeed find a $$$m$$$ such that $$$f(a,m,n,a_{pos})=1$$$, and $$$a_{m-1} \neq a_{pos}$$$ (assuming $$$a_0=-1$$$)

Are we done?

Not still :p. We can observe that condition $$$1$$$ is satisfied, but sometimes condition $$$2$$$ would not be. For example, simulate the above approach on the array $$$a=[1,1,2,3,3]$$$.

How to fix this issue? It's pretty easy to fix this issue.

**Hint**

Instead of rearranging the subarray $$$a[m,n]$$$, we will rearrange the subarray $$$a[m-1,n]$$$.

How to rearrange?

Okay, time for one more hint.

What will be the answer for $$$a=[1,1,2,3,3]$$$?

**Answer**

$$$p=[1,4,2,5,3]$$$

You can refer to the attached code for implementation details.

**Code**

```
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define all(x) x.begin(),x.end()
void solve(){
ll n; cin>>n;
vector<ll> a(n+5),freq(n+5,0);
for(ll i=1;i<=n;i++){
cin>>a[i]; freq[a[i]]++;
}
for(ll i=1;i<=n;i++){
ll till=(n+1)/2;
if(freq[i]>till){
cout<<"NO\n";
return;
}
}
cout<<"YES\n";
vector<ll> ans;
ll cur=1;
while(cur<=n){
ll val=a[cur];
vector<ll> v1,v2;
while(cur<=n){
if(a[cur]==val){
v1.push_back(cur);
}
else{
v2.push_back(cur);
}
if(v1.size()==v2.size()){
for(ll i=0;i<v1.size();i++){
ans.push_back(v1[i]); ans.push_back(v2[i]);
}
ans.pop_back();
break;
}
if(cur==n){
while(1){
if(ans.empty()||v1.size()==v2.size()){
sort(all(v1)); sort(all(v2));
if(v1.size()!=v2.size()){
ans.push_back(v1[0]);
v1.erase(v1.begin());
}
if(!v2.empty()&&!ans.empty()){
if(a[ans.back()]==a[v2[0]]){
swap(v1,v2);
}
}
for(ll i=0;i<v1.size();i++){
ans.push_back(v2[i]); ans.push_back(v1[i]);
}
break;
}
if(a[ans.back()]==val){
v1.push_back(ans.back());
}
else{
v2.push_back(ans.back());
}
ans.pop_back();
}
cur=n+1;
}
cur++;
}
}
for(auto it:ans){
cout<<it<<" ";
}
cout<<"\n";
return;
}
int main()
{
ll test_cases=1;
cin>>test_cases;
while(test_cases--){
solve();
}
}
```

Great Round!! Indeed, problems were quite hard but doable, but overall a v.good experience!

So I solved the problem D a little differently, I tried to make use of the fact that we can always take multible of some number x > 1 and dump all the other elements in the array and zero will always be multiple,

this give n + n / 2 + n / 4 — = 2n queries in total. There is a lot of case handling but You can look at my code to understand it a little better for e.g. if x == 2, than we can just dump all elements except 0 — 4 — 6 — 8 — 10

now the next smallest multiple we can take is 4 than we have 0 — 8 — 12 -16 If we take zero, than all the elements in gcd(pi, 0) will be different hence we can just use zero or pi that gives largest value

LINK FOR THE SOLUTION : https://mirror.codeforces.com/contest/1762/submission/185393565

The first step to find a not-1 position costs $$$\lfloor \frac{n}{2} \rfloor$$$ querys. The second step cost about $$$n(1 + \frac{1}{2} + \frac{1}{4} + \frac{1}{8} + \cdots)$$$ querys. Why the total cost can be limited to $$$2n$$$?

I think we can use a simple idea to deal with the first not-1 position, that is to eliminate not-0 positions as well. You can query (i,i+1), (i,i+2), (i+1,i+2). If they are all ones, you can be sure they are not 0, so remove them from the possible answers, otherwise, you found your first not-1 position. Lmk if I missed anth.

Yeah, as I have done that using vector p2,

for each i, if gcd(i, i — 1) and gcd(i, i + 1) is 1 than this number can not be 1, reason being,

x, 0, y, now if zero was in the middle, gcd(x. 0) = x and gcd(0, y) = y so max(x, y) > 1 because distinct elements in permutaion, there is this case where 0 was first or last element and you never find any element in middle just use that as edge case and print 1 n

Also the idea that half of numbers are even can be employed. One can query pairs (1, 2), (3, 4), ... until gcd is 1. If there's no such index encountered we can also query (1, 4) and (1, 3) to finally find the index of a number that is not 1 or that is even. Then we put it at first place and find all gcds of it and with all the other numbers, collect stat and leave only those indices that have the greatest gcd encountered. Repeat until we have two numbers left.

i did exact same apprroach but got WA on test 5 can u please help https://mirror.codeforces.com/contest/1762/submission/185370228

even my solution failed on exactly the same test case . if you are able to find the mistake please reply https://mirror.codeforces.com/contest/1762/submission/185422415

1 2 4 6 8 7 3 5 0 I used same approach and then i found on the above mentioned test case it takes 19 queries.

mine submissions takes 15 submission which is in range

I used a similar approach and stress-tested it on all permutations of size 10, it passed them all. Not sure what the problem is.

Here is my approach, I maintain a list of possible indexes which are initially all indexes. In each round, I query the gcd of the first element with all other elements. Now the maximum result I get must be the value of the first element and all of its multiples including 0 must give the same value. I repeat rounds till the number of possible elements becomes 1. If the number of elements giving maximum gcd is 1, then my first element must either be a co-prime to all elements with the maximum gcd element being 0, or the first element must be 0. So I answer with the first element and the element giving maximum gcd.

Submission link Stress test code

Edit- I found the error thanks to propane. I am exceeding query limit when the first element is 1

i had exactly same approach and for the exceeding query limit when the first element is 1 i used the fact that if for an index on the first 2 queries it got gcd 1 it cant be 0 so i terminated the process there and deleted this index and moved forward but still query limit exceeded came :(

I also came up with this solution! But sadly i couldn't participate in the contest

Problem A can use

`__builtin_ctz(x)`

for even numbers or`__builtin_ctz(x+1)`

for odd numbers. link: https://mirror.codeforces.com/contest/1762/submission/185402449can you explain it more?

`__builtin_ctz`

counts the number of trailing zeros of the number in binary form. To change parity is to change the least significant bit (LSB) from 0 to 1 or vice versa. For example, say we have 11100 (with 2 trailing zeros), two divisions/right-shift operations are needed to change the LSB. +1 for odd numbers to convert trailing ones to trailing zeroes.Damn clever!

I really enjoyed this round.

The implementation of the first four problems is quite easy. In this way the problems become purely observational.

Keep up with the good rounds!

Intended solution for D is genious.

My solution for problem C was a bit different from the editorial. Did that after processing each character I found the number of spaces or free positions where 0/1 may be put that is we have two options for that position. Now we can every time add the 2^spaces to the answer and take respective modulo as well.

(https://mirror.codeforces.com/contest/1762/submission/275475939) I followed the same logic,can you tell why does mine give wrong ans for TC3?

Can't believe I'm doing this , but alright — I have Idea for D: 1) First we ask n — 1 queries of format ? 1 i, 2 <= i <= n . We will remember all the answers we get

Maximum of all those gcds = a[1], right? Unless all the answers are distinct and are from 1..n-1 — in this case a[1] == 0, and then we can output ! 1 2

Okay, so we know the value of a[1] and we know all the positions j , that gcd(a[1], a[j])==x, for each x

2) Let's take all positions where gcd(a[j], a[1])==a[1] ( we could've remembered this from step 1). For example we have 2, 3, 7 9( it means that a[2] = a[1] * k1, a[3] = a[1] * k2, a[7] = a[1] * k3 ... k[i] is obviously from 0 to (n-1) / a[1]

Now we can just ask another set of questions: ? 2 3 | ? 2 7 | ? 2 9

If any of those gcd(a[2], a[j]) != a[1] then it means either a[2] or a[j] == 0.

As always with guys of green profiles , my code is having WA2 lmao, here it is. Tell me if you can spot a mistake

1 2 4 3 0 Try this case

Good one, thanks.

Fast editorial (wtf about #837)

Can anyone tell whats wrong with my Submission in D https://mirror.codeforces.com/contest/1762/submission/185370228 it would be great help

1 2 4 6 8 7 3 5 0 calculate number of queries for this case.

15 brother with is less than 2*(9) where 9 is the size of array

Actually, in my case, it took 19 queries. `` First I queried the first position with every other element, which took 8 queries. Then I updated the array to [2,4,6,8,7,3,5,0]. Then I queried the first element of the current array (which has value 2) with every other element. This took another 7 queries for me. So the total is 15 queries. I took the elements which gave maximum gcd. So updated array looks like [4,6,8,0]. Then following the same procedure I will query again another 3 times. So the total number of queries is 18. The resultant subarray is [8,0]. So I queried last time before giving an answer which totals up to 19. Maybe you can relate to your code. The idea is just to avoid position 1 when querying with other elements.

ya i avoided the first position actually and moreover I got a wa actually but I checked for many a times but not able to found wa test case

Take a look at Ticket 16571 from

CF Stressfor a counter example.thanks a lot got it

Very beautiful problem F! I stand up and applause!

Thanks!

I am glad that you liked it (:

I solved F with a different approach.

I made a directed graph such that there is an edge from $$$i$$$ and $$$j$$$ if $$$A_i \geq A_j$$$ and all $$$A_k$$$ between $$$A_i$$$ and $$$A_j$$$ are less greater than $$$A_i$$$. Similarly, I add an edge between $$$A_i$$$ and $$$A_i$$$ such that $$$A_i \leq A_j$$$ and all $$$A_k$$$ between $$$A_i$$$ and $$$A_j$$$ are greater than $$$A_i$$$. So, there are atmost $$$2$$$ outgoing edges from each $$$i$$$.

Now, $$$DP_i$$$ = $$$DP_j$$$ + $$$DP_k$$$ — $$$DP_l$$$ where there is a directed edge from $$$i$$$ to $$$j$$$ and $$$i$$$ to $$$k$$$. But to avoid double calculations, we need to subtract $$$DP_l$$$ where $$$l$$$ is the smallest position that can be reached by both $$$i$$$ and $$$j$$$ using some directed edges.

Now, to find this position $$$l$$$, we use binary lifting technique with binary search. Since $$$l$$$ is the smallest position, you have $$$2$$$ nodes $$$u$$$ and $$$v$$$ such that $$$A_u \leq A_v$$$ and $$$A_u \leq A_l \leq A_v$$$. Hence it is always optimal for $$$A_u$$$ to take the edge such that $$$A_{p_u} \geq A_u$$$ and for $$$A_v$$$ to take $$$A_{p_v} \leq A_v$$$.

Now, we can binary search and find the largest node which is less than or equal to mid and check if - they are same - $$$A_u > A_v$$$ - $$$A_u < A_v$$$ This maximum node can be found by binary lifting technique.

Time complexity — $$$O(N log^2N)$$$ and works fine within $$$3$$$ seconds.

My code

What will be the expected rating of the 2nd question?

i think it would be around 1000

Nice editorial , hints are available for every problem.

Can someone explain C? Why suffix though?

Example:

s = 1_0_1_0_0_0f(s) = 8

how?

try to find what binary digits can occupy empty places.

1st empty space : 0

2nd empty space : 1

3rd empty space : 0/1

4th empty space : 0/1

5th empty space : 0/1

So the

longest suffix with the same digits in the original stringonly accounts for the number of ways to fill the binary digits in empty places.Also, try to work out for this case:

s = 1_0_1_0_0_0_1You will observe that, because of the

last onein thestring, all the2 possibilities (0 / 1)in previous empty places change to1.Wow! Good Explanation. Thanks man

but why longest suffix and not any other idea

try working out the examples , you will get an idea

I am not getting Problem C solution can someone explain it.

Satyam_343 is legend!

Certainly, least we can do is : satyam343 orz.

Not not not $$$\ldots \ldots$$$ untrue

I made the above meme

Not not not $$$\ldots \ldots$$$ untrue

for C, a little optimization: say that current suffix has length l. then in the summation we will be summing 2^(k-1) from k=1 to l, but this is just 2^(l)-1. thus we only need to sum (2^length)-1 over all consecutive strings of 1s and all consecutive strings of 0s. example: 101101111 1 — length 1; 0 — length 1; 11 — length 2; 0 — length 1; 1111 — length 4; summing 2^(length)-1 gives 1+1+3+1+15=21, as desired.

## Explanation for the observation about suffixes for C

hasto be odd. (because, again,odd-length-prefixand a binary string).andthe last character of the next odd-length prefix is the same as this "good" one, then there are $$$two$$$ options to fill that intervening position between them. (There's a single intervening position between two consecutive odd-lengthed-prefixes.)Most imp: one way of filling this intervening position will end up increasing the frequency-difference by 2 and the other way will not alter the frequency-difference at all.The "single-intervening-element" between the current and next odd-lengthed prefix will not be able to salvage the situation and cover-up a gap of $$$3/5/7..\dots$$$. It can only cover frequency gap of $$$1$$$.

Finally: This means you can use both two options of filling the intervening position only when you can trust that you don't have anyupcomingodd-lengthed prefix that ends at an unlike character. In all other cases, there is actually only one way of filling up the intervening position.Only when, you know that the entire suffix of $$$s$$$ from this point on contains "like" characters, can you start using the other "second" way of filling up the intervening position.

can u explain why they are setting curr to 1, if the characters are not equal?

GOOOOD round!

cool