1777.md (13564B)
1 Source: https://codeforces.com/blog/entry/111729 2 3 We hope you enjoyed the contest!. Thank you for your participation! Do vote under the Feedback section, and feel free to give your review of the problems in the comments. 4 5 --- 6 7 [1777A - Everybody Likes Good Arrays!](/contest/1777/problem/A "Codeforces Round 845 (Div. 2) and ByteRace 2023") 8 9 Idea: [ShivanshJ](/profile/ShivanshJ "Candidate Master ShivanshJ") 10 Preparation: [ShivanshJ](/profile/ShivanshJ "Candidate Master ShivanshJ") 11 Editorialist: [ShivanshJ](/profile/ShivanshJ "Candidate Master ShivanshJ") 12 13 **Hints** 14 15 **Hint 1** 16 17 Try to make the problem simpler. 18 19 **Hint 2** 20 21 Parity? 22 23 **Hint 3** 24 25 Try replacing even numbers with $0$ and odd numbers with $1$ in other words consider all numbers modulo $2$. 26 27 **Hint 4** 28 29 Think harder! It works! 30 31 **Solution** 32 33 Tutorial is loading... 34 35 **Implementation (C++)** 36 37 ``` 38 /* Enjoying CP as always!*/ 39 #include <bits/stdc++.h> 40 using namespace std; 41 #define int long long 42 43 signed main() { 44 ios_base::sync_with_stdio(false); 45 cin.tie(NULL); 46 int t; 47 cin>>t; 48 while(t--) { 49 //Take input 50 int n; 51 cin>>n; 52 int a[n]; 53 for(int i=0;i<n;i++) { 54 cin>>a[i]; 55 } 56 //initialize answer.. 57 int ans=0; 58 for(int i=0;i+1<n;i++) { 59 ans+=(!((a[i]^a[i+1])&1)); 60 /*XOR the two numbers and check 0th bit in the resultant, if it is 1 61 then, numbers are of different parity, otherwise both are of same parity*/ 62 } 63 cout<<ans<<"\n"; 64 } 65 return 0; 66 } 67 ``` 68 69 **Implementation (Python)** 70 71 ``` 72 def main(): 73 T = int(input()) 74 while T > 0: 75 T = T - 1 76 n = int(input()) 77 a = [int(x) for x in input().split()] 78 ans = 0 79 80 for i in range(1, n): 81 ans += 1 - ((a[i] + a[i - 1]) & 1) 82 83 print(ans) 84 85 86 if __name__ == '__main__': 87 main() 88 ``` 89 90 **Feedback** 91 92 * Good problem: 93 * Average problem: 94 * Bad problem: 95 * Did not solve: 96 97 [1777B - Emordnilap](/contest/1777/problem/B "Codeforces Round 845 (Div. 2) and ByteRace 2023") 98 99 Idea: [TimeWarp101](/profile/TimeWarp101 "Candidate Master TimeWarp101") [quantau](/profile/quantau "Expert quantau") 100 Preparation: [TimeWarp101](/profile/TimeWarp101 "Candidate Master TimeWarp101") 101 Editorialist: [TimeWarp101](/profile/TimeWarp101 "Candidate Master TimeWarp101") 102 103 **Hints** 104 105 **Hint 1** 106 107 Will the answer differ for different permutations? 108 109 **Hint 2** 110 111 If you only look at 2 elements, how much will they contribute to the answer? 112 113 **Solution** 114 115 Tutorial is loading... 116 117 **Implementation (C++)** 118 119 ``` 120 #include<bits/stdc++.h> 121 using namespace std; 122 #define int long long 123 signed main() 124 { 125 const int N = 1e5 + 5; 126 const int mod = 1e9 + 7; 127 vector<int> fact(N); 128 fact[0] = 1; 129 for(int i = 1; i < N; i++) 130 { 131 fact[i] = fact[i - 1] * i; 132 fact[i] %= mod; 133 } 134 int t; 135 cin >> t; 136 while(t--) 137 { 138 int n; 139 cin >> n; 140 int ans = n * (n - 1); 141 ans %= mod; 142 ans = (ans * fact[n]) % mod; 143 cout << ans << endl; 144 } 145 return 0; 146 } 147 ``` 148 149 **Implementation (Python)** 150 151 ``` 152 t = int(input()) 153 for _ in range(t): 154 n = int(input()) 155 nf = 1 156 mod = int(1e9 + 7) 157 for i in range(n): 158 nf = nf * (i + 1) 159 nf %= mod 160 ans = n * (n - 1) * nf 161 ans %= mod 162 print(ans) 163 ``` 164 165 **Feedback** 166 167 * Good problem: 168 * Average problem: 169 * Bad problem: 170 * Did not solve: 171 172 [1777C - Quiz Master](/contest/1777/problem/C "Codeforces Round 845 (Div. 2) and ByteRace 2023") 173 174 Idea: [quantau](/profile/quantau "Expert quantau") 175 Preparation: [TimeWarp101](/profile/TimeWarp101 "Candidate Master TimeWarp101") [quantau](/profile/quantau "Expert quantau") 176 Editorialist: [TimeWarp101](/profile/TimeWarp101 "Candidate Master TimeWarp101") 177 178 **Hints** 179 180 **Hint 1** 181 182 Would sorting the array help? 183 184 **Hint 2** 185 186 Would iterating over the factors help? 187 188 **Hint 3** 189 190 If the optimal team has students with maximum smartness $M$ and minimum smartness $m$, would having students with smartness $X$ such that $m \le X \le M$ the answer will not change. 191 192 **Hint 4** 193 194 Two pointers? 195 196 **Solution** 197 198 Tutorial is loading... 199 200 **Implementation (C++)** 201 202 ``` 203 #include <bits/stdc++.h> 204 #define all(v) v.begin(), v.end() 205 #define var(x, y, z) cout << x << " " << y << " " << z << endl; 206 #define ll long long int 207 #define pii pair<ll, ll> 208 #define pb push_back 209 #define ff first 210 #define ss second 211 #define FASTIO \ 212 ios ::sync_with_stdio(0); \ 213 cin.tie(0); \ 214 cout.tie(0); 215 216 using namespace std; 217 218 const ll inf = 1e17; 219 const ll MAXM = 1e5; 220 vector<ll> factors[MAXM + 5]; 221 222 void init() 223 { 224 for (ll i = 1; i <= MAXM; i++) 225 { 226 for (ll j = i; j <= MAXM; j += i) 227 { 228 factors[j].pb(i); 229 } 230 } 231 } 232 233 void solve() 234 { 235 ll n, m; 236 cin >> n >> m; 237 vector<pii> vec; 238 for (ll i = 0; i < n; i++) 239 { 240 ll value; 241 cin >> value; 242 vec.pb({value, i}); 243 } 244 sort(all(vec)); 245 vector<ll> frequency(m + 5, 0); 246 ll curr_count = 0; 247 ll j = 0; 248 ll global_ans = inf; 249 for (ll i = 0; i < n; i++) 250 { 251 for (auto x : factors[vec[i].ff]) 252 { 253 if (x > m) 254 break; 255 if (!frequency[x]++) 256 { 257 curr_count++; 258 } 259 } 260 while (curr_count == m) 261 { 262 ll curr_ans = vec[i].ff - vec[j].ff; 263 if (curr_ans < global_ans) 264 { 265 global_ans = curr_ans; 266 } 267 for (auto x : factors[vec[j].ff]) 268 { 269 if (x > m) 270 break; 271 if (--frequency[x] == 0) 272 { 273 curr_count--; 274 } 275 } 276 j++; 277 } 278 } 279 cout << (global_ans >= inf ? -1 : global_ans) << "\n"; 280 } 281 282 int main() 283 { 284 FASTIO 285 init(); 286 ll t; 287 cin >> t; 288 while (t--) 289 { 290 solve(); 291 } 292 return 0; 293 } 294 ``` 295 296 **Feedback** 297 298 * Good problem: 299 * Average problem: 300 * Bad problem: 301 * Did not solve: 302 303 [1777D - Score of a Tree](/contest/1777/problem/D "Codeforces Round 845 (Div. 2) and ByteRace 2023") 304 305 Idea: [AwakeAnay](/profile/AwakeAnay "International Master AwakeAnay") 306 Preparation: [mayankfrost](/profile/mayankfrost "Candidate Master mayankfrost") [ShivanshJ](/profile/ShivanshJ "Candidate Master ShivanshJ") 307 Editorialist: [AwakeAnay](/profile/AwakeAnay "International Master AwakeAnay") 308 309 **Hints** 310 311 **Hint 1** 312 313 What would be the value of a node at time $t$? 314 315 **Hint 2** 316 317 The value of a node $u$ after time $t$ would be the xor of the initial values of all nodes in the subtree of $u$ which are at a distance $t$ from $u$. 318 319 **Hint 3** 320 321 What is the expected value of xor of $k$ boolean values? 322 323 **Solution** 324 325 Tutorial is loading... 326 327 **Implementation (C++)** 328 329 ``` 330 #include <bits/stdc++.h> 331 using namespace std; 332 333 #define MOD 1000000007 334 335 long long power(long long a, int b) 336 { 337 long long ans = 1; 338 while (b) 339 { 340 if (b & 1) 341 { 342 ans *= a; 343 ans %= MOD; 344 } 345 a *= a; 346 a %= MOD; 347 b >>= 1; 348 } 349 return ans; 350 } 351 352 int DFS(int v, vector<int> edges[], int p, int dep, int ped[]) 353 { 354 int mdep = dep; 355 for (auto it : edges[v]) 356 if (it != p) 357 mdep = max(DFS(it, edges, v, dep + 1, ped), mdep); 358 ped[v] = mdep - dep + 1; 359 return mdep; 360 } 361 362 int main() 363 { 364 ios_base::sync_with_stdio(false); 365 cin.tie(NULL); 366 int T, i, j, n, u, v; 367 cin >> T; 368 while (T--) 369 { 370 cin >> n; 371 vector<int> edges[n]; 372 for (i = 0; i < n - 1; i++) 373 { 374 cin >> u >> v; 375 u--, v--; 376 377 edges[u].push_back(v); 378 edges[v].push_back(u); 379 } 380 381 int ped[n]; 382 DFS(0, edges, 0, 0, ped); 383 384 long long p = power(2, n - 1), ans = 0; 385 for (i = 0; i < n; i++) 386 { 387 ans += p * ped[i] % MOD; 388 ans %= MOD; 389 } 390 cout << ans << "\n"; 391 } 392 } 393 ``` 394 395 **Feedback** 396 397 * Good problem: 398 * Average problem: 399 * Bad problem: 400 * Did not solve: 401 402 [1777E - Edge Reverse](/contest/1777/problem/E "Codeforces Round 845 (Div. 2) and ByteRace 2023") 403 404 Idea: [Crocuta](/profile/Crocuta "Candidate Master Crocuta") 405 Preparation: [mayankfrost](/profile/mayankfrost "Candidate Master mayankfrost") 406 Editorialist: [mayankfrost](/profile/mayankfrost "Candidate Master mayankfrost") 407 408 **Hints** 409 410 **Hint 1** 411 412 If the cost is c, all edges with weight less than or equal to c are reversible. 413 414 **Hint 2** 415 416 If an edge can be reversed, can it be treated as bidirectional? 417 418 **Hint 3** 419 420 Let there exist a set of possible starting nodes. If this set is non empty, the highest node h in the topological ordering of nodes will always be present in the set. Think why. 421 422 **Solution** 423 424 Tutorial is loading... 425 426 **Implementation (C++)** 427 428 ``` 429 #include <bits/stdc++.h> 430 using namespace std; 431 432 // Using Kosa Raju, we guarantee the topmost element (indicated by root) of stack is from the root SCC 433 434 void DFS(int v, bool visited[], int &root, vector<int> edges[]) 435 { 436 visited[v] = true; 437 for (auto it : edges[v]) 438 if (!visited[it]) 439 DFS(it, visited, root, edges); 440 root = v; 441 } 442 443 int cnt(int v, bool visited[], vector<int> edges[]) 444 { 445 int ans = 1; 446 visited[v] = true; 447 for (auto it : edges[v]) 448 if (!visited[it]) 449 ans += cnt(it, visited, edges); 450 return ans; 451 } 452 453 int main() 454 { 455 ios_base::sync_with_stdio(false); 456 cin.tie(NULL); 457 int T; 458 cin >> T; 459 while (T--) 460 { 461 int i, j, n, m, u, v, w; 462 cin >> n >> m; 463 vector<pair<int, int>> og_edges[n]; 464 for (i = 0; i < m; i++) 465 { 466 cin >> u >> v >> w; 467 u--, v--; 468 469 og_edges[u].push_back({v, w}); 470 } 471 472 int l = -1, r = 1e9 + 1, mid; 473 while (r - l > 1) 474 { 475 mid = l + (r - l) / 2; 476 477 vector<int> edges[n]; 478 for (i = 0; i < n; i++) 479 { 480 for (auto it : og_edges[i]) 481 { 482 edges[i].push_back(it.first); 483 if (it.second <= mid) 484 edges[it.first].push_back(i); 485 } 486 } 487 488 bool visited[n] = {}; 489 int root; 490 for (i = 0; i < n; i++) 491 { 492 if (!visited[i]) 493 DFS(i, visited, root, edges); 494 } 495 496 memset(visited, false, sizeof(visited)); 497 498 if (cnt(root, visited, edges) == n) 499 r = mid; 500 else 501 l = mid; 502 } 503 504 if (r == 1e9 + 1) 505 r = -1; 506 cout << r << '\n'; 507 } 508 return 0; 509 } 510 ``` 511 512 **Feedback** 513 514 * Good problem: 515 * Average problem: 516 * Bad problem: 517 * Did not solve: 518 519 [1777F - Comfortably Numb](/contest/1777/problem/F "Codeforces Round 845 (Div. 2) and ByteRace 2023") 520 521 Idea: [Crocuta](/profile/Crocuta "Candidate Master Crocuta") 522 Preparation: [TimeWarp101](/profile/TimeWarp101 "Candidate Master TimeWarp101") 523 Editorialist: [Crocuta](/profile/Crocuta "Candidate Master Crocuta") 524 525 **Hints** 526 527 **Hint 1** 528 529 Can we somehow fix the maximum element ? 530 531 **Hint 2** 532 533 To calculate the answer over all subarrays with the same maximum element, can we use the trie trick for calculating the maximum xor. 534 535 **Solution** 536 537 Tutorial is loading... 538 539 **Implementation (C++)** 540 541 ``` 542 #include <bits/stdc++.h> 543 544 using namespace std; 545 546 struct Trie{ 547 struct Trie *child[2]={0}; 548 }; 549 typedef struct Trie trie; 550 551 void insert(trie *dic, int x) 552 { 553 trie *temp = dic; 554 for(int i=30;i>=0;i--) 555 { 556 int curr = x>>i&1; 557 if(temp->child[curr]) 558 temp = temp->child[curr]; 559 else 560 { 561 temp->child[curr] = new trie; 562 temp = temp->child[curr]; 563 } 564 } 565 } 566 567 int find_greatest(trie *dic, int x) { 568 int res = 0; 569 trie *temp = dic; 570 for(int i=30;i>=0;i--) { 571 int curr = x>>i&1; 572 if(temp->child[curr^1]) { 573 res ^= 1<<i; 574 temp = temp->child[curr^1]; 575 } 576 else { 577 temp = temp->child[curr]; 578 } 579 } 580 return res; 581 } 582 583 int main() { 584 int test_cases; 585 cin >> test_cases; 586 while(test_cases--) 587 { 588 int n; 589 cin>>n; 590 int a[n+1]; 591 for(int i=1;i<=n;i++) { 592 cin>>a[i]; 593 } 594 595 trie *t[n+2]; 596 int prexor[n+1]; 597 prexor[0] = 0; 598 for(int i=1;i<=n;i++) { 599 t[i] = new trie; 600 insert(t[i], prexor[i-1]); 601 prexor[i] = prexor[i-1]^a[i]; 602 } 603 t[n+1] = new trie; 604 insert(t[n+1], prexor[n]); 605 606 pair<int,int> asc[n+1]; 607 for(int i=1;i<=n;i++) { 608 asc[i] = make_pair(a[i],i); 609 } 610 sort(asc+1,asc+n+1); 611 612 int left[n+1], right[n+1]; 613 stack<int> s; 614 for(int i=1;i<=n;i++) { 615 while(!s.empty() && a[i]>=a[s.top()]) 616 s.pop(); 617 if(s.empty()) 618 left[i] = 0; 619 else 620 left[i] = s.top(); 621 s.push(i); 622 } 623 while(!s.empty()) 624 s.pop(); 625 for(int i=n;i>0;i--) { 626 while(!s.empty() && a[i]>a[s.top()]) 627 s.pop(); 628 if(s.empty()) 629 right[i] = n+1; 630 else 631 right[i] = s.top(); 632 s.push(i); 633 } 634 635 int ans = 0; 636 for(int i=1;i<=n;i++) { 637 int x = asc[i].second; 638 int r = right[x]-1; 639 int l = left[x]+1; 640 if(x-l < r-x) { 641 for(int j=l-1;j<x;j++) { 642 ans = max(ans, find_greatest(t[x+1], prexor[j]^a[x])); 643 } 644 t[l] = t[x+1]; 645 for(int j=l-1;j<x;j++) { 646 insert(t[l], prexor[j]); 647 } 648 } 649 else { 650 for(int j=x;j<=r;j++) { 651 ans = max(ans, find_greatest(t[l], prexor[j]^a[x])); 652 } 653 for(int j=x;j<=r;j++) { 654 insert(t[l], prexor[j]); 655 } 656 } 657 } 658 cout<<ans << endl; 659 } 660 } 661 ``` 662 663 **Feedback** 664 665 * Good problem: 666 * Average problem: 667 * Bad problem: 668 * Did not solve: