codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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 ```