1762.md (24030B)
1 Source: https://codeforces.com/blog/entry/110169 2 3 Thank you for participation! I hope you liked atleast one problem from the set (: 4 5 We tried hard to have an interesting problemset. 6 7 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. 8 9 [1762A - Divide and Conquer](/contest/1762/problem/A "Codeforces Round 838 (Div. 2)") 10 11 Idea:[satyam343](/profile/satyam343 "Master satyam343") 12 13 **Hint 1** 14 15 If sum is even, answer is $0$. Otherwise we need to change parity of atleast one element of $a$. 16 17 **Hint 2** 18 19 It it optimal to change parity of atmost one element. 20 21 **Hint 3** 22 23 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. 24 25 **Solution** 26 27 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$. 28 29 Iterate from $i=1$ to $n$ and calculate $f(a_i)$ for each $i$. 30 31 Answer is minimum among all the calculated values. 32 33 Time complexity is $O(n \cdot log(A_{max}))$. 34 35 **Code** 36 37 ``` 38 #include <bits/stdc++.h> 39 using namespace std; 40 #define ll long long 41 void solve(){ 42 ll n; cin>>n; 43 ll sum=0,ans=21; 44 vector<ll> a(n); 45 for(auto &it:a){ 46 cin>>it; 47 sum+=it; 48 } 49 if(sum&1){ 50 for(auto &it:a){ 51 ll cur=it,now=0; 52 while(!((cur+it)&1)){ 53 now++; 54 cur/=2; 55 } 56 ans=min(ans,now); 57 } 58 } 59 else{ 60 ans=0; 61 } 62 cout<<ans<<"\n"; 63 } 64 int main() 65 { 66 ios_base::sync_with_stdio(false); 67 cin.tie(NULL); 68 ll t; cin>>t; 69 while(t--){ 70 solve(); 71 } 72 } 73 ``` 74 75 [1762B - Make Array Good](/contest/1762/problem/B "Codeforces Round 838 (Div. 2)") 76 77 Idea:[satyam343](/profile/satyam343 "Master satyam343") 78 79 **Hint 1** 80 81 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)$. 82 83 **Hint 2** 84 85 So now we need to choose some prime number $p$. Let us start with the smallest prime number $p=2$. 86 87 **Hint 3** 88 89 Here is one interesting fact. There always exists a power of $2$ in the range $[x,2x]$ for any positive integer $x$. 90 91 **Solution** 92 93 Suppose $f(x)$ gives the smallest power of $2$ which is greater than $x$. 94 95 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. 96 97 Time complexity is $O(n \cdot log(A_{max}))$. 98 99 **Code** 100 101 ``` 102 #include <bits/stdc++.h> 103 using namespace std; 104 #define ll long long 105 ll f(ll x){ 106 ll cur=1; 107 while(cur<=x){ 108 cur*=2; 109 } 110 return cur; 111 } 112 void solve(){ 113 ll n; cin>>n; 114 cout<<n<<"\n"; 115 for(ll i=1;i<=n;i++){ 116 ll x; cin>>x; 117 cout<<i<<" "<<f(x)-x<<"\n"; 118 } 119 } 120 int main() 121 { 122 ios_base::sync_with_stdio(false); 123 cin.tie(NULL); 124 ll t; cin>>t; 125 while(t--){ 126 solve(); 127 } 128 } 129 ``` 130 131 [1762C - Binary Strings are Fun](/contest/1762/problem/C "Codeforces Round 838 (Div. 2)") 132 133 Idea:[satyam343](/profile/satyam343 "Master satyam343") 134 135 **Hint 1** 136 137 Let us first find $f(s[1,n])$. 138 139 **Hint 2** 140 141 $f(s[1,n])=2^{len-1}$ where $len$ is the length of longest suffix of $s$ in which all characters are same. 142 143 **Hint 3** 144 145 How to prove the result in hint $2$? 146 147 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$. 148 149 Now we assume that $s$ contains distinct characters. 150 151 Suppose $t$ is one good extension of $s$. Assume we are index $i$. If there exists an index $j(j \gt i)$ such that $s_i \neq s_j$, we should have $t_{2i} \neq s_i$. 152 153 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 \lt i)$ and $t_{2j}$ can be anything(either $0$ or $1$) for all $j(i \leq j \lt n)$. 154 155 **Solution** 156 157 Now we know how to solve for whole string $s$. 158 159 We can similarly solve for all prefixes. 160 161 To find $f(s[1,i])$, we need to find the longest suffix of $s[1,i]$ containing same character. 162 163 We can easily calculate this all prefixes while moving from $i=1$ to $n$. 164 165 Time complexity is $O(n)$. 166 167 **Code** 168 169 ``` 170 #include <bits/stdc++.h> 171 using namespace std; 172 #define ll long long 173 const ll MOD=998244353; 174 void solve(){ 175 ll n; cin>>n; 176 string s; cin>>s; s=" "+s; 177 ll ans=0,cur=1; 178 for(ll i=1;i<=n;i++){ 179 if(s[i]==s[i-1]){ 180 cur=(2*cur)%MOD; 181 } 182 else{ 183 cur=1; 184 } 185 ans=(ans+cur)%MOD; 186 } 187 cout<<ans<<"\n"; 188 } 189 int main() 190 { 191 ios_base::sync_with_stdio(false); 192 cin.tie(NULL); 193 ll t; cin>>t; 194 while(t--){ 195 solve(); 196 } 197 } 198 ``` 199 200 [1762D - GCD Queries](/contest/1762/problem/D "Codeforces Round 838 (Div. 2)") 201 202 Idea:[amurto](/profile/amurto "Master amurto") Prepared by:[errorgorn](/profile/errorgorn "International Grandmaster errorgorn") 203 204 **Hint 1** 205 206 Intended solution uses $2 \cdot (n-2)$. You are allowed to guess two indices. Doesn't this hint towards something? 207 208 **Hint 2** 209 210 If we can eliminate $n-2$ elements that cannot be $0$ for sure, we are done. 211 212 **Hint 3** 213 214 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. 215 216 **Solution** 217 218 So suppose we have three distinct indices $i$, $j$ and $k$. 219 220 Let us assume $l=query(i,k)$ and $r=query(j,k)$ 221 222 Now we have only three possibilities. 223 224 * $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$ 225 226 * $l \gt 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 \gt r$, this means $r$ cannot be $p_k$. Thus $p_r \neq 0$ for sure 227 228 * $l \lt r$ In this case, $p_i$ cannot be $0$. Why? Refer to the above argument. 229 230 This we can eliminate one index on using $2$ queries. We will perform this operation $n-2$ times. Refer to attached code for details. 231 232 Time complexity is $O(n)$. 233 234 **Code** 235 236 ``` 237 #include <bits/stdc++.h> 238 using namespace std; 239 #define ll long long 240 void solve(){ 241 ll n; cin>>n; 242 ll l=1,r=2; 243 for(ll i=3;i<=n;i++){ 244 ll ql,qr; 245 cout<<"? "<<l<<" "<<i<<endl; 246 cin>>ql; 247 cout<<"? "<<r<<" "<<i<<endl; 248 cin>>qr; 249 if(ql>qr){ 250 r=i; 251 } 252 else if(ql<qr){ 253 l=i; 254 } 255 } 256 cout<<"! "<<l<<" "<<r<<endl; 257 ll check; cin>>check; 258 assert(check==1); 259 } 260 int main() 261 { 262 ios_base::sync_with_stdio(false); 263 cin.tie(NULL); 264 ll t; cin>>t; 265 while(t--){ 266 solve(); 267 } 268 } 269 ``` 270 271 [1762E - Tree Sum](/contest/1762/problem/E "Codeforces Round 838 (Div. 2)") 272 273 Idea:[satyam343](/profile/satyam343 "Master satyam343") Improved by:[TheScrasse](/profile/TheScrasse "Grandmaster TheScrasse") 274 275 **Hint 1** 276 277 There does not exist any good tree of size $n$ if $n$ is odd. 278 279 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. 280 281 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. 282 283 **Hint 2** 284 285 Now assume $n$ is even. 286 287 Here is an interesting claim. 288 289 For any unweighted tree,there exists exactly **one** assignment of weight of edges which makes it good. 290 291 Thus there are $n^{n-2}$ distinct edge-weighted trees. 292 293 **Hint 3** 294 295 How to prove the claim in hint $2$? 296 297 Arbitrarily root the tree at node $1$. 298 299 Now start from leaves and move towards root and assign the weight of edges in the path. 300 301 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. 302 303 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$. 304 305 **Solution** 306 307 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. 308 309 We can prove this claim by induction, similar to what we did in hint $3$. 310 311 To find answer we will look at contribution of each edge. 312 313 Here's detailed explanation on how to dot it. 314 315 In total, we have $n^{n-2} \cdot (n-1)$ edges. 316 317 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. 318 319 Among $n^{n-2} \cdot (n-1)$ edges, how many possibilities do we have for $e$? 320 321 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. 322 323 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}$. 324 325 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}$. 326 327 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$. 328 329 Now this edge lies on the path from $1$ to $n$ as both lie on opposite sides of this node. 330 331 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. 332 333 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. 334 335 Time complexity is $O(n \cdot \log(n))$. 336 337 **Code** 338 339 ``` 340 #include <bits/stdc++.h> 341 using namespace std; 342 #define ll long long 343 const ll MOD=998244353; 344 const ll MAX=500500; 345 vector<ll> fact(MAX+2,1),inv_fact(MAX+2,1); 346 ll binpow(ll a,ll b,ll MOD){ 347 ll ans=1; 348 a%=MOD; 349 while(b){ 350 if(b&1) 351 ans=(ans*a)%MOD; 352 b/=2; 353 a=(a*a)%MOD; 354 } 355 return ans; 356 } 357 ll inverse(ll a,ll MOD){ 358 return binpow(a,MOD-2,MOD); 359 } 360 void precompute(ll MOD){ 361 for(ll i=2;i<MAX;i++){ 362 fact[i]=(fact[i-1]*i)%MOD; 363 } 364 inv_fact[MAX-1]=inverse(fact[MAX-1],MOD); 365 for(ll i=MAX-2;i>=0;i--){ 366 inv_fact[i]=(inv_fact[i+1]*(i+1))%MOD; 367 } 368 } 369 ll nCr(ll a,ll b,ll MOD){ 370 if((a<0)||(a<b)||(b<0)) 371 return 0; 372 ll denom=(inv_fact[b]*inv_fact[a-b])%MOD; 373 return (denom*fact[a])%MOD; 374 } 375 void solve(){ 376 ll n,ans=0; cin>>n; 377 if(n&1){ 378 cout<<0; 379 return; 380 } 381 ll sgn=1; 382 for(ll i=1;i<n;i++){ 383 sgn*=-1; 384 ll r=n-i,l=i; 385 ll fix_l=nCr(n-2,l-1,MOD); //fixing l nodes on left side 386 ll fix_root=(l*r)%MOD; //fixing roots of subtrees on both sides 387 ll trees=(binpow(l,l-2,MOD)*binpow(r,r-2,MOD))%MOD; //counting no of subtrees 388 ll no_of_e=(((fix_l*fix_root)%MOD)*trees)%MOD; //no of possibilities for e 389 ans=(ans+sgn*no_of_e)%MOD; 390 } 391 ans=(ans+MOD)%MOD; 392 cout<<ans; 393 return; 394 } 395 int main() 396 { 397 ios_base::sync_with_stdio(false); 398 cin.tie(NULL); 399 precompute(MOD); 400 ll t=1; 401 //cin>>t; 402 while(t--){ 403 solve(); 404 } 405 } 406 ``` 407 408 [1762F - Good Pairs](/contest/1762/problem/F "Codeforces Round 838 (Div. 2)") 409 410 Idea:[satyam343](/profile/satyam343 "Master satyam343") 411 412 **Hint 1** 413 414 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}$. 415 416 Why not solve the easier version first? 417 418 A pair $(l,r)$ is *good* if there exists a sequence of indices $i_1, i_2, \dots, i_m$ such that 419 420 * $i_1=l$ and $i_m=r$; 421 * $i_j \lt i_{j+1}$ for all $1 \leq j \lt m$; and 422 * $0 \lt a_{i_j}-a_{i_{j+1}} \leq k$ for all $1 \leq j \lt m$. 423 424 Suppose $F(a,k)$ number of pairs $(l,r)$ ($1 \leq l \lt r \leq n$) that are good. 425 426 Find $F(a,k)$. 427 428 **Hint 2** 429 430 To solve the problem in hint $1$, let us define $dp_i$ as the number of pairs $j(i \lt j)$ such that $(i,j)$ is good. 431 432 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]$. 433 434 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)$. 435 436 **Hint 3** 437 438 Now let us get back to original problem. 439 440 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. 441 442 Time for another cool claim! 443 444 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. 445 446 **Solution** 447 448 How to prove the claim in hint $3$? 449 450 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$ 451 452 * such that difference between adjacent elements of $a$ is atmost $k$ 453 * strictly increasing if $a_l \lt a_r$ 454 * strictly decreasing if $a_l \gt a_r$ 455 456 Thus $(l,r)$ will be counted in $F(a,k)$ if $a_l \lt a_r$ and $(l,r)$ will be counted in $F(rev(a),k)$ if $a_l \gt a_r$. 457 458 Time complexity is $O(n \cdot \log(n))$. 459 460 **Code** 461 462 ``` 463 #include <bits/stdc++.h> 464 using namespace std; 465 #define ll long long 466 const ll MAX=1000100; 467 class ST{ 468 public: 469 vector<ll> segs; 470 ll size=0; 471 ll ID=MAX; 472 473 ST(ll sz) { 474 segs.assign(2*sz,ID); 475 size=sz; 476 } 477 478 ll comb(ll a,ll b) { 479 return min(a,b); 480 } 481 482 void upd(ll idx, ll val) { 483 segs[idx+=size]=val; 484 for(idx/=2;idx;idx/=2){ 485 segs[idx]=comb(segs[2*idx],segs[2*idx+1]); 486 } 487 } 488 489 ll query(ll l,ll r) { 490 ll lans=ID,rans=ID; 491 for(l+=size,r+=size+1;l<r;l/=2,r/=2) { 492 if(l&1) { 493 lans=comb(lans,segs[l++]); 494 } 495 if(r&1){ 496 rans=comb(segs[--r],rans); 497 } 498 } 499 return comb(lans,rans); 500 } 501 }; 502 struct FenwickTree{ 503 vector<ll> bit; 504 ll n; 505 FenwickTree(ll n){ 506 this->n = n; 507 bit.assign(n, 0); 508 } 509 FenwickTree(vector<ll> a):FenwickTree(a.size()){ 510 ll x=a.size(); 511 for(size_t i=0;i<x;i++) 512 add(i,a[i]); 513 } 514 ll sum(ll r) { 515 ll ret=0; 516 for(;r>=0;r=(r&(r+1))-1) 517 ret+=bit[r]; 518 return ret; 519 } 520 ll sum(ll l,ll r) { 521 if(l>r) 522 return 0; 523 return sum(r)-sum(l-1); 524 } 525 void add(ll idx,ll delta) { 526 for(;idx<n;idx=idx|(idx+1)) 527 bit[idx]+=delta; 528 } 529 }; 530 FenwickTree freq(MAX); 531 ST segtree(MAX); 532 vector<ll> dp(MAX,0); 533 ll solve(vector<ll> a,ll n,ll k){ 534 ll now=0; 535 for(ll i=n-1;i>=0;i--){ 536 ll j=segtree.query(a[i]+1,a[i]+k); 537 if(j<n){ 538 dp[i]=dp[j]+freq.sum(a[i]+1,a[j]); 539 } 540 else{ 541 dp[i]=0; 542 } 543 now+=dp[i]; 544 segtree.upd(a[i],i); 545 freq.add(a[i],1); 546 } 547 for(auto it:a){ 548 segtree.upd(it,MAX); 549 freq.add(it,-1); 550 } 551 return now; 552 } 553 void solve(){ 554 ll n,k; cin>>n>>k; 555 vector<ll> a(n); 556 ll ans=0; 557 map<ll,ll> cnt; 558 for(auto &it:a){ 559 cin>>it; 560 cnt[it]++; 561 ans+=cnt[it]; 562 } 563 ans+=solve(a,n,k); 564 reverse(a.begin(),a.end()); 565 ans+=solve(a,n,k); 566 cout<<ans<<"\n"; 567 return; 568 } 569 int main() 570 { 571 ios_base::sync_with_stdio(false); 572 cin.tie(NULL); 573 ll t=1; 574 cin>>t; 575 while(t--){ 576 solve(); 577 } 578 } 579 ``` 580 581 [1762G - Unequal Adjacent Elements](/contest/1762/problem/G "Codeforces Round 838 (Div. 2)") 582 583 Idea:[satyam343](/profile/satyam343 "Master satyam343") 584 585 **Hint 1** 586 587 Answer is NO only when there exists an element of $a$ which occurs more that $\lceil \frac{n}{2} \rceil$ times. 588 589 **Hint 2** 590 591 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. 592 593 If $a$ is beautiful, there exists only one permutation. 594 595 We have rearrange such that $x$ occupies all the odd indices and keep the elements at even indices such that condition $2$ in satisfied. 596 597 **Hint 3** 598 599 To solve the original problem, we will divide the array $a$ into multiple beautiful subarrays and arrange the elements in those subarrays. 600 601 **Solution** 602 603 Let us continue from where we left off. 604 605 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. 606 607 Here is one construction using which we can achieve our goal. 608 609 Suppose $l$ denotes the leftmost point of our concerned subarray. 610 611 If $a_l \neq a_{l+1}$, we move forward, as subarray $a[l,l]$ is good. 612 613 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]$ 614 615 * length of this subarray is odd 616 * $a_l$ occurs exactly $\lceil \frac{r-l+1}{2} \rceil$ times in this subarray 617 618 Now we can rearrange the elements of this subarray $a[l,r]$. 619 620 Do note that the subarray $a[1,r]$ satisfies both the conditions stated in the statement. 621 622 So our task is to make the subarray $a[r+1,n]$ good now. 623 624 We can now update $l=r+1$ and continue searching for the corresponding $r$ and so on. 625 626 Now it might be the case that we did not get a valid $r$ for the last search. 627 628 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. 629 630 Assume that we had started at $pos=l$ and couldn't find $r$. 631 632 Subarray $a[1,pos-1]$ is already good. 633 634 To fix this issue, we will do a similar search that we did before. 635 636 We start from the back(from index $n$) and move towards left till index $m$ such that 637 638 * $m \lt pos$ 639 * $a[m,n]$ is beautiful 640 * $a_{pos}$ occurs exactly $\lceil \frac{n-m+1}{2} \rceil$ times in this subarray 641 * $a_{pos} \neq a_{m-1}$ 642 643 Now we arrange elements of this subarray in the same fashion that we did before. 644 645 Are we done? 646 647 No. First, we must prove that we will always get some $m$. 648 649 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]$ 650 651 It is easy to note that $f(a,pos,n,a_{pos}) \gt 1$ 652 653 (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 )) 654 655 Now we start from the back and move towards the right to find $m$ with $n$ as our right endpoint of the concerned subarray. 656 657 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$) 658 659 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$) 660 661 Are we done? 662 663 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]$. 664 665 How to fix this issue? It's pretty easy to fix this issue. 666 667 **Hint** 668 669 Instead of rearranging the subarray $a[m,n]$, we will rearrange the subarray $a[m-1,n]$. 670 671 How to rearrange? 672 673 Okay, time for one more hint. 674 675 What will be the answer for $a=[1,1,2,3,3]$? 676 677 **Answer** 678 679 $p=[1,4,2,5,3]$ 680 681 You can refer to the attached code for implementation details. 682 683 **Code** 684 685 ``` 686 #include <bits/stdc++.h> 687 using namespace std; 688 #define ll long long 689 #define all(x) x.begin(),x.end() 690 void solve(){ 691 ll n; cin>>n; 692 vector<ll> a(n+5),freq(n+5,0); 693 for(ll i=1;i<=n;i++){ 694 cin>>a[i]; freq[a[i]]++; 695 } 696 for(ll i=1;i<=n;i++){ 697 ll till=(n+1)/2; 698 if(freq[i]>till){ 699 cout<<"NO\n"; 700 return; 701 } 702 } 703 cout<<"YES\n"; 704 vector<ll> ans; 705 ll cur=1; 706 while(cur<=n){ 707 ll val=a[cur]; 708 vector<ll> v1,v2; 709 while(cur<=n){ 710 if(a[cur]==val){ 711 v1.push_back(cur); 712 } 713 else{ 714 v2.push_back(cur); 715 } 716 if(v1.size()==v2.size()){ 717 for(ll i=0;i<v1.size();i++){ 718 ans.push_back(v1[i]); ans.push_back(v2[i]); 719 } 720 ans.pop_back(); 721 break; 722 } 723 if(cur==n){ 724 while(1){ 725 if(ans.empty()||v1.size()==v2.size()){ 726 sort(all(v1)); sort(all(v2)); 727 if(v1.size()!=v2.size()){ 728 ans.push_back(v1[0]); 729 v1.erase(v1.begin()); 730 } 731 if(!v2.empty()&&!ans.empty()){ 732 if(a[ans.back()]==a[v2[0]]){ 733 swap(v1,v2); 734 } 735 } 736 for(ll i=0;i<v1.size();i++){ 737 ans.push_back(v2[i]); ans.push_back(v1[i]); 738 } 739 break; 740 } 741 if(a[ans.back()]==val){ 742 v1.push_back(ans.back()); 743 } 744 else{ 745 v2.push_back(ans.back()); 746 } 747 ans.pop_back(); 748 } 749 cur=n+1; 750 } 751 cur++; 752 } 753 } 754 for(auto it:ans){ 755 cout<<it<<" "; 756 } 757 cout<<"\n"; 758 return; 759 } 760 int main() 761 { 762 ll test_cases=1; 763 cin>>test_cases; 764 while(test_cases--){ 765 solve(); 766 } 767 } 768 ```