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.