1369.md (14164B)
1 Source: https://codeforces.com/blog/entry/79235 2 3 #### [A. FashionabLee :](https://codeforces.com/contest/1369/problem/A) 4 5 Invented by [DeadlyCritic](/profile/DeadlyCritic "Master DeadlyCritic"). 6 7 **Brief Solution** 8 9 $\mathcal Brief\;\mathcal Solution :$ 10 11 A $n$-regular convex polygon is beautiful if and only if $n \% 4 = 0$. ($\%$ is the modular arithmetic symbol) 12 13 **Complete Proof** 14 15 Tutorial is loading... 16 17 **Python solution** 18 19 ``` 20 t = int(input()) 21 for testcase in range(t): 22 n = int(input()) 23 if(n%4 == 0) : 24 print("Yes") 25 else : 26 print("No") 27 ``` 28 29 **C++ solution** 30 31 ``` 32 #include <iostream> 33 34 using namespace std; 35 36 int main(){ 37 int t; 38 cin >> t; 39 while(t--){ 40 int n; 41 cin >> n; 42 if(n % 4 == 0){ 43 cout << "YES\n"; 44 } 45 else cout << "NO\n"; 46 } 47 } 48 ``` 49 50 #### [B. AccurateLee :](https://codeforces.com/contest/1369/problem/B) 51 52 Invented by [DeadlyCritic](/profile/DeadlyCritic "Master DeadlyCritic"). 53 54 **Brief Solution** 55 56 $\mathcal Brief\;\mathcal Solution :$ 57 58 If the string $s$ is non-decreasing, then the answer is $s$ itself, otherwise the answer is $x+1$ zeroes and $y$ ones, where $x$ is the number of leading zeroes of the string $s$, and $y$ is the number of trailing ones of the string $s$. 59 60 **Complete Proof** 61 62 Tutorial is loading... 63 64 **Python solution** 65 66 ``` 67 t = int(input()) 68 for testcase in range(t): 69 n = int(input()) 70 s = input() 71 lef, rig, sw = 1, 1, 0 72 for i in range(n-1): 73 if(s[i] > s[i+1]): 74 sw = 1 75 break 76 if(sw == 0): 77 print(s) 78 continue 79 for i in range(n): 80 if (s[i] == '1'): 81 lef = i 82 break 83 for i in range(n-1, 0, -1): 84 if (s[i] == '0'): 85 rig = i 86 break 87 st = s[:lef] + '0' + s[rig+1:] 88 print(st) 89 ``` 90 91 **C++ solution** 92 93 ``` 94 #include <iostream> 95 #include <string> 96 97 using namespace std; 98 99 int main(){ 100 101 int t; 102 cin >> t; 103 while(t--){ 104 int n; 105 cin >> n; 106 string s; 107 cin >> s; 108 int sw = 1; 109 for(int i = 1; i < s.size(); i++){ 110 if(s[i] < s[i-1])sw = 0; 111 } 112 if(sw){ 113 cout << s << '\n'; 114 continue; 115 } 116 string ans; 117 for(int i = 0; i < s.size(); i++){ 118 if(s[i] == '1')break; 119 ans.push_back('0'); 120 } 121 ans.push_back('0'); 122 for(int i = s.size()-1; i >= 0; i--){ 123 if(s[i] == '0')break; 124 ans.push_back('1'); 125 } 126 cout << ans << '\n'; 127 } 128 } 129 ``` 130 131 #### [C. RationalLee :](https://codeforces.com/contest/1369/problem/C) 132 133 Invented by [DeadlyCritic](/profile/DeadlyCritic "Master DeadlyCritic") and [adedalic](/profile/adedalic "International Master adedalic"). 134 135 **Brief Solution** 136 137 $\mathcal Brief\; \mathcal Solution$ : 138 139 Give greatest elements to friends with $w_i = 1$. For the rest sort the elements in non-descending order of $a_i$ and sort the friends in non-ascending order of $w_i$ then give first $w_1-1$ elements to friend $1$, next $w_2-1$ elements to friend $2$ and so on, also give $k-i+1$-th greatest element to friend $i$ $(1 \le i \le k)$. 140 141 **Complete Proof** 142 143 Tutorial is loading... 144 145 **Python solution** 146 147 ``` 148 t = int(input()) 149 for tc in range(t): 150 n, k = map(int, input().split()) 151 a = list(map(int, input().split())) 152 w = list(map(int, input().split())) 153 a.sort(reverse = True) 154 w.sort() 155 ii, l, r = k, 0, n-1 156 ans = 0 157 for i in range(k): 158 if(w[i] > 1): 159 ii = i 160 break 161 ans = ans+a[l]*2 162 l = l+1 163 for u in range(k-1, ii-1, -1): 164 i = w[u] 165 ans = ans + a[l] + a[r] 166 r = r-i+1 167 l = l+1 168 print(ans) 169 ``` 170 171 **C++ solution** 172 173 ``` 174 #include <bits/stdc++.h> 175 #define ll long long 176 #define fr first 177 #define sc second 178 #define int ll 179 180 using namespace std; 181 const int MN = 2e5+7; 182 183 vector<int> v[MN]; 184 185 signed main(){ 186 ios::sync_with_stdio(false); 187 cin.tie(); 188 cout.tie(); 189 190 int t; 191 cin >> t; 192 while(t--){ 193 int n, k; 194 cin >> n >> k; 195 for(int i = 0; i <= n; i++)v[i].clear(); 196 ll a[n], w[k]; 197 for(int i = 0; i < n; i++){ 198 cin >> a[i]; 199 } 200 for(int i = 0; i < k; i++){ 201 cin >> w[i]; 202 } 203 sort(w, w+k); 204 sort(a, a+n); 205 for(int i = 0; i < k/2; i++)swap(w[i], w[k-i-1]); 206 int po = 0; 207 for(int i = 0; i < n-k; i++){ 208 while(w[po] == v[po].size()+1)po++; 209 v[po].push_back(a[i]); 210 } 211 ll ans = 0; 212 int qf = 1; 213 for(int i = 0; i < k; i++){ 214 ans += a[n-i-1]; 215 if(v[i].size())ans += v[i][0]; 216 else ans += a[n-qf], qf++; 217 } 218 219 cout << ans << '\n'; 220 } 221 } 222 ``` 223 224 #### [D. TediousLee :](https://codeforces.com/contest/1369/problem/D) 225 226 Invented by [DeadlyCritic](/profile/DeadlyCritic "Master DeadlyCritic"). 227 228 **Brief Solution** 229 230 $\mathcal Brief \mathcal Solution$ : 231 232 Realize that a RDB of level $i$ is consisted of a vertex (the root of the RDB of level $i$) connected to the roots of two RDBs of level $i-2$ and a RDB of level $i-1$. 233 234 Run a DP and calculate the answer for each level $i$ ($ 3 \le i \le 2 \cdot 10^6$), then $dp_i = 2 \cdot dp_{i-2} + dp_{i-1} + (i \% 3 == 0?4:0)$. 235 236 **Complete Proof** 237 238 Tutorial is loading... 239 240 **Python solution** 241 242 ``` 243 v = [] 244 v.append(0) 245 v.append(0) 246 v.append(0) 247 v.append(4) 248 v.append(4) 249 mod = int(1e9+7) 250 for i in range (5, 2000010): 251 v.append(max(((2*v[i-2])+v[i-1])%mod,((4*v[i-4])+4*v[i-3]+v[i-2]+4)%mod)) 252 t = int(input()) 253 for _ in range(t): 254 print(v[int(input())]) 255 ``` 256 257 **C++ solution** 258 259 ``` 260 #include <bits/stdc++.h> 261 #define ll long long 262 using namespace std; 263 264 const int mod = int(1e9+7); 265 const int MN = int(2e6+7); 266 267 int dp[MN]; 268 269 signed main(){ 270 ios::sync_with_stdio(false); 271 cin.tie(); 272 cout.tie(); 273 dp[0] = dp[1] = 0; 274 dp[2] = 4; 275 for(int i = 3; i < MN; i++){ 276 long long w = dp[i-1]; 277 w += 2*dp[i-2] + (i % 3 == 2)*4; 278 w %= mod; 279 dp[i] = w; 280 } 281 282 int t; 283 cin >> t; 284 while(t--){ 285 int n; 286 cin >> n; 287 n--; 288 cout << dp[n]%mod << '\n'; 289 } 290 } 291 ``` 292 293 Challenge : Try solving problem D for $n \le 10^{18}$. (no matrix-multiplication) 294 295 #### [E. DeadLee :](https://codeforces.com/contest/1369/problem/E) 296 297 Invented by [DeadlyCritic](/profile/DeadlyCritic "Master DeadlyCritic"). 298 299 **Hints** 300 301 $\mathcal Hints$ : 302 303 1. Find some greedy approaches. Its guessable that the problem is greedy. 304 2. Define $s_i$ for food $i$ equal to the number of guys who likes food $i$. Then find some condition which is enough to be sure that no answer exist. 305 3. See the last friend in a suitable permutation. What food will he eat? 306 4. Its easy to see that if $\forall 1 \le i \le m \Rightarrow s_i \gt w_i$, then no answer exist. 307 5. If a food $i$ exist such that $s_i \le w_i$, then what will happen to the friends who like this food? They can always eat this food no matter what happens, so lets call them as late as possible(so its less likely for them to eat more than one plate). Now continue the process with rest of the friends and foods. 308 309 **Brief Solution** 310 311 $\mathcal Brief\;\mathcal Solution$ : 312 313 Define $s_i$ equal to the number of friends who likes food $i$. If for some $i$, $s_i \le w_i$ then place all the friends who likes food $i$ in the end of the permutation and erase them and continue doing the same thing for the rest of the friends and foods 314 315 It's easy to see that if the set of friends became empty then the permutation we constructed is suitable(and no one would eat Lee), otherwise Lee has to buy more food!! 316 317 **Complete Proof** 318 319 Tutorial is loading... 320 321 **Python solution** 322 323 ``` 324 import sys 325 import heapq 326 327 inputarray = [int(x) for x in sys.stdin.read().split()] 328 329 n, m = inputarray[0], inputarray[1] 330 331 s, w = [], [] 332 for i in range(2, n+2): 333 w.append(inputarray[i]) 334 335 g, eg, foodm, friendm, x, y = [], [], [], [], [], [] 336 337 for i in range(n): 338 s.append(0) 339 foodm.append(0) 340 g.append([]) 341 342 for i in range(m): 343 friendm.append(0) 344 x.append(0) 345 y.append(0) 346 347 inppo = n+2 348 for i in range(m): 349 x[i], y[i] = inputarray[inppo], inputarray[inppo+1] 350 inppo = inppo+2 351 x[i] = x[i]-1 352 y[i] = y[i]-1 353 u = x[i] 354 v = y[i] 355 s[u] = s[u]+1 356 s[v] = s[v]+1 357 g[u].append(i) 358 g[v].append(i) 359 eg.append((v, u)) 360 361 myq = [] 362 363 ans = [] 364 365 for i in range(n): 366 heapq.heappush(myq, (-w[i]+s[i], i)) 367 368 while len(myq): 369 u = myq[0] 370 heapq.heappop(myq) 371 if u[0] != -w[u[1]]+s[u[1]]: 372 continue 373 if(u[0] > 0): 374 print("DEAD") 375 sys.exit() 376 foodm[u[1]] = 1 377 sw = 1 378 for i in g[u[1]]: 379 if friendm[i] == 0: 380 friendm[i] = 1 381 if y[i] == u[1]: 382 x[i], y[i] = y[i], x[i] 383 s[x[i]] = s[x[i]]-1 384 s[y[i]] = s[y[i]]-1 385 heapq.heappush(myq, (-w[y[i]]+s[y[i]], y[i])) 386 ans.append(i) 387 if(len(ans) == m): 388 sw = 0 389 break; 390 if(sw == 0): 391 break 392 print("ALIVE") 393 for i in ans[::-1]: 394 print(i+1, end=" ") 395 ``` 396 397 **C++ solution** 398 399 ``` 400 #include <bits/stdc++.h> 401 402 #define ll long long 403 #define fr first 404 #define sc second 405 #define pii pair<int, int> 406 #define all(v) v.begin(), v.end() 407 408 using namespace std; 409 const int MN = 2e5+7; 410 411 int x[MN], y[MN], s[MN], w[MN], mark[MN], colmark[MN]; 412 413 vector<int> v[MN], a; 414 vector<pii> f; 415 416 priority_queue<pii, vector<pii>, greater<pii>> pq; 417 418 signed main(){ 419 ios::sync_with_stdio(false); 420 cin.tie(); 421 cout.tie(); 422 int n, m; 423 cin >> n >> m; 424 for(int i = 1; i <= n; i++)cin >> w[i]; 425 for(int i = 0; i < m; i++){ 426 cin >> x[i] >> y[i]; 427 s[x[i]]++; 428 s[y[i]]++; 429 v[x[i]].push_back(i); 430 v[y[i]].push_back(i); 431 } 432 for(int i = 1; i <= n; i++){ 433 if(s[i])pq.push({max(0, s[i]-w[i]), i}); 434 else colmark[i] = 1; 435 } 436 437 while(pq.size()){ 438 auto q = pq.top(); 439 pq.pop(); 440 if(q.fr != max(0, s[q.sc]-w[q.sc]))continue; 441 if(q.fr > 0){ 442 cout << "DEAD\n"; 443 exit(0); 444 } 445 int id = q.sc; 446 vector<int> wt; 447 for(auto u : v[id]){ 448 if(mark[u])continue; 449 a.push_back(u); 450 if(x[u] == id) 451 swap(x[u], y[u]); 452 if(!colmark[x[u]])wt.push_back(x[u]); 453 mark[u] = 1; 454 } 455 sort(all(wt)); 456 for(int i = 0; i < wt.size(); i++){ 457 s[wt[i]]--; 458 if(i == wt.size()-1 || wt[i+1] != wt[i]){ 459 if(s[wt[i]]){ 460 if(max(0, s[wt[i]]-w[wt[i]]) == 0)colmark[wt[i]] = 1; 461 pq.push({max(0, s[wt[i]]-w[wt[i]]), wt[i]}); 462 } 463 } 464 } 465 } 466 cout << "ALIVE\n"; 467 for(int i = 0; i < a.size()/2; i++)swap(a[i], a[a.size()-i-1]); 468 for(auto u : a){ 469 cout << u+1 << ' '; 470 } 471 cout << '\n'; 472 } 473 ``` 474 475 #### [F. BareLee :](https://codeforces.com/contest/1369/problem/F) 476 477 Invented by [DeadlyCritic](/profile/DeadlyCritic "Master DeadlyCritic") and [AS.82](/profile/AS.82 "Candidate Master AS.82"). 478 479 **Brief Solution** 480 481 $\mathcal Brief\; \mathcal Solution$ : 482 483 Define $win_{s,\,e}$ ($s \le e$) equal to $1$ if Lee can win the game when $s$ is written on the board, and equal to $0$ otherwise, also define $lose_{s,\,e}$ the same way. 484 485 Win : 486 487 If $e$ is odd then if $s$ is odd Lee loses otherwise Lee wins. So if $e$ is even then : 488 489 * if $\frac e 2 \lt s \le e$ then if $s$ is odd then Lee wins, otherwise Lee loses; 490 * if $\frac e 4 \lt s \le \frac e 2$ then Lee wins; 491 * if $s \le \frac e 4$ then the answer is equal to $win_{s,\, \lfloor \frac e 4 \rfloor}$. 492 493 Lose : 494 495 If $e \lt 2 \cdot s$, then Lee can immediately lose, otherwise the answer is equal to $\displaystyle win_{s,\, \lfloor \frac e 2 \rfloor}$. 496 497 **Complete Proof** 498 499 Tutorial is loading... 500 501 **Python solution** 502 503 ``` 504 import sys 505 506 inpy = [int(x) for x in sys.stdin.read().split()] 507 508 def win(s, e) : 509 if e == s : 510 return False 511 if e == s+1 : 512 return True 513 if e % 2 == 1 : 514 if s % 2 == 1 : 515 return False 516 return True 517 q = e//4 518 519 if s <= q : 520 return win(s, q) 521 q = e//2 522 if(s > q) : 523 return (e-s) % 2 == 1 524 return True 525 526 def lose(s, e) : 527 q = e//2 528 if(s > q) : 529 return True 530 else : 531 return win(s, q) 532 533 t = inpy[0] 534 start = (True, False) 535 inpo = 1 536 v = (True, True) 537 538 for tc in range(t): 539 if(inpo+1 >= len(inpy)) : 540 print('wtf') 541 s, e = inpy[inpo], inpy[inpo+1] 542 inpo = inpo+2 543 v = ((win(s, e), lose(s, e))) 544 if start[0] and start[1] : 545 break 546 if (not start[0]) and (not start[1]) : 547 break 548 if start[1] : 549 v = (not v[0], not v[1]) 550 start = (v[1], v[0]) 551 552 if((start[0] != True and start[0] != False) or (start[1] != True and start[1] != False)) : 553 print('wtf') 554 sw = 2 555 if start[1] : 556 sw = sw-1 557 print(1, end = ' ') 558 else : 559 sw = sw-1 560 print(0, end = ' ') 561 if start[0] : 562 print(1) 563 sw = sw-1 564 else : 565 print(0) 566 sw = sw-1 567 if sw : 568 print(wtf) 569 ``` 570 571 **C++ solution** 572 573 ``` 574 #include <iostream> 575 #include <vector> 576 #include <string> 577 #define fr first 578 #define sc second 579 #define ll long long 580 #define int ll 581 582 using namespace std; 583 584 const int MN = 1e5+7; 585 586 pair<int, int> c[MN]; 587 588 int chk(ll s, ll e){ 589 if(e == s)return 0; 590 if(e == s+1)return 1; 591 if(e & 1){ 592 if(s & 1)return 0; 593 return 1; 594 } 595 if(s <= e/4) 596 return chk(s, e/4); 597 if(s > (e/4)*2)return ((e-s)&1); 598 else return 1; 599 } 600 601 int lck(ll s, ll e){ 602 if(s*2 > e)return 1; 603 int w = e/2 + 3; 604 while(w*2 > e)w--; 605 return chk(s, w); 606 } 607 608 signed main(){ 609 ios::sync_with_stdio(false); 610 cin.tie(); 611 cout.tie(); 612 613 int n; 614 cin >> n; 615 616 for(int i = 0; i < n; i++){ 617 ll x, y; 618 cin >> x >> y; 619 c[i] = {chk(x, y), lck(x, y)}; 620 } 621 622 int f = 1; 623 int s = 0; 624 for(int i = 0; i < n; i++){ 625 if(f == 1 && s == 1)break; 626 if(f == 0 && s == 0)break; 627 if(s == 1) c[i].fr^=1, c[i].sc^=1; 628 f = c[i].sc; 629 s = c[i].fr; 630 } 631 cout << s << ' ' << f << '\n'; 632 } 633 ```