codeforces-scrape

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

2120.md (35657B)


      1 Source: https://codeforces.com/blog/entry/144048
      2 
      3 Thanks for participating in our CodeNite 2025.
      4 
      5 #### [2120A — Square of Rectangles](https://codeforces.com/contest/2120/problem/A)
      6 
      7 Idea: [Dragmon](/profile/Dragmon "Expert Dragmon") Solution: [Dragmon](/profile/Dragmon "Expert Dragmon") Prepared by: [Dragmon](/profile/Dragmon "Expert Dragmon")
      8 
      9 **Hint**
     10 
     11 There are only two possible ways to arrange rectangles into a square if possible.
     12 
     13 **Solution**
     14 
     15 The only cases possible to arrange rectangles into a square are:
     16 
     17 1. All three rectangles are put side by side, i.e. $l_1=l_2=l_3=b_1+b_2+b_3$ or $b_1=b_2=b_3=l_1+l_2+l_3$.
     18 2. Rectangles $2$ and $3$ are side by side with rectangle $1$ above it, i.e. $l_1+l_2=l_1+l_3=b_1=b_2+b_3$ or $b_1+b_2=b_1+b_3=l_1=l_2+l_3$.
     19 
     20 Check both these cases, and if either is true, output YES, otherwise NO. Complexity is $O(1)$ per test.
     21 
     22 **Code - aryansanghi**
     23 
     24 ```
     25 //Written By Aryan Sanghi
     26 
     27 #include<bits/stdc++.h>
     28 
     29 using namespace std;
     30 
     31 #define ll long long int
     32 
     33 int main()
     34 {
     35     ll t;
     36     cin>>t;
     37 
     38     while(t--)
     39     {
     40         ll l1, b1, l2, b2, l3, b3;
     41         cin>>l1>>b1>>l2>>b2>>l3>>b3;
     42 
     43         if(l1+l2+l3 == b1 && b1==b2 && b2==b3) cout<<"YES\n";
     44         else if(l2+l3 == l1 && b2==b3 && b1+b2==l1) cout<<"YES\n";
     45         else if(b1+b2+b3 == l1 && l1==l2 && l2==l3) cout<<"YES\n";
     46         else if(b2+b3 == b1 && l2==l3 && l1+l2==b1) cout<<"YES\n";
     47         else cout<<"NO\n";
     48     }
     49 }
     50 ```
     51 
     52 **Code - harshith_04**
     53 
     54 ```
     55 #include <iostream>
     56 using namespace std;
     57  
     58 int main(){
     59     int t;
     60     cin >> t;
     61     
     62     int l1, b1, l2, b2, l3, b3;
     63     
     64     auto check = [&] () {
     65         if (l1 == l2 && l2 == l3) return (l1 == b1 + b2 + b3 || (b1 == b2 + b3 && 2*l1 == b1));
     66         if (l2 == l3) return (b2 + b3 == b1 && b1 == l2 + l1);
     67         return false;
     68     };
     69     
     70     while(t--) {
     71         cin >> l1 >> b1 >> l2 >> b2 >> l3 >> b3;
     72         if(check()) cout << "YES\n";
     73         else {
     74             swap(l1, b1); swap(l2, b2); swap(l3, b3);
     75             if(check()) cout << "YES\n";
     76             else cout << "NO\n";
     77         }
     78     }
     79     
     80     return 0;
     81 }
     82 ```
     83 
     84 #### [2120B — Square Pool](https://codeforces.com/contest/2120/problem/B)
     85 
     86 Idea: [harshith_04](/profile/harshith_04 "Candidate Master harshith_04"), [Dragmon](/profile/Dragmon "Expert Dragmon") Solution: [harshith_04](/profile/harshith_04 "Candidate Master harshith_04"), [Dragmon](/profile/Dragmon "Expert Dragmon") Prepared by: [harshith_04](/profile/harshith_04 "Candidate Master harshith_04")
     87 
     88 **Hint 1**
     89 
     90 What happens to the balls that collide with an edge, eventually?
     91 
     92 **Hint 2**
     93 
     94 How does a collision between two balls affect the outcome?
     95 
     96 **Solution**
     97 
     98 Observations
     99 
    100 * Any ball on the diagonals of the square that is shot towards a pocket will be potted on a free table.
    101 * Any ball that collides with an edge will be in a $4$-periodic path colliding with the $4$ edges forever on a free table.
    102 * The collisions are elastic, so if two balls collide, they exchange their directions.
    103 * $\bigstar$ Neither collisions affect the effective number of balls traversing towards a pocket.
    104 
    105 Therefore, the answer is the number of balls initially on the diagonals of the square and shot towards the pockets.
    106 
    107 Hope you liked the figures; a lot of effort went into them.
    108 
    109 **Code - harshith_04**
    110 
    111 ```
    112 #include <iostream>
    113 using namespace std;
    114 
    115 int main() {
    116     int t;
    117     cin >> t;
    118     
    119     int n, s, ans = 0, dxi, dyi, xi, yi;
    120     while(t--) {
    121         cin >> n >> s;
    122         
    123         for (int i = 0; i < n; i++) {
    124             cin >> dxi >> dyi >> xi >> yi;
    125             if (dxi == dyi) ans += (xi == yi);
    126             else ans += (xi + yi == s);
    127         }
    128         
    129         cout << ans << '\n';
    130         ans = 0;
    131     }
    132     return 0;
    133 }
    134 ```
    135 
    136 #### [2120C — Divine Tree](https://codeforces.com/contest/2120/problem/C)
    137 
    138 Idea: [harshith_04](/profile/harshith_04 "Candidate Master harshith_04") Solution: [harshith_04](/profile/harshith_04 "Candidate Master harshith_04") Prepared by: [harshith_04](/profile/harshith_04 "Candidate Master harshith_04")
    139 
    140 **Hint**
    141 
    142 What are bounds on $m$ for a given $n$ to have a divine tree? And how does the tree look for the lower bound and the upper bound?
    143 
    144 **Solution**
    145 
    146 The $\text{min}$ and $\text{max}$ value of $m$ for a divine tree to exist are $n$ and $\frac{n \cdot (n + 1)}{2}$ respectively.
    147 
    148 $\text{POC:}$ Any $m \in [\text{min}, \text{max}]$ can be achieved similar to exhaustive subset sum with redraws enabled.
    149 
    150 Let $p = m - n$, $\text{cur} = 0$, $\text{ans}$ = [ ]. Now, we need to select a multiset of $n$ non-negative integers that sum to $p$.
    151 
    152 $\text{Greedy:}$ Loop $j$ from $n - 1$ to $0$, if $\text{cur} + i \le p$: $\text{cur}$ += $i,$ $\text{ans.push_back}(i + 1)$
    153 
    154 If $\text{ans.back}()$ is not $1$ add a $1$, why?
    155 
    156 $\text{Construction:}$ The tree can always be simple path, why?
    157 
    158 1. Tree is rooted at $\text{ans}[0]$. Let's store $\text{vis}[0:n - 1] = \text{false}$ to keep track if a node is visited or not.
    159 2. Loop $i$ from $1$ to $\text{size(ans)}$ and add edge between $\text{ans}[i-1]$ to $\text{ans}[i]$ and mark all of them $\text{true}$ in $\text{vis}$.
    160 3. Take all un-visited in the array $\text{unvis}$ and add an edge from $1$ to $\text{unvis}[0]$.
    161 4. Loop $i$ from $1$ to $\text{size(unvis)}$ and add an edge from $\text{unvis}[i-1]$ to $\text{unvis}[i]$.
    162 
    163 The divine tree which is a simple path looks like $\text{ans}[0] \leftrightarrow$ . . . $\leftrightarrow 1 \leftrightarrow \text{unvis}[0] \leftrightarrow$ . . . $\leftrightarrow \text{unvis.back}()$.
    164 
    165 **Code - harshith_04**
    166 
    167 ```
    168 #include <iostream>
    169 #include <cstdint>
    170 #include <cassert>
    171 #include <vector>
    172 
    173 using namespace std;
    174 
    175 #define i64 int64_t
    176 
    177 void solve() {
    178     i64 n, sum;
    179     cin >> n >> sum;
    180 
    181     if(sum < n || sum > n * (n + 1) / 2) {
    182         cout << "-1\n";
    183         return;
    184     }
    185 
    186     i64 k = sum - n;
    187 
    188     vector<i64> ans;
    189     i64 curr = 0, nsum = 0;
    190 
    191     for(i64 i = n - 1; i >= 0; --i) {
    192         if(curr == k) break;
    193         if(curr + i <= k) {
    194             curr += i;
    195             ans.push_back(i + 1);
    196             nsum += i + 1;
    197         }
    198     }
    199 
    200     i64 ct = ans.size();
    201     for(i64 i = 0; i < n - ct; ++i) ans.push_back(1);
    202 
    203     nsum += (n - ct);
    204     
    205     assert(nsum == sum);
    206 
    207     if(n == sum) {
    208         cout << "1\n";
    209         for(i64 i = 1; i < n; i++) cout << i << ' ' << i + 1 << '\n';
    210         return;
    211     }
    212 
    213     vector<bool> vis(n + 1, 1);
    214     cout << ans[0] << '\n';
    215     vis[ans[0]] = 0;
    216 
    217     for(i64 i = 1; i <= n; i++) {
    218         cout << ans[i - 1] << ' ' << ans[i] << '\n';
    219         vis[ans[i - 1]] = 0, vis[ans[i]] = 0;
    220 
    221         if(ans[i] == 1) {
    222             i64 prev = 1;
    223             for(i64 j = 2; j <= n; ++j) {
    224                 if(vis[j]) {
    225                     cout << prev << ' ' << j << '\n';
    226                     prev = j;
    227                 }
    228             }
    229             return;
    230         }
    231     }
    232 }
    233 
    234 int main() {
    235     ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    236     
    237     i64 t;
    238     cin >> t;
    239 
    240     while(t--) solve();
    241     return 0;
    242 }
    243 ```
    244 
    245 #### [2120D — Matrix Game](https://codeforces.com/contest/2120/problem/D)
    246 
    247 Idea: [Dragmon](/profile/Dragmon "Expert Dragmon") Solution: [Dragmon](/profile/Dragmon "Expert Dragmon") Prepared by: [Dragmon](/profile/Dragmon "Expert Dragmon")
    248 
    249 **Hint**
    250 
    251 Use pigeonhole principle to get minimum $n$ and then minimum $m$.
    252 
    253 **Solution**
    254 
    255 If each column is of size $n=k(a-1)+1$, by pigeonhole principle, it will have at least $a$ elements with the same value. Let those elements appear positions $p_1 \lt p_2 \lt ... \lt p_a$($p_i$ is the row number where the element occurs) and let the value be $v$. Consider the tuple $(v, p_1,p_2,...,p_a)$. If the same tuple appears $b$ times, we are done as we obtain an $a*b$ submatrix with all elements of same value. The number of possible values of the tuple is $k\times\,^nC_a$. So, there should be atleast $m=(b-1)k\times\,^nC_a+1$ columns for there to be $b$ repetitions by pigeonhole principle.
    256 
    257 **Code - aryansanghi**
    258 
    259 ```
    260 //Written By Aryan Sanghi
    261  
    262 #include<bits/stdc++.h>
    263  
    264 using namespace std;
    265  
    266 #define int long long
    267  
    268 const int mod=1e9+7;
    269  
    270 int modpower(int a, int b)
    271 {
    272     int r=1;
    273     
    274     a=a%mod;
    275     while(b>0)
    276     {
    277         if(b%2==1)
    278         {
    279             r*=a;
    280             r%=mod;
    281         }
    282         
    283         b=b/2;
    284         a*=a;
    285         a%=mod;
    286         
    287     }
    288     
    289     return r;
    290 }
    291  
    292  
    293 int32_t main(){
    294     int t;
    295     cin>>t;
    296  
    297     while(t--){
    298         int a, b, k;
    299         cin>>a>>b>>k;
    300         
    301         int n=1, m=1;
    302         
    303         n*=a-1;
    304         n%=mod;
    305         n*=k;
    306         n%=mod;
    307         n+=1;
    308         n%=mod;
    309         
    310         m*=b-1;
    311         m%=mod;
    312         m*=k;
    313         m%=mod;
    314         for(int i=0;i<a;i++){
    315             m*=(n-i+mod)%mod;
    316             m%=mod;
    317             m*=modpower((a-i+mod)%mod, mod-2)%mod;
    318             m%=mod;
    319         }
    320         m+=1;
    321         m%=mod;
    322         
    323         cout<<n<<" "<<m<<"\n";
    324     }
    325 }
    326 ```
    327 
    328 **Code - Starsilk**
    329 
    330 ```
    331 #include <bits/stdc++.h>
    332 using namespace std;
    333 const long long mod=1000000007;
    334 long long inv[100001];
    335 int main(){
    336 	ios::sync_with_stdio(false),cin.tie(0);
    337 	int T;
    338 	long long i,a,b,k,d,ans;
    339 	inv[1]=1;
    340 	for(i=2;i<=100000;i++)inv[i]=(mod-mod/i)*inv[mod%i]%mod;
    341 	for(cin>>T;T>0;T--)
    342 	{
    343 		cin>>a>>b>>k;
    344 		d=k*a-k+1;
    345 		ans=k;
    346 		for(i=1;i<=a;i++)ans=ans*((d-i+1)%mod)%mod*inv[i]%mod;
    347 		cout<<d%mod<<' '<<(ans*b-ans+1+mod)%mod<<'\n';
    348 	}
    349 	return 0;
    350 }
    351 ```
    352 
    353 #### [2120E — Lanes of Cars](https://codeforces.com/contest/2120/problem/E)
    354 
    355 Idea: [Dragmon](/profile/Dragmon "Expert Dragmon") Solution: [Dragmon](/profile/Dragmon "Expert Dragmon") Prepared by: [picramide](/profile/picramide "Master picramide"), [Dragmon](/profile/Dragmon "Expert Dragmon")
    356 
    357 **Hint 1**
    358 
    359 Use binary search to find minimum number of cars in a lane after optimal number lane shifts.
    360 
    361 **Hint 2**
    362 
    363 Adjust cars afterwards such that minimum number of cars remains same as found in binary search, but angriness is minimized.
    364 
    365 **Solution**
    366 
    367 Observe the following(Let $1$ car shift lanes at a time):
    368 
    369 1. It is always optimal to shift the car at the back of a lane before shifting cars in front of it.
    370 2. The optimal condition is that in every iteration, the car shifts from the back of the lane with max cars to the back of the lane with minimum cars.
    371 3. If $(\text{cars in the max lane} - \text{cars in min lane}) \lt = K$, then it is not optimal to shift any cars as it will only increase the angriness.
    372 4. It doesn't matter when a car switches lane; it can switch at any time and the optimal answer remains the same.
    373 
    374 For a value $v$, let
    375 
    376 1. $def(v)$ be number of cars required such that each lane has atleast $v$ cars, i.e. $def(v)=\sum_{i=1}^N max(0, v-a[i]))$
    377 2. $defs(v)$ be number of lanes with less than $v$ cars initially, i.e. $defs(v)=\sum_{i=1}^N (v-a[i] \gt 0)$.
    378 3. $exc(v)$ be number of cars to remove such that each lanes has atmost $v$ cars, i.e. $exc(v)=\sum_{i=1}^N max(0, a[i]-v)$
    379 4. $excs(v)$ be number of lanes with more than $v$ cars initially, i.e. $excs=\sum_{i=1}^N (a[i]-v \gt 0)$
    380 
    381 Using binary search, find the maximum value of $v$ for which $exc(v+k) \gt def(v)$. This $v$ denotes the minimum value that the array will have after cars have switched lanes optimally, and the maximum value of the array will be $v+k$ if $exc(v+k)=def(v)$ and $v+k+1$ if $exc(v+k) \gt def(v)$.
    382 
    383 Final sorted array $A'$ after optimal lane switches will have values between $v+1$ and $v+k-1$ remain the same as array $A$. Of the first $defs(v)$ elements, last $max(0, exc(v)-def(v)-excs(v))$ values will be $v+1$ and remaining values will be $v$. Of the last $excs(v)$ elements, last $min(excs(v), exc(v)-def(v))$ values will be $v+k+1$ and remaining elements will be $v+k$. Find minimum angriness after optimal lane switches using array $A'$ and calculating number of cars that have switched lanes. Time complexity is $O(n \log \max(A_i))$
    384 
    385 Special thanks to [picramide](/profile/picramide "Master picramide") for the initial problem idea, which I misheard and it turned into this problem.
    386 
    387 **Code - aryansanghi**
    388 
    389 ```
    390 //Written By Aryan Sanghi
    391 
    392 #include<bits/stdc++.h>
    393 
    394 using namespace std;
    395 
    396 #define ll long long int
    397 #define rep(i, n) for(ll i = 0; i < n;i++)
    398 
    399 int main()
    400 {
    401     ll t;
    402     cin>>t;
    403 
    404     while(t--)
    405     {
    406         ll n, k;
    407         cin>>n>>k;
    408 
    409         vector<ll> a(n, 0);
    410         ll suma=0;
    411         rep(i, n) cin>>a[i], suma+=a[i];
    412 
    413         sort(a.begin(), a.end());
    414 
    415         ll l=a[0], r=(suma+n-1)/n + 1;
    416 
    417         while(r-l>1){
    418             ll mid=(l+r)/2;
    419             
    420             ll req=0, exc=0;
    421             rep(i, n) req+=max<ll>(0, mid-a[i]), exc+=max<ll>(0, a[i]-mid-k);
    422 
    423             if(req>exc) r=mid;
    424             else l=mid;
    425         }
    426 
    427         ll req=0, exc=0, reqs=0, excs=0, ans=0;
    428         rep(i, n){
    429             if(a[i]<=l) reqs++, req+=l-a[i], a[i]=l;
    430             if(a[i]>=l+k+1) excs++, exc+=a[i]-l-k, a[i]=l+k;
    431         }
    432         exc -= req;
    433         rep(i, min<ll>(excs, exc)) a[n - 1 - i]++;
    434         exc -= excs;
    435         rep(i, exc) a[i]++, req++;
    436         ans += req * k;
    437         for(int i = 0; i < n; ++i) ans += (a[i] * (a[i] + 1)) / 2;
    438         // rep(i, n) cout << a[i] << " ";
    439         // cout << "\n";
    440         cout << ans <<"\n";
    441     }
    442 }
    443 ```
    444 
    445 **Code - ugly2333**
    446 
    447 ```
    448 //��
    449 #include<bits/stdc++.h>
    450 using namespace std;
    451 typedef long long LL;
    452 typedef double DB;
    453 const int N = 1111111;
    454 const LL inf = 1e18;
    455 int n,k,a[N];
    456 LL s[N];
    457 int main(){
    458 	int T,i,l,r,h;
    459 	LL x,y,z,o,p,t;
    460 	scanf("%d",&T);
    461 	while(T--){
    462 		scanf("%d%d",&n,&k);
    463 		for(i=1;i<=n;i++)
    464 			scanf("%d",a+i);
    465 		sort(a+1,a+n+1);
    466 		for(i=1;i<=n;i++)
    467 			s[i]=s[i-1]+a[i];
    468 		z=inf,o=-1;
    469 		l=0,r=N;
    470 		while(l<=r){
    471 			h=l+r>>1;
    472 			i=lower_bound(a+1,a+n+1,h)-a-1;
    473 			x=(LL)i*h-s[i];
    474 			i=lower_bound(a+1,a+n+1,h+k)-a-1;
    475 			y=(s[n]-s[i])-(LL)(n-i)*(h+k);
    476 			if(z>max(x,y))
    477 				z=max(x,y),o=h;
    478 			if(x<y)
    479 				l=h+1;
    480 			else
    481 				r=h-1;
    482 		}
    483 		//cout<<z<<' '<<o<<endl;
    484 		p=z*k;
    485 		t=0;
    486 		for(i=1;i<=n;i++){
    487 			x=min(max((LL)a[i],o),o+k);
    488 			p+=(LL)x*(x+1)/2;
    489 			t+=x-a[i];
    490 		}
    491 		if(t>0)
    492 			p-=(o+k)*t;
    493 		if(t<0)
    494 			p+=(o+1)*-t;
    495 		printf("%lld\n",p);
    496 	}
    497 	return 0;
    498 }
    499 ```
    500 
    501 #### [2120F — Superb Graphs](https://codeforces.com/contest/2120/problem/F)
    502 
    503 Idea: [Dragmon](/profile/Dragmon "Expert Dragmon") Solution: [Dragmon](/profile/Dragmon "Expert Dragmon") Prepared by: [picramide](/profile/picramide "Master picramide"), [Dragmon](/profile/Dragmon "Expert Dragmon")
    504 
    505 **Hint 1**
    506 
    507 If two vertices have same open neighborhood in some graph $G_i$, atleast one of them has to correpond to a clique in every $G_i, H_i$ pair.
    508 
    509 **Hint 2**
    510 
    511 If two vertices have same closed neighborhood in some graph $G_i$, atleast one of them has to correpond to an independent set in every $G_i, H_i$ pair.
    512 
    513 **Solution**
    514 
    515 In a graph $G$, two vertices $v_1$ and $v_2$ are said to be of type1 if they are not adjacent and have the same open neighborhood, i.e., $v_1v_2 \not\in E(G)$ and $N_G(v_1)=N_G(v_2)$.
    516 
    517 In a graph $G$, two vertices $v_1$ and $v_2$ are said to be of type2 if they are adjacent and have the same closed neighborhood, i.e., $v_1v_2 \in E(G)$ and $N_G[v_1]=N_G[v_2]$.
    518 
    519 An equivalence class is defined as the set of vertices of the same type. Here, note that if two vertices of type1 are present, then both vertices can't correspond to independent sets as we can merge them to a larger independent set and denote it by a single vertex. Similarly, if two vertices of type2 are present, then both can't correspond to cliques as we can merge them to a larger clique and denote it by a single vertex.
    520 
    521 Proof:
    522 
    523 * Graph is superb $\rightarrow$ Every type1 pair has atleast one vertex correspond to a clique and every type2 pair has atleast one vertex correspond to an independent set(We'll prove contrapositive).
    524 
    525 Assume there exists a type1 pair $v_1v_2$ that has both vertices corresponding to an independent set. Let their vertex set be $V_1$ and $V_2$. Consider the set $V=V_1 \cup V_2$ and a new vertex $v$ that has the same neighborhood as $v_1(or v_2)$. Each vertex in the set $V$ satisfies all of the $4$ conditions given, as if vertices in set $V_1$ were connected to a vertex, so is every vertex in the set $V_2$ and vice versa. Hence, we can merge both $v_1$ and $v_2$ into a single vertex $v$ and still satisfy the conditions, making the graph not superb as it doesn't have minimum order. Same reasoning goes for a type2 pair.
    526 
    527 * Every type1 pair has atleast one vertex correspond to a clique and every type2 pair has atleast one vertex correspond to an independent set $\rightarrow$ Graph is superb.
    528 
    529 Consider a graph $G({v_i}, E)$. Let its fun graph be $G'({V_i}, E')$. Observe that if two vertices $V_i$ and $V_j$ have different neighborhoods (excluding each other), then we can't have any fun graph $G2'$ in which a vertex $K$ contains some non-zero vertices of $V_i$ and some non-zero vertices of $V_j$. This is because if that happens, then it means all vertices in set $K$ have the same neighborhood, excluding each other, meaning that $V_i$ and $V_j$ have the same neighborhood, excluding each other, a contradiction. For the same reasons, if two vertices have the same neighborhood, excluding each other, they have to be either a type1 or type2 pair for there to exist another fun graph $G2'$ in which a vertex $K$ contains some non-zero vertices from both sets. Suppose every type1 pair has at least one vertex corresponding to a clique, and every type2 pair has at least one vertex corresponding to an independent set. In that case, there can't be any fun graph $G2'$ in which a vertex K contains some non-zero vertices from two sets of $G'$ as set $K$ has either all vertices in it connected or none of them connected. So, in $G2'$, each vertex $K$ corresponds to a subset of vertices of $G'$, implying that it has at least as many vertices as $G'$. So, $G'$ is of minimum cardinality and so is superb. \end{enumerate}
    530 
    531 So, for this problem, a vertex is assigned $0$ if it is assigned an independent set and a vertex is assigned $1$ if it is assigned a clique. Consider two vertices $a$ and $b$. If both are type1, then we can denote it by $a \lor b$(both can't be I.S.) and if both are type2, we can denote it by $\lnot a \lor \lnot b$(Both can't be cliques). We can make a $2$-sat equation using this. If the $2$-sat has a solution, then the graph is a superb graph. Else, it is not. Expected complexity is $O(n^3)$
    532 
    533 **Code - picramide**
    534 
    535 ```
    536 #include <bits/stdc++.h>
    537 using namespace std;
    538 #define endl '\n'
    539 #define int long long
    540 
    541 bool twoSAT(vector<vector<int>> &adj, vector<vector<int>> &adj_rev, vector<bool> &assignment) {
    542     int n = adj.size();
    543     vector<int> order;
    544     vector<bool> used(n, false);
    545 
    546     function<void(int)> dfs1 = [&](int v) {
    547         used[v] = true;
    548 
    549         for(auto u : adj[v]) 
    550             if(!used[u])
    551                 dfs1(u);
    552 
    553         order.push_back(v);
    554     };
    555 
    556     vector<int> comp(n, -1);
    557 
    558     function<void(int, int)> dfs2 = [&](int v, int color) {
    559         comp[v] = color;
    560 
    561         for(auto u : adj_rev[v]) 
    562             if(comp[u] == -1)
    563                 dfs2(u, color);
    564     };
    565 
    566     for(int i = 0; i < n; ++i) 
    567         if(!used[i])
    568             dfs1(i);
    569 
    570     used.assign(n, false);
    571 
    572     for(int i = 0, j = 0; i < n; ++i) {
    573         int v = order[n - i - 1];
    574         if(comp[v] == -1)
    575             dfs2(v, j++);
    576     }
    577 
    578     assignment.assign(n / 2, false);
    579     for(int i = 0; i < n; i += 2) {
    580         if(comp[i] == comp[i + 1]) 
    581             return false; 
    582         assignment[i / 2] = comp[i] > comp[i + 1];
    583     }
    584     return true;
    585 }
    586 
    587 void solve() {
    588     int n, k; cin >> n >> k;
    589 
    590     vector<vector<int>> adj(2*n), adj_rev(2*n);
    591 
    592     auto add_or = [&](int a, bool nega, int b, bool negb) {
    593         a = (2*a) + nega;
    594         b = (2*b) + negb;
    595         adj[a^1].push_back(b);
    596         adj[b^1].push_back(a);
    597         adj_rev[b].push_back(a^1);
    598         adj_rev[a].push_back(b^1);
    599     };
    600 
    601     function<void(int, vector<vector<int>>&)> process = [&n, &add_or](int m, vector<vector<int>> &adj) {
    602         map<vector<int>, vector<int>> mp;
    603 
    604         for(int i = 0; i < n; ++i) {
    605             auto temp = adj[i];
    606             temp.push_back(i);
    607             sort(temp.begin(), temp.end());
    608 
    609             mp[temp].push_back(i);
    610         }
    611 
    612         for(auto [x, y] : mp) {
    613             for(int i = 0; i < y.size(); ++i) {
    614                 for(int j = i + 1; j < y.size(); ++j) {
    615                     add_or(y[i], 1, y[j], 1);
    616                 }
    617             }
    618         }
    619 
    620         mp.clear();
    621 
    622         for(int i = 0; i < n; ++i) {
    623             sort(adj[i].begin(), adj[i].end());
    624             mp[adj[i]].push_back(i);
    625         }
    626 
    627         for(auto [x, y] : mp) {
    628             for(int i = 0; i < y.size(); ++i) {
    629                 for(int j = i + 1; j < y.size(); ++j) {
    630                     add_or(y[i], 0, y[j], 0);
    631                 }
    632             }
    633         }
    634     };
    635 
    636     for(int i = 0; i < k; ++i) {
    637         int m; cin >> m;
    638         vector<vector<int>> adj(n);
    639 
    640         for(int j = 0; j < m; ++j) {
    641             int x, y; cin >> x >> y;
    642             x--; y--;
    643             adj[x].push_back(y);
    644             adj[y].push_back(x);
    645         }
    646 
    647         process(m, adj);
    648     }
    649 
    650     vector<bool> assignment(n, false);
    651     cout << ((twoSAT(adj, adj_rev, assignment)) ? "Yes" : "No");
    652 }
    653 
    654 int32_t main() {
    655     ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    656     int _TC = 0; cin >> _TC;
    657     for(int _ct = 1; _ct <= _TC; ++_ct) {
    658         solve(); cout << endl;
    659     }
    660 }
    661 ```
    662 
    663 **Bonus problem**
    664 
    665 When is a graph a superb graph of itself?
    666 
    667 #### [2120G — Eulerian Line Graph](https://codeforces.com/contest/2120/problem/G)
    668 
    669 Idea: [Dragmon](/profile/Dragmon "Expert Dragmon") Solution: [Dragmon](/profile/Dragmon "Expert Dragmon") Prepared by: [Dragmon](/profile/Dragmon "Expert Dragmon")
    670 
    671 **Hint 1**
    672 
    673 If $G$ has an Euler cycle, what can we say about $L^k(G), k\geq1$
    674 
    675 **Hint 2**
    676 
    677 If $L(G)$ has Euler path, how to determine if $L^k(G), k\geq2$ has an Euler path?
    678 
    679 **Hint 3**
    680 
    681 If $L(G)$ doesn't Euler tour, but $L^2(G)$ does, what can we say about structure of $G$? Can there exist another graph $H$ such that $L(H)=G$?
    682 
    683 **Solution**
    684 
    685 Following are the cases where Euler tour is possible:
    686 
    687 For the case of Euler cycle-
    688 
    689 1. If $G$ has an Euler cycle, then $L(G)$ always has an Euler cycle.
    690 2. If after removing the two odd-degree vertices of $G$, the remaining graph is fully disconnected(i.e. the odd-degree vertices form a vertex cover), then $L^2(G)$ has an Euler cycle.
    691 
    692 For the case of Euler path-
    693 
    694 1. If $G$ doesn't have an Euler tour but $L(G)$ does, then there is no graph $H$ such that $G=L^2(H)$, and any of the graph $L^{-k}(H), k\geq0$ has an Euler tour. So, we only need to consider cases where $G$ has an Euler tour, $L(G)$ doesn't, but $L^2(G)$ does, or where both $G$ and $L(G)$ have Euler tour.
    695 2. If $G$ has an Euler path, $L(G)$ doesn't, but $L^2(G)$ does, then $G$ has exactly two odd-degree vertices $v_1$ and $v_2$. Additionally, graph obtained after removing $v_1$ and $v_2$ from $G$(i.e. $G\backslash${$v_1,v_2$}) consists of exactly one connected component with more than one vertex, and the rest are isolated vertices. Additionally, each connected component/isolated vertex in $G\backslash${$v_1,v_2$} has exactly two edges connecting them to $v_1$, $v_2$ in $G$. Here, $L^k(G), k\geq3$ won't have Euler tour.
    696 3. If $G$ has an Euler tour and $L(G)$ also has an Euler tour, find the smallest trailing path of $G$(trailing path means a path where the degree of all vertices is either $1$ or $2$. There will be only $2$ of them as $G$ has an Euler tour) and return its length, and that will be the answer as the length of a trailing path decreases by $1$ from $G$ to $L(G)$.
    697 
    698 All of this can be checked in initial graph itself in $O(n+m)$ time.
    699 
    700 **Code - aryansanghi**
    701 
    702 ```
    703 //Written By Aryan Sanghi
    704  
    705 #include<bits/stdc++.h>
    706  
    707 using namespace std;
    708  
    709 #define ll long long int
    710 #define rep(i, n) for(ll i = 0; i < n;i++)
    711 #define pb push_back
    712 
    713 vector<vector<ll> > v;
    714  
    715 bool EulerCycle(ll k)
    716 {
    717     ll odd = 0, n=v.size();
    718     rep(i, n) if(v[i].size() % 2) odd++;
    719     
    720     
    721     if(odd == 0) return true;// G has all even degree vertices, so it has Euler Cycle
    722  
    723     rep(i, n)
    724     rep(j, v[i].size())
    725     if(v[v[i][j]].size()%2==v[i].size()%2){
    726         // cout<<i+1<<" "<<v[i][j]+1<<"\n";
    727         return false;
    728     }
    729  
    730     if(k>=2) return true;// L^2(G) has all even degree vertices, so it has Euler Cycle
    731  
    732     return false;
    733 }
    734  
    735 int LongestTrailingPath(ll n, ll p){
    736     if(v[n].size()>2) return 0;
    737     rep(i, v[n].size()) if(v[n][i]!=p) return 1+LongestTrailingPath(v[n][i], n);
    738 }
    739  
    740 void MarkVisited(ll n, vector<ll> &visited, vector<vector<ll> > &adj){
    741     visited[n]=1;
    742     rep(i, adj[n].size()){
    743         if(!visited[adj[n][i]]){
    744             MarkVisited(adj[n][i], visited, adj);
    745         }
    746     }
    747 }
    748  
    749 bool EulerPath(ll k){
    750     ll oddv[2], temp=0, n=v.size();
    751     rep(i, n) if(v[i].size()%2) oddv[temp++]=i;
    752     ll l[2]={LongestTrailingPath(oddv[0], -1), LongestTrailingPath(oddv[1], -1)};
    753     if(l[0]>l[1]) swap(l[0], l[1]), swap(oddv[0], oddv[1]);
    754     if(l[0]>=k) return true; // shortest longest trailing path is longer than k
    755     if(l[0]>0) return false; // shortest longest trailing path is non zero and less than k
    756     if(l[1]==1 && v[oddv[0]].size()==3 && v[oddv[1]][0] == oddv[0] && k==1) return true; // odd[0] and odd[1] are connected with one one have degree 1 and other having degree 3
    757     if(find(v[oddv[0]].begin(), v[oddv[0]].end(), oddv[1]) != v[oddv[0]].end()) return false; // odd[0] and odd[1] are adjacent
    758     if(k==1 || k>=3) return false; // Special cases left, and k=1, k>=4 don't satisfy it
    759  
    760     vector<vector<ll> > tempv(v);
    761     vector<ll> vis(v.size(), 0), noniso;
    762  
    763     rep(i, n){
    764         if(find(tempv[i].begin(), tempv[i].end(), oddv[0]) != tempv[i].end()) tempv[i].erase(find(tempv[i].begin(), tempv[i].end(), oddv[0]));
    765         if(find(tempv[i].begin(), tempv[i].end(), oddv[1]) != tempv[i].end()) tempv[i].erase(find(tempv[i].begin(), tempv[i].end(), oddv[1]));
    766         if(tempv[i].size()>0 && i!=oddv[0] && i!=oddv[1]) noniso.pb(i);
    767     }
    768  
    769     MarkVisited(noniso[0], vis, tempv);
    770     rep(i, noniso.size()){
    771         if(!vis[noniso[i]]) return false; // After removing odd degree vertices, there is more than one component
    772     }
    773  
    774     ll cntedge=0;
    775     rep(i, noniso.size()){
    776         int temp=0;
    777         if(find(v[noniso[i]].begin(), v[noniso[i]].end(), oddv[0]) != v[noniso[i]].end()) cntedge++, temp++;
    778         if(find(v[noniso[i]].begin(), v[noniso[i]].end(), oddv[1]) != v[noniso[i]].end()) cntedge++, temp++;
    779  
    780         if(temp && v[noniso[i]].size() > 2) return false; // Vertex connected to odd vertex has degree exactly 2
    781     }
    782     if(cntedge>2) return false; // More than 2 edges are connected to odd degree vertices from the component
    783  
    784     return true; // Special case, k=2 is always satisfied
    785 }
    786  
    787 void solve(){
    788     ll n, m, k;
    789     cin>>n>>m>>k;
    790  
    791     v.clear();
    792     v.resize(n);
    793  
    794     rep(i, m){
    795         ll x, y;
    796         cin>>x>>y;
    797         v[x-1].pb(y-1);
    798         v[y-1].pb(x-1);
    799     }
    800  
    801     if(EulerCycle(k)){
    802         cout<<"YES\n";
    803         return;
    804     }
    805     if(EulerPath(k)){
    806         cout<<"YES\n";
    807         return;
    808     }
    809     cout<<"NO\n";
    810 }
    811  
    812 int main()
    813 {
    814     ll t;
    815     cin>>t;
    816  
    817     while(t--)
    818     {
    819         solve();
    820     }
    821 }
    822 ```
    823 
    824 **Code - ugly2333**
    825 
    826 ```
    827 //��
    828 #include<bits/stdc++.h>
    829 using namespace std;
    830 typedef long long LL;
    831 typedef double DB;
    832 const int N = 222222;
    833 int n,m,k,a[N],b[N],d[N],r[N][2];
    834 vector<int> v[N],c;
    835 LL solve1(){
    836 	int i;
    837 	LL s=0;
    838 	for(i=1;i<=m;i++)
    839 		s+=d[a[i]]%2!=d[b[i]]%2;
    840 	return s;
    841 }
    842 LL solve2(){
    843 	int i;
    844 	LL s=0;
    845 	for(i=1;i<=n;i++)
    846 		s+=(LL)r[i][0]*r[i][1];
    847 	return s;
    848 }
    849 LL solve3(){
    850 	int i,o;
    851 	LL s=0;
    852 	for(i=1;i<=n;i++)
    853 		s+=(LL)r[i][0]*r[i][1]*(d[i]-2);
    854 	for(i=1;i<=m;i++){
    855 		o=(d[a[i]]+d[b[i]])%2;
    856 		s+=(LL)(r[a[i]][0]-(d[b[i]]%2==0))*(r[b[i]][o^1]-(d[a[i]]%2==(o^1)))+(LL)(r[a[i]][1]-(d[b[i]]%2==1))*(r[b[i]][o]-(d[a[i]]%2==o));
    857 	}
    858 	return s;
    859 }
    860 int dfs(int u,int fa=0){
    861 	if(d[u]>=3)
    862 		return 0;
    863 	if(d[u]==1)
    864 		return N;
    865 	int i,x,r=N;
    866 	for(i=0;i<v[u].size();i++){
    867 		x=v[u][i];
    868 		if(x!=fa)
    869 			r=min(r,dfs(x,u)+1);
    870 	}
    871 	return r;
    872 }
    873 int main(){
    874 	int T,i,f;
    875 	LL s,t;
    876 	scanf("%d",&T);
    877 	while(T--){
    878 		scanf("%d%d%d",&n,&m,&k);
    879 		for(i=1;i<=m;i++)
    880 			scanf("%d%d",a+i,b+i);
    881 		for(i=1;i<=m;i++)
    882 			d[a[i]]++,d[b[i]]++;
    883 		for(i=1;i<=m;i++)
    884 			r[a[i]][d[b[i]]%2]++,r[b[i]][d[a[i]]%2]++;
    885 		for(i=1;i<=m;i++)
    886 			v[a[i]].push_back(b[i]),v[b[i]].push_back(a[i]);
    887 		if(k==1)
    888 			f=solve1()<=2;
    889 		if(k==2)
    890 			f=solve2()<=2;
    891 		if(k==3)
    892 			f=solve3()<=2;
    893 		if(k>3){
    894 			s=solve2();
    895 			if(s==0)
    896 				f=1;
    897 			if(s>=4)
    898 				f=0;
    899 			if(s==2){
    900 				t=solve3();
    901 				if(t==0)
    902 					f=1;
    903 				if(t>=4)
    904 					f=0;
    905 				if(t==2){
    906 					c.clear();
    907 					for(i=1;i<=n;i++)
    908 						if(r[i][0]&&r[i][1])
    909 							c.push_back(i);
    910 					if(c.size()!=2)
    911 						f=0;
    912 					else
    913 						f=k<=min(dfs(c[0]),dfs(c[1]))+1;
    914 				}
    915 			}
    916 		}
    917 		if(f)
    918 			printf("YES\n");
    919 		else
    920 			printf("NO\n");
    921 		for(i=1;i<=n;i++)
    922 			d[i]=0,r[i][0]=0,r[i][1]=0,v[i].clear();
    923 	}
    924 	return 0;
    925 }
    926 ```
    927 
    928 The removed problem was supposed to be G in the Div. 1 + Div. 2, the same problem exists and is available [here](https://www.acmicpc.net/problem/7979).
    929 
    930 **Solution**
    931 
    932 Let $s_i$ be the maximum number such that array $[a_1, a_2, ...a_i-1, s_i, a_i+1, .., a_n]$ is valid.
    933 
    934 Lemma 1: There exists at most one index $i$ such that $a_i \ge s_i$.
    935 
    936 Proof 1: Assume there exist two indices $i$ and $j$ such that $a_i \ge s_i$ and $a_j \ge s_j$, say $i \lt j$.
    937 
    938 $a_j \ge s_j \gt = j-1 + a_1 + a_2 + ... + a_{j-1} \Rightarrow a_j \ge j-1 + \sum_{k = 1}^{j-1} a_k \Lleftarrow \text{Eq}_1$
    939 
    940 For an index $i \lt j$, $a_i \ge s_i$ when $a_j \ge s_j \Rightarrow$
    941 
    942 $a[i] \ge a[j] - (j-i) + 1 \Lleftarrow \text{Eq}_2$
    943 
    944 $\text{Eq}_1$ and $\text{Eq}_2 \Rightarrow$
    945 
    946 $a_j + a_i \ge j-1 - (j-i) + 1 + a_j + \sum_{k = 1}^{j-1} a_k \Rightarrow a_i \ge i + \sum_{k = 1}^{j-1} a_k$
    947 
    948 since $i \lt j \Rightarrow$
    949 
    950 $a_i \ge i + a_1 + a_2 + .... + a_i + ... + a_{j-1} \Rightarrow 0 \ge i + a_1 + ... + a_{i-1} + .... + a_j$
    951 
    952 $\text{Contradiction!!}$
    953 
    954 Lemma 2: If $a_i \le s_i$ $\forall$ $i \in [1, n]$, $a$ is valid.
    955 
    956 Proof 2: Backwards induction — let's divide it into two cases.
    957 
    958 Case 1. $a_i \lt s_i$ $\forall$ $i \in [1, n]$. Let $j \gt 0$ be the smallest index such that $a_j \gt 0$ and say $j$-th index car overtakes the one ahead $i.e.,$
    959 
    960 $0 ... a_{j-1}, a_j, a_{j+1} ... a_n \Rightarrow 0 ... a_j-1, a_{j-1}, a_{j+1} ... a_n$ $0 ... s_{j-1}, s_j, s_{j+1} ... s_n \Rightarrow 0 ... s_j-1, \ge s_{j-1} + a_j, s_{j+1} ... s_n$
    961 
    962 * For all $i \lt j-1$ and $i \gt j$, $a_i \lt s_i$ holds as they were unaffected, why?
    963 * At index $j-1$ since $a_j \lt s_j \Rightarrow a[j]-1 \lt s[j]-1$ holds.
    964 * At index $j$ since $a_{j-1} \lt s_{j-1} \Rightarrow a_{j-1} \lt s_{j-1} + a_j$ holds.
    965 
    966 Case 2. Now, for an index $j$ if $a_j = s_j \Rightarrow$ we choose the index $k \gt j$ such that $a_k \gt 0$; if there's no such $k$, we choose $j$. Condition holds similarly, why?
    967 
    968 $\text{Solution}$
    969 
    970 ```
    971 def check(arr, i):
    972     cnt = 0, s = sum(arr[:i - 1]) + i  
    973     for j in range(i + 1, n):
    974         if arr[j] <= cnt:  cnt += 1 
    975         else:  s += arr[j] - cnt↵
    976     return arr[i] <= s↵
    977 ```
    978 
    979 Let $p = [0, a_1, a_1 + a_2, a_1 + a_2 + a_3, .... ]$ and say an index $i$ is critical $\Leftrightarrow$ $i + p[i] \lt a_i$.
    980 
    981 Lemma 3: It is sufficient to check the greatest critical index $i.e.,$ if $i_1, i_2, ..., i_k$ are critical, $check(a, i_k)$ would be enough to determine whether $a$ is valid or not.
    982 
    983 Proof 3: Trivial, if $i_k$ performs $a_{i_k}$ overtakes successfully $\Rightarrow$ overtakes at indices $i \lt i_k$ will be nullified by $a_{i_k}$
    984 
    985 Special thanks to [Proelectro444](/profile/Proelectro444 "Master Proelectro444") for the formal proof.
    986 
    987 $\looparrowright$ Alternate Solution: $O(n \cdot log n)$ data structure optimized $check(a, i_k)$ $\forall$ $k \in [1, n]$.
    988 
    989 **Code O(n) - harshith_04**
    990 
    991 ```
    992 #include <bits/stdc++.h>
    993 using namespace std;
    994 
    995 const int N = 1e6;
    996 int64_t n, a[N], p[N + 1];
    997 
    998 void solve() {
    999     cin >> n;
   1000     for(int i = 0; i < n; i++) cin >> a[i];
   1001 
   1002     for(int i = 1; i <= n; i++) p[i] = p[i - 1] + a[i - 1];
   1003 
   1004     int cti = n - 1;
   1005     for(int i = n - 1; i >= 0; --i) {
   1006         if(i + p[i] < a[i]) {
   1007             cti = i;
   1008             break;
   1009         }
   1010     }
   1011 
   1012     int cnt = 0;
   1013     int64_t s_i = p[cti] + cti;
   1014 
   1015     for (int j = cti + 1; j < n; ++j) {
   1016         if (a[j] <= cnt) ++cnt;
   1017         else s_i += a[j] - cnt;
   1018     }
   1019 
   1020     if (s_i < a[cti]) cout << "No\n";
   1021     else cout << "Yes\n";
   1022 }
   1023 
   1024 int main() {
   1025     ios::sync_with_stdio(false); cin.tie(nullptr);
   1026 
   1027     int t; cin >> t;
   1028 
   1029     while(t--) solve();
   1030     return 0;
   1031 }
   1032 ```
   1033 
   1034 **Code O(n*logn) - IceKnight1093**
   1035 
   1036 ```
   1037 #include "bits/stdc++.h"
   1038 using namespace std;
   1039 using ll = long long int;
   1040 mt19937_64 RNG(chrono::high_resolution_clock::now().time_since_epoch().count());
   1041 
   1042 #include <ext/pb_ds/assoc_container.hpp>
   1043 #include <ext/pb_ds/tree_policy.hpp>
   1044 using namespace __gnu_pbds;
   1045 template<class T>
   1046 using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
   1047 
   1048 struct FT {
   1049     vector<ll> s;
   1050     FT(int n) : s(n) {}
   1051     void update(int pos, ll dif) { // a[pos] += dif↵
   1052         for (; pos < size(s); pos |= pos + 1) s[pos] += dif;
   1053     }
   1054     ll query(int pos) { // sum of values in [0, pos)
   1055         ll res = 0;
   1056         for (; pos > 0; pos &= pos - 1) res += s[pos-1];
   1057         return res;
   1058     }
   1059 };
   1060 
   1061 int main()
   1062 {
   1063     ios::sync_with_stdio(false); cin.tie(0);
   1064 
   1065     map<vector<int>, bool> cache;
   1066     auto brute = [&] (const auto &self, auto v) -> bool {
   1067         if (ranges::max(v) == 0) return true;
   1068         if (cache.find(v) != cache.end()) return cache[v];
   1069  
   1070         for (int i = 1; i < v.size(); ++i) {
   1071             if (v[i] > 0) {
   1072                 auto w = v;
   1073                 --w[i];
   1074                 swap(w[i], w[i-1]);
   1075                 bool res = self(self, w);
   1076  
   1077                 if (res) return cache[v] = true;
   1078             }
   1079         }
   1080         return cache[v] = false;
   1081     };
   1082 
   1083     auto solve = [&] (auto v) {
   1084         int n = size(v);
   1085 
   1086         vector<int> b(n);
   1087         Tree<array<int, 2>> cur;
   1088         for (int i = 0; i < n; ++i) {
   1089             if (v[i] == 0) b[i] = i;
   1090             else {
   1091                 // v[i]-th largest element↵
   1092                 if (cur.size() >= v[i]) {
   1093                     int want = cur.size() - v[i];
   1094                     auto [val, _] = *cur.find_by_order(want);
   1095                     b[i] = val;
   1096                 }
   1097                 else b[i] = -1;
   1098             }
   1099             cur.insert({b[i], i});
   1100         }
   1101 
   1102         vector deactivate(n+1, vector<int>());
   1103         for (int i = 0; i < n; ++i)
   1104             if (b[i] >= 0) deactivate[b[i]].push_back(i);
   1105         
   1106         ll pref = 0;
   1107         for (int i = 0; i < n; ++i) pref += v[i] + 1;
   1108 
   1109         FT fen(n);
   1110         ll suf = 0;
   1111         for (int i = n-1; i >= 0; --i) {
   1112             pref -= v[i] + 1;
   1113             
   1114             ranges::reverse(deactivate[i]);
   1115             for (int x : deactivate[i]) {
   1116                 if (v[x]) {
   1117                     int sub = fen.query(x+1) - fen.query(i+1);
   1118                     sub = x - i - sub;
   1119                     suf -= v[x] - sub;
   1120                     fen.update(x, -1);
   1121                 }
   1122                 suf -= fen.query(n) - fen.query(x);
   1123             }
   1124             ll have = pref + suf;
   1125             if (v[i] > have) return false;
   1126             if (v[i] > 0) {
   1127                 suf += v[i];
   1128                 fen.update(i, 1);
   1129             }
   1130         }
   1131         return true;
   1132     };
   1133 
   1134     int t; cin >> t;
   1135     while (t--) {
   1136         int n; cin >> n;
   1137         vector a(n, 0);
   1138         for (int &x : a) cin >> x;
   1139         
   1140         if (solve(a)) cout << "Yes\n";
   1141         else cout << "No\n";
   1142     }
   1143 }
   1144 ```
   1145 
   1146 **Bonus for those who haven't seen the Solution**
   1147 
   1148 If $a$ is valid, also determine the index of the first overtaker, if multiple are possible, return any one of them.