1659.md (15947B)
1 Source: https://codeforces.com/blog/entry/100938 2 3 Thank you everyone 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 [1659A - Red Versus Blue](/contest/1659/problem/A "Codeforces Round 782 (Div. 2)") 8 9 Idea: [TimeWarp101](/profile/TimeWarp101 "Expert TimeWarp101") 10 Editorial: [TimeWarp101](/profile/TimeWarp101 "Expert TimeWarp101") 11 12 **Hints** 13 14 **Hint 1** 15 16 Is it a good idea to have consecutive `B`'s? 17 18 **Hint 2** 19 20 If you space out all the `B`'s, how many regions do you have to place the `R`'s into? 21 22 **Hint 3** 23 24 What is the best way of placing the `R`'s into $b+1$ regions such that the maximum number of `R`'s in a region is minimum? 25 26 **Solution** 27 28 Tutorial is loading... 29 30 **Implementation (C++)** 31 32 ``` 33 #include<bits/stdc++.h> 34 using namespace std; 35 using lol=long long int; 36 #define endl "\n" 37 38 int main() 39 { 40 ios_base::sync_with_stdio(false); 41 cin.tie(NULL); 42 int _=1; 43 cin>>_; 44 while(_--) 45 { 46 int n,r,b; 47 cin>>n>>r>>b; 48 int p=r/(b+1),q=r%(b+1); 49 for(int i=0;i<q;i++) cout<<string(p+1,'R')<<'B'; 50 for(int i=q;i<b;i++) cout<<string(p,'R')<<'B'; 51 cout<<string(p,'R'); 52 cout<<endl; 53 } 54 return 0; 55 } 56 ``` 57 58 **Implementation (Python)** 59 60 ``` 61 t = int(input()) 62 for i in range(t): 63 n, r, b = map(int, input().split()) 64 p = r % (b + 1) 65 y = "" 66 for j in range(int(r / (b + 1))): 67 y = y + "R" 68 ans = "" 69 for i in range(b + 1): 70 if i > 0: 71 ans = ans + "B" 72 ans = ans + y 73 if p > 0: 74 ans = ans + "R" 75 p = p - 1 76 print(ans) 77 ``` 78 79 **Feedback** 80 81 * Good problem: 82 * Average problem: 83 * Bad problem: 84 * Did not solve: 85 86 [1659B - Bit Flipping](/contest/1659/problem/B "Codeforces Round 782 (Div. 2)") 87 88 Idea: [Newtech66](/profile/Newtech66 "Expert Newtech66") 89 Editorial: [Newtech66](/profile/Newtech66 "Expert Newtech66") 90 91 **Hints** 92 93 **Hint 1** 94 95 Let's say you don't ever pick a bit. How many times will it get flipped? 96 97 **Hint 2** 98 99 If you do pick a bit once at some point, it will get flipped $1$ less time overall. 100 101 **Hint 3** 102 103 To get the lexicographically largest string, you need to make bits $1$ starting from the left. What is the minimum number of times you have to select a bit to ensure it gets flipped, or stays the same? 104 105 **Solution** 106 107 Tutorial is loading... 108 109 **Implementation (C++)** 110 111 ``` 112 #include<bits/stdc++.h> 113 using namespace std; 114 using lol=long long int; 115 #define endl "\n" 116 117 int main() 118 { 119 ios_base::sync_with_stdio(false); 120 cin.tie(NULL); 121 int _=1; 122 cin>>_; 123 while(_--) 124 { 125 int n,k; 126 cin>>n>>k; 127 string s; 128 cin>>s; 129 vector<int> f(n,0); 130 int tmpk=k; 131 for(int i=0;i<n && tmpk>0;i++) 132 { 133 if(k%2==s[i]-'0') 134 { 135 f[i]=1; 136 tmpk--; 137 } 138 } 139 f[n-1]+=tmpk; 140 for(int i=0;i<n;i++) 141 { 142 if((k-f[i])%2==1) s[i]='1'-(s[i]-'0'); 143 } 144 cout<<s<<endl; 145 for(auto& e:f) cout<<e<<" "; 146 cout<<endl; 147 } 148 return 0; 149 } 150 ``` 151 152 **Implementation (Python)** 153 154 ``` 155 t = int(input()) 156 for i in range(t): 157 n, k = map(int, input().split()) 158 kc = k 159 s = input() 160 f = [0] * n 161 ans = "" 162 for i in range(n): 163 if k == 0: 164 break 165 if kc % 2 == 1 and s[i] == '1': 166 f[i] = f[i] + 1 167 k = k - 1 168 elif kc % 2 == 0 and s[i] == '0': 169 f[i] = f[i] + 1 170 k = k - 1 171 f[n - 1] = f[n - 1] + k 172 for i in range(n): 173 flip = kc - f[i] 174 if flip % 2 == 0: 175 ans = ans + s[i] 176 else: 177 if s[i] == '1': 178 ans = ans + '0' 179 else: 180 ans = ans + '1' 181 print(ans) 182 for i in range(n): 183 print(f[i], end = ' ') 184 print() 185 ``` 186 187 **Feedback** 188 189 * Good problem: 190 * Average problem: 191 * Bad problem: 192 * Did not solve: 193 194 [1659C - Line Empire](/contest/1659/problem/C "Codeforces Round 782 (Div. 2)") 195 196 Idea: [Newtech66](/profile/Newtech66 "Expert Newtech66") 197 Editorial: [Newtech66](/profile/Newtech66 "Expert Newtech66") 198 199 **Hints** 200 201 **Hint 1** 202 203 Try to analyze the cost of each operation separately. Is there some linearity you can exploit? 204 205 **Hint 2** 206 207 Try to make greedy decisions. Can we say that it is always better to move right whenever possible? 208 209 **Hint 3** 210 211 Let's say you fix the final position of your capital. Now think about Hint 2. 212 213 **Solution** 214 215 Tutorial is loading... 216 217 **Implementation (C++)** 218 219 ``` 220 #include<bits/stdc++.h> 221 using namespace std; 222 using lol=long long int; 223 #define endl "\n" 224 const lol inf=1e18+8; 225 226 int main() 227 { 228 ios_base::sync_with_stdio(false); 229 cin.tie(NULL); 230 int _=1; 231 cin>>_; 232 while(_--) 233 { 234 int n; 235 lol a,b; 236 cin>>n>>a>>b; 237 vector<lol> x(n+1),p(n+1); 238 x[0]=0; 239 for(int i=1;i<=n;i++) cin>>x[i]; 240 partial_sum(x.begin(),x.end(),p.begin()); 241 lol ans=inf; 242 for(int i=0;i<=n;i++) 243 { 244 ans=min(ans,(a+b)*(x[i]-x[0])+b*(p[n]-p[i]-(n-i)*x[i])); 245 } 246 cout<<ans<<endl; 247 } 248 return 0; 249 } 250 ``` 251 252 **Feedback** 253 254 * Good problem: 255 * Average problem: 256 * Bad problem: 257 * Did not solve: 258 259 [1659D - Reverse Sort Sum](/contest/1659/problem/D "Codeforces Round 782 (Div. 2)") 260 261 Idea: [Newtech66](/profile/Newtech66 "Expert Newtech66") 262 Editorial: [Newtech66](/profile/Newtech66 "Expert Newtech66") 263 264 **Hints** 265 266 **Hint 1** 267 268 Is there any way to tell how many $1$s were in $A$? 269 270 **Hint 2** 271 272 Can you tell what $a_n$ was by looking at just $c_n$? 273 274 **Hint 3** 275 276 Try to simulate removing each $B_i$ starting from $B_n$. 277 278 **Solution** 279 280 Tutorial is loading... 281 282 **Implementation (C++)** 283 284 ``` 285 #include<bits/stdc++.h> 286 using namespace std; 287 using lol=long long int; 288 #define endl "\n" 289 290 int main() 291 { 292 ios_base::sync_with_stdio(false); 293 cin.tie(NULL); 294 int _=1; 295 cin>>_; 296 while(_--) 297 { 298 int n; 299 cin>>n; 300 vector<lol> v(n); 301 for(auto& e:v) cin>>e; 302 int k=accumulate(v.begin(),v.end(),0ll)/n; 303 vector<int> b(n),ans(n,0); 304 int lf=n-k; 305 for(int i=lf;i<n;i++) b[i]=n-1; 306 for(int i=n-1;i>=0 && lf<=i;i--) 307 { 308 int cur=v[i]-(b[i]-i); 309 if(cur==i+1) ans[i]=1; 310 else if(cur==1) 311 { 312 ans[i]=0; 313 lf--; 314 b[lf]=i-1; 315 } 316 } 317 for(auto& e:ans) cout<<e<<" "; 318 cout<<endl; 319 } 320 return 0; 321 } 322 ``` 323 324 **Feedback** 325 326 * Good problem: 327 * Average problem: 328 * Bad problem: 329 * Did not solve: 330 331 **Challenge** 332 333 Try to solve this problem if it is possible for invalid $C$ to be given as input. This was the original version of the problem, but testers struggled a lot with it. The solution to this is still used in the validator. 334 335 [1659E - AND-MEX Walk](/contest/1659/problem/E "Codeforces Round 782 (Div. 2)") 336 337 Idea: [Newtech66](/profile/Newtech66 "Expert Newtech66") 338 Editorial: [TimeWarp101](/profile/TimeWarp101 "Expert TimeWarp101") 339 340 **Hints** 341 342 **Hint 1** 343 344 Can the MEX ever be $ \gt 2$? 345 346 **Hint 2** 347 348 For the MEX to be $0$, the AND of the walk should be $ \gt 0$. This implies that some bit is on for all the edges of the walk. How can you check this efficiently? 349 350 **Hint 3** 351 352 Make $30$ graphs, with each graph only containing edges where the $i$-th bit is on. You can use disjoint sets on these graphs to solve the above problem. 353 354 **Hint 4** 355 356 When MEX is $1$, we know $0$ exists in the sequence. We need to avoid $1$ and jump from some other number to $0$. We need to get rid of the $0$-th bit while some other bit stays on to ensure we don't get $1$ in our sequence. This basically means that we need to walk to a node which has an even edge and ensure our AND so far is $ \gt 1$. Travelling through the even edge would guarantee that our answer is $1$. 357 358 **Hint 5** 359 360 Again, make $29$ graphs, with each graph only containing edges where the $0$-th and $i$-th ($i\geq 1$) bits are on. Use disjoint sets on these graphs. For each vertex you can note if it is adjacent to an even edge and then store this information in the disjoint set data structure. 361 362 **Solution** 363 364 Tutorial is loading... 365 366 **Implementation (C++)** 367 368 ``` 369 #pragma GCC optimize("Ofast") 370 #pragma GCC optimize("unroll-loops") 371 #pragma GCC target("avx,avx2,fma") 372 373 #include <bits/stdc++.h> 374 #include <ext/pb_ds/assoc_container.hpp> 375 #include <ext/pb_ds/trie_policy.hpp> 376 #include <ext/rope> 377 378 using namespace std; 379 using namespace __gnu_pbds; 380 using namespace __gnu_cxx; 381 382 mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); 383 384 #define fi first 385 #define se second 386 #define pb push_back 387 #define eb emplace_back 388 #define mp make_pair 389 #define gcd __gcd 390 #define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0) 391 #define rep(i, n) for (int i=0; i<(n); i++) 392 #define rep1(i, n) for (int i=1; i<=(n); i++) 393 #define all(x) (x).begin(), (x).end() 394 #define rall(x) (x).rbegin(), (x).rend() 395 #define endl "\n" 396 397 typedef long long ll; 398 typedef unsigned long long ull; 399 typedef unsigned uint; 400 typedef long double ld; 401 typedef pair<int, int> pii; 402 typedef pair<ll, ll> pll; 403 typedef vector<int> vi; 404 typedef vector<vector<int>> vvi; 405 typedef vector<ll> vll; 406 typedef vector<vector<ll>> vvll; 407 typedef vector<bool> vb; 408 typedef vector<vector<bool>> vvb; 409 template<typename T, typename cmp = less<T>> 410 using ordered_set=tree<T, null_type, cmp, rb_tree_tag, tree_order_statistics_node_update>; 411 typedef trie<string, null_type, trie_string_access_traits<>, pat_trie_tag, trie_prefix_search_node_update> pref_trie; 412 413 struct dsu { 414 vi d; 415 dsu(int n) : d(n, -1) {} 416 int find(int x) {return d[x] < 0 ? x : d[x] = find(d[x]);} 417 void join(int x, int y) { 418 x = find(x), y = find(y); 419 if(x == y) return; 420 if(d[x] > d[y]) swap(x, y); 421 d[x] += d[y]; d[y] = x; 422 } 423 bool is_joined(int x, int y) { 424 return find(x) == find(y); 425 } 426 }; 427 428 int32_t main() { 429 fastio; 430 int n, m; cin >> n >> m; 431 vector<tuple<int, int, int>> edges; 432 rep(i, m) { 433 int u, v, w; cin >> u >> v >> w; 434 edges.eb(--u, --v, w); 435 } 436 vector<dsu> zero(30, n), one(30, n); 437 rep(j, 30) { 438 for(auto& [u, v, w]: edges) if(w >> j & 1) { 439 zero[j].join(u, v); 440 } 441 } 442 vb even(n); 443 rep1(j, 29) { 444 for(auto& [u, v, w]: edges) if((w >> j & 1)) { 445 one[j].join(u, v); 446 } 447 vb vis(n); 448 for(auto& [u, v, w]: edges) if(!(w & 1)) { 449 vis[one[j].find(u)] = 1; 450 vis[one[j].find(v)] = 1; 451 } 452 rep(i, n) if(vis[one[j].find(i)]) even[i] = 1; 453 } 454 auto check = [&](int u, int v) -> int { 455 rep(j, 30) if(zero[j].is_joined(u, v)) return 0; 456 if(even[u]) return 1; 457 rep1(j, 29) if(one[j].is_joined(u, v)) return 1; 458 return 2; 459 }; 460 int q; cin >> q; 461 while(q--) { 462 int u, v; cin >> u >> v; --u, --v; 463 cout << check(u, v) << endl; 464 } 465 } 466 ``` 467 468 **Feedback** 469 470 * Good problem: 471 * Average problem: 472 * Bad problem: 473 * Did not solve: 474 475 **Challenge** 476 477 Try to solve this problem if the queries were for **longest** walk instead. 478 479 [1659F - Tree and Permutation Game](/contest/1659/problem/F "Codeforces Round 782 (Div. 2)") 480 481 Idea: [Newtech66](/profile/Newtech66 "Expert Newtech66") 482 Editorial: [Newtech66](/profile/Newtech66 "Expert Newtech66") 483 484 [Bench0310](/profile/Bench0310 "Grandmaster Bench0310") has written another proof for the solution to this problem [here](https://codeforces.com/blog/entry/101560?#comment-904422) and [here](https://codeforces.com/blog/entry/101560?#comment-904443). Many thanks to him! 485 486 **Hints** 487 488 **Hint 1** 489 490 Notice that as long as there are $\geq 3$ elements not in their correct place, Alice can always put at least $1$ element into the correct place. 491 492 **Hint 2** 493 494 Intuitively, Alice should win if the tree is "big enough", because Bob won't be able to reach some places quickly enough. How to define this sense of "big enough"? 495 496 **Hint 3** 497 498 Try to solve this problem on a line graph. 499 500 **Hint 4** 501 502 It is actually possible to force a sequence of moves to get the $2$ remaining elements onto the diameter of the tree. Given this, use the answer to Hint 3. 503 504 **Hint 5** 505 506 Prove that Alice always wins on trees with diameter $\geq 3$. 507 508 **Hint 6** 509 510 A tree of diameter $2$ is a star graph. This case has a number of edge cases. This time, try to look at permutation cycles. Can you define some kind of invariant? 511 512 **Solution** 513 514 Tutorial is loading... 515 516 **Implementation (C++)** 517 518 ``` 519 #include<bits/stdc++.h> 520 using namespace std; 521 using lol=long long int; 522 #define endl "\n" 523 524 pair<int,int> dfs(int u,const vector<vector<int>>& g,int p=-1) //returns {node with max dist,max dist} 525 { 526 pair<int,int> res{u,0}; 527 int mx=0; 528 for(auto v:g[u]) 529 { 530 if(v==p) continue; 531 pair<int,int> cur=dfs(v,g,u); 532 cur.second++; 533 if(mx<cur.second) 534 { 535 res=cur; 536 mx=cur.second; 537 } 538 } 539 return res; 540 } 541 542 int main() 543 { 544 ios_base::sync_with_stdio(false); 545 cin.tie(NULL); 546 int _=1; 547 cin>>_; 548 while(_--) 549 { 550 int n,x; 551 cin>>n>>x; 552 vector<vector<int>> g(n+1); 553 vector<int> p(n+1),deg(n+1,0); 554 for(int i=1;i<n;i++) 555 { 556 int u,v; 557 cin>>u>>v; 558 g[u].push_back(v); 559 g[v].push_back(u); 560 deg[u]++,deg[v]++; 561 } 562 for(int i=1;i<=n;i++) 563 { 564 cin>>p[i]; 565 } 566 //find diameter of tree with 2 DFSes 567 int diam=dfs(dfs(1,g).first,g).second; 568 //if diam>=3, Alice always wins 569 //if diam=1, n=2, have to check if p=[1,2] 570 //otherwise we have a star graph and cases follow 571 if(diam>=3) cout<<"Alice"; 572 else if(diam==1) cout<<((p[1]==1)?"Alice":"Bob"); 573 else 574 { 575 //we need to check if we have already won or can win in the first move 576 //this is possible if the permutation is already sorted 577 //or if there are two marked elements and the chip is on neither of them 578 vector<int> marked; 579 for(int i=1;i<=n;i++) 580 { 581 if(p[i]!=i) marked.push_back(i); 582 } 583 if((int)marked.size()==0) 584 { 585 cout<<"Alice"; 586 }else if((int)marked.size()==2 && (x!=marked[0] && x!=marked[1])) 587 { 588 cout<<"Alice"; 589 }else 590 { 591 //we haven't won yet and it is not possible to win in one move 592 //cases follow 593 //first find center, it will have deg>1 594 int center; 595 for(int i=1;i<=n;i++) 596 { 597 if(deg[i]>1) 598 { 599 center=i; 600 break; 601 } 602 } 603 //is chip on center? 604 bool chiponcenter=(x==center); 605 //is center marked? 606 bool centerismarked=(find(marked.begin(),marked.end(),x)!=marked.end()); 607 //list the cycles 608 vector<int> vis(n+1,false); 609 vector<vector<int> > cycles; 610 for(int i=1;i<=n;i++) 611 { 612 if(vis[i]) continue; 613 int j=i; 614 cycles.push_back({j}); 615 vis[j]=true; 616 while(!vis[p[j]]) 617 { 618 cycles.back().push_back(p[j]); 619 vis[p[j]]=true; 620 j=p[j]; 621 } 622 } 623 //min number of swaps 624 int swapcnt=0; 625 for(auto& cycle:cycles) swapcnt+=(int)cycle.size()-1; 626 //parity 627 int parity=(swapcnt+!chiponcenter)%2; 628 //cases 629 if(!centerismarked) cout<<(parity?"Alice":"Bob"); 630 else if(chiponcenter && centerismarked) cout<<"Bob"; 631 else //chip not on center and center is marked 632 { 633 //need to check if we can unmark center on first move 634 //it is impossible if x is on p[center] (since we need to move p[center] to get center 635 //to the right place, but p[center] is blocked) 636 bool cannotunmarkcenter=(p[center]==x); 637 if(cannotunmarkcenter) cout<<"Bob"; 638 else cout<<(parity?"Alice":"Bob"); 639 } 640 } 641 } 642 cout<<endl; 643 } 644 return 0; 645 } 646 ``` 647 648 **Feedback** 649 650 * Good problem: 651 * Average problem: 652 * Bad problem: 653 * Did not solve: