1878.md (14676B)
1 Source: https://codeforces.com/blog/entry/120813 2 3 Thank you for participating in the first ever Serbian Div. 3 Codeforces round! 4 5 **Sorry** 6 7 Before the editorial, we are sorry for the big gap between problems C and D. 8 9 This was the first round we ever created (except for [wxhtzdy](/profile/wxhtzdy "Master wxhtzdy")). 10 11 We are striving to become better problem-setters and create more balanced problems-sets in the future. 12 13 Also a massive thanks to [Vladosiya](/profile/Vladosiya "Expert Vladosiya") for giving us a chance to create a divison 3 round! 14 15 [1878A - How Much Does Daytona Cost?](/contest/1878/problem/A "Codeforces Round 900 (Div. 3)") 16 17 **Problem was authored and prepared by** 18 19 Author: [wxhtzdy](/profile/wxhtzdy "Master wxhtzdy") 20 21 Prepared by: [ognjentesic](/profile/ognjentesic "Pupil ognjentesic"), [AndrewPav](/profile/AndrewPav "Specialist AndrewPav"), [AlphaMale06](/profile/AlphaMale06 "Expert AlphaMale06") 22 23 **Hints** 24 25 **Hint 1** 26 27 When is the answer definitely "NO"? 28 29 **Hint 2** 30 31 What happens if there is no element equal to $k$ in the array? 32 33 **Hint 3** 34 35 What happens if there is an element equal to $k$ in the array? 36 37 **Tutorial** 38 39 Tutorial is loading... 40 41 **Solution** 42 43 ``` 44 #include <bits/stdc++.h> 45 46 using namespace std; 47 48 int main(){ 49 int t; //read the number of test cases 50 cin >> t; 51 while(t--){ 52 int n, k; 53 cin >> n >> k; //read n and k 54 bool ys=0; //bool value if true then there exists a subsegment which satisfies the condition, else it doesn't exist 55 for(int i=0; i< n; i++){ 56 int a; //read the i-th element of the array 57 cin >> a; 58 if(a==k)ys=1; //if the element is equal to k, then the subsegment [i, i] has the most common element equal to k 59 } 60 if(ys)cout << "YES\n"; //output the answer 61 else cout << "NO\n"; 62 } 63 } 64 ``` 65 66 [1878B - Aleksa and Stack](/contest/1878/problem/B "Codeforces Round 900 (Div. 3)") 67 68 **Problem was authored and prepared by** 69 70 Author: [ognjentesic](/profile/ognjentesic "Pupil ognjentesic") 71 72 Prepared by: [ognjentesic](/profile/ognjentesic "Pupil ognjentesic"), [AlphaMale06](/profile/AlphaMale06 "Expert AlphaMale06") 73 74 **Hints** 75 76 **Hint 1** 77 78 Watch parity. 79 80 **Hint 2** 81 82 What does the parity of $3 \cdot x$ depend on? 83 84 **Hint 3** 85 86 What parity are numbers which divide odd numbers? 87 88 **Tutorial** 89 90 Tutorial is loading... 91 92 **Solution** 93 94 ``` 95 #include <bits/stdc++.h> 96 97 using namespace std; 98 99 int main(){ 100 int t; //read the number of test cases 101 cin >> t; 102 while(t--){ 103 int n; //read n 104 cin >> n; 105 for(int i=0; i< n; i++)cout << i*2+1 << " "; //write the first n odd numbers in order 106 cout << '\n'; 107 } 108 } 109 ``` 110 111 [1878C - Vasilije in Cacak](/contest/1878/problem/C "Codeforces Round 900 (Div. 3)") 112 113 **Problem was authored and prepared by** 114 115 Author: [AlphaMale06](/profile/AlphaMale06 "Expert AlphaMale06") 116 117 Prepared by: [ognjentesic](/profile/ognjentesic "Pupil ognjentesic"), [AlphaMale06](/profile/AlphaMale06 "Expert AlphaMale06") 118 119 **Hints** 120 121 **Hint 1** 122 123 Prove that the answer for the second test case is "NO". 124 125 **Hint 2** 126 127 $ 1 + 2 + 3 \gt 5$ 128 129 **Hint 3** 130 131 Determine the minimum and maximum sum achievable. 132 133 **Hint 4** 134 135 Prove that it's possible to construct the desired sequence for any requested sum between the minimum and maximum possible sum. 136 137 **Tutorial** 138 139 Tutorial is loading... 140 141 **Solution** 142 143 ``` 144 #include <iostream> 145 146 using namespace std; 147 148 int main(){ 149 int t; //read the number of test cases 150 cin >> t; 151 while(t--){ 152 long long n, x, k; //read n, x, k for each test case 153 cin >> n >> x >> k; 154 if(2*k>=x*(x+1) && 2*k<=n*(n+1)-(n-x)*(n-x+1)){ //check if k is between the minimum and maximum sum 155 cout << "YES\n"; 156 } 157 else cout << "NO\n"; 158 } 159 } 160 ``` 161 162 [1878D - Reverse Madness](/contest/1878/problem/D "Codeforces Round 900 (Div. 3)") 163 164 **Problem was authored and prepared by** 165 166 Author: [AlphaMale06](/profile/AlphaMale06 "Expert AlphaMale06") 167 168 Prepared by: [ognjentesic](/profile/ognjentesic "Pupil ognjentesic"), [AlphaMale06](/profile/AlphaMale06 "Expert AlphaMale06") 169 170 **Hints** 171 172 **Hint 1** 173 174 For each $i$, ($1 \le i \le k$), we can treat the substring $[l_i, r_i]$ as a seperate test case. 175 176 **Hint 2** 177 178 What happens when we make the same modification twice? 179 180 **Hint 3** 181 182 Does the order of the operations matter? 183 184 **Hint 4** 185 186 Try pre-processing the queries 187 188 **Tutorial** 189 190 Tutorial is loading... 191 192 **Solution** 193 194 ``` 195 #include <bits/stdc++.h> 196 197 using namespace std; 198 199 int main(){ 200 int t; //number of test cases 201 cin >> t; 202 while(t--){ 203 int n, k; //read the input 204 cin >> n >> k; 205 string s; 206 cin >> s; 207 int a[k]; int b[k]; 208 for(int i=0; i< k; i++){cin >> a[i]; a[i]--;} 209 for(int i=0; i< k; i++){cin >> b[i]; b[i]--;} 210 int q; 211 cin >> q; 212 int cnt[n+1]={0}; //read and preprocess queries 213 for(int i=0; i< q; i++){ 214 int x; cin >> x; cnt[x-1]++; 215 } 216 string ans=""; 217 for(int i=0; i<k; i++){ //treat each interval as a seperate test case 218 string s1=s.substr(a[i], b[i]-a[i]+1); 219 int sum=0; 220 int l=a[i]; 221 int r=b[i]; 222 for(int j=l; j<=(l+r)/2; j++){ 223 sum+=cnt[j]+cnt[r-j+l]; 224 if(sum&1)swap(s1[j-l], s1[r-j]); 225 } 226 ans+=s1; 227 } 228 cout << ans << '\n'; 229 } 230 } 231 ``` 232 233 [1878E - Iva & Pav](/contest/1878/problem/E "Codeforces Round 900 (Div. 3)") 234 235 **Problem was authored and prepared by** 236 237 Author: [AndrewPav](/profile/AndrewPav "Specialist AndrewPav"), [AlphaMale06](/profile/AlphaMale06 "Expert AlphaMale06") 238 239 Prepared by: [ognjentesic](/profile/ognjentesic "Pupil ognjentesic"), [AndrewPav](/profile/AndrewPav "Specialist AndrewPav"), [OAleksa](/profile/OAleksa "Specialist OAleksa"), [AlphaMale06](/profile/AlphaMale06 "Expert AlphaMale06") 240 241 **Hints** 242 243 **Hint 1** 244 245 Try calculating $f(l, r)$ bit by bit 246 247 **Hint 2** 248 249 Which condition has to hold true for all elements on a subsegment $[l,r]$, and for a certain bit, for that bit to be present in $f(l,r)$? 250 251 **Hint 3** 252 253 How can we check if that condition is true for a certain bit fast? 254 255 **Hint 4** 256 257 Try prefix sums. 258 259 **Hint 5** 260 261 Try binary search. 262 263 **Tutorial** 264 265 Tutorial is loading... 266 267 **Solution** 268 269 ``` 270 #include <bits/stdc++.h> 271 using namespace std; 272 using ll = long long; 273 274 275 const int N =200003; 276 const int bits=30; 277 int pref[N][bits]; 278 int a[N]; 279 void Buildprefix(int n){ //Builds the prefix sums for each bit 280 for(int i=0; i< n; i++){ 281 for(int j=0; j<30; j++){ 282 if(a[i]&(1<<j)){ 283 pref[i+1][j]=pref[i][j]+1; 284 } 285 else{ 286 pref[i+1][j]=pref[i][j]; 287 } 288 } 289 } 290 } 291 void solve(){ 292 int n; 293 cin >> n; 294 for(int i=0; i< n; i++){ 295 cin >> a[i]; 296 } 297 Buildprefix(n); 298 int q; 299 cin >> q; 300 while(q--){ 301 int l, k; 302 cin >> l >> k; 303 if(a[l-1]<k){ 304 cout << -1 << '\n'; 305 continue; 306 } 307 int lo=l; 308 int hi=n; 309 int ans=l; 310 while(lo<=hi){ 311 int s=(lo+hi)/2; 312 int num=0; 313 for(int j=0; j< bits; j++){ 314 if(pref[s][j]-pref[l-1][j]==s-l+1){ 315 num+=(1<<j); 316 } 317 } 318 if(num>=k){ 319 lo=s+1; 320 ans=max(ans, s); 321 } 322 else hi=s-1; 323 } 324 cout << ans << '\n'; 325 } 326 } 327 328 int main(){ 329 int t = 1; 330 cin >> t; 331 while(t--){ 332 solve(); 333 } 334 } 335 ``` 336 337 [1878F - Vasilije Loves Number Theory](/contest/1878/problem/F "Codeforces Round 900 (Div. 3)") 338 339 **Problem was authored and prepared by** 340 341 Author: [ognjentesic](/profile/ognjentesic "Pupil ognjentesic"), [AlphaMale06](/profile/AlphaMale06 "Expert AlphaMale06") 342 343 Prepared by: [ognjentesic](/profile/ognjentesic "Pupil ognjentesic"), [AlphaMale06](/profile/AlphaMale06 "Expert AlphaMale06") 344 345 **Hints** 346 347 **Hint 1** 348 349 What does the condition $gcd(a, n) = 1$ allow us to do? 350 351 **Hint 2** 352 353 How does any allowed operation affect $d(a \cdot n)$? 354 355 **Hint 3** 356 357 Try to prove that the answer is "YES" if $d(n)$ divides $n$. 358 359 **Hint 4** 360 361 Try to prove that the answer is "NO" otherwise. 362 363 **Hint 5** 364 365 How can you find and maintain the number of divisors quickly? 366 367 **Hint 6** 368 369 To make the implementation easier, try using the condition $d(n) \le 10^9$. 370 371 **Tutorial** 372 373 Tutorial is loading... 374 375 **Solution** 376 377 ``` 378 #include <bits/stdc++.h> 379 380 using ll = long long; 381 using namespace std; 382 383 const int N = 1000003; 384 map<int, int> powers; //key is a prime number, value is te highest powert 385 map<int, int> original_divisors; //same as map powers but isn't updated during queries, it's used to reset the powers 386 int smallest_divisor[N]; //precalculated smallest divisors to make factorization O(logx) 387 bool mark[N]; //marks numbers which aren't prime (used for sieve) 388 ll divisor_count = 1; //the number of divisors (updated during queries) 389 390 void prime(){ //calculates the smallers divisor for each number from 1 to N (sieve of erathosetenes) 391 smallest_divisor[1]=1; 392 smallest_divisor[2]=2; 393 for(int i=4; i<N; i+=2){ 394 mark[i]=true; 395 smallest_divisor[i]=2; 396 } 397 for(int i=3; i<N; i+=2){ 398 if(!mark[i]){ 399 smallest_divisor[i]=i; 400 for(ll j = i*1ll*i; j<N; j+=2*i){ 401 if(!mark[j]){ 402 smallest_divisor[j]=i; 403 mark[j]=1; 404 } 405 } 406 } 407 } 408 } 409 //a function for factorizing a number (used to process queries and factorize n in the beginning) 410 //it also updates the highest prime which divides n (powers map), and the number of divisors of n (divisor_count) 411 void factorize(int x){ 412 int p=0; 413 int current_divisor = 1; 414 while(x>1){ //while x has non 1 divisors, divide it by it's smallest divisor which isn't 1(smallers divisor if always prime) 415 if(smallest_divisor[x]!=current_divisor){ 416 if(p>0){ 417 divisor_count/=powers[current_divisor]+1; 418 powers[current_divisor]+=p; 419 divisor_count*=powers[current_divisor]+1; 420 } 421 p=1; 422 current_divisor=smallest_divisor[x]; 423 } 424 else{ 425 p++; 426 } 427 x/=smallest_divisor[x]; 428 } 429 if(p>0){ 430 divisor_count/=powers[current_divisor]+1; 431 powers[current_divisor]+=p; 432 divisor_count*=powers[current_divisor]+1; 433 } 434 return; 435 } 436 437 int main(){ 438 prime(); //precalculate smallest divisors 439 int t; 440 cin >> t; 441 while(t--){ 442 //read n and q 443 int n; int q; 444 cin >> n >> q; 445 //factorize n 446 factorize(n); 447 //since factorize updates the powers map, update the origional_divisors map too 448 for(auto prime : powers){ 449 original_divisors[prime.first]=prime.second; 450 } 451 int original_divisor_count = divisor_count; //since factorize updates the divisor_count we update the original_divisor_count too 452 vector<int> queries; //storing previous queries 453 //processing queries 454 while(q--){ 455 int query_type; 456 cin >> query_type; 457 if(query_type==1){ //query of type 1 (multiply n by x) 458 int x; 459 cin >> x; 460 factorize(x); //factorize x, update the powers map, and the number of divisors 461 queries.push_back(x); //add x to the list of previous queries 462 ll num=n; 463 for(int query : queries){ //check if the product of all previous queries and n is divisible by d(n) 464 num*=query; 465 num%=divisor_count; 466 } 467 if(num==0){ //if it is the answer is yes else the answer is no 468 cout << "YES\n"; 469 } 470 else cout << "NO\n"; 471 } 472 else{ //here we should reset everything related to the type 1 query 473 powers.clear(); //clear the powers map and set it to original divisors and powers 474 for(auto original_div : original_divisors){ 475 powers[original_div.first]=original_div.second; 476 } 477 divisor_count=original_divisor_count; //restart the divisor_count 478 queries.clear(); //clear the queries (since we only need the queries since the previous type 2 query) 479 } 480 } 481 original_divisors.clear(); 482 powers.clear(); 483 divisor_count=1; 484 original_divisor_count =1; 485 if(t) cout << "\n"; 486 } 487 } 488 ``` 489 490 [1878G - wxhtzdy ORO Tree](/contest/1878/problem/G "Codeforces Round 900 (Div. 3)") 491 492 **Problem was authored and prepared by** 493 494 Author: [wxhtzdy](/profile/wxhtzdy "Master wxhtzdy") 495 496 Prepared by: [ognjentesic](/profile/ognjentesic "Pupil ognjentesic"), [OAleksa](/profile/OAleksa "Specialist OAleksa"), [AlphaMale06](/profile/AlphaMale06 "Expert AlphaMale06") 497 498 **Hints** 499 500 **Hint 1** 501 502 How many vertices actually matter on the path from $x$ to $y$? 503 504 **Hint 2** 505 506 How do we find them? 507 508 **Hint 3** 509 510 Root the tree arbitrarily. 511 512 **Hint 4** 513 514 Try calculating the number of occurrences for each bit on the path from the root to a certain vertex. 515 516 **Hint 5** 517 518 Try binary search. 519 520 **Hint 6** 521 522 Try LCA (Lowest common ancestor). 523 524 **Tutorial** 525 526 Tutorial is loading... 527 528 **Solution** 529 530 ``` 531 #include <bits/stdc++.h> 532 #define f first 533 #define s second 534 using namespace std; 535 #define int long long 536 const int maxn = 2e5 + 69; 537 const int k = 19; 538 const int bits = 30; 539 vector<int> g[maxn]; 540 int n, q, a[maxn], up[maxn][k], tin[maxn], tout[maxn], timer, d[maxn]; 541 int r[maxn][k]; 542 int bst[maxn][bits]; 543 void dfs(int v, int p, vector<int> b) { 544 tin[v] = ++timer; 545 up[v][0] = p; 546 r[v][0] = a[p]; 547 d[v] = d[p] + 1; 548 for (int i = 0;i < bits;i++) { 549 bst[v][i] = b[i]; 550 if (a[v] & (1 << i)) 551 b[i] = v; 552 } 553 for (int i = 1;i < k;i++) { 554 up[v][i] = up[up[v][i - 1]][i - 1]; 555 r[v][i] = r[v][i - 1] | r[up[v][i - 1]][i - 1]; 556 } 557 for (auto u : g[v]) { 558 if (u != p) 559 dfs(u, v, b); 560 } 561 tout[v] = timer; 562 } 563 564 bool is_anc(int u, int v) { 565 return tin[u] <= tin[v] && tout[u] >= tout[v]; 566 } 567 568 int lca(int u, int v) { 569 if(is_anc(u, v)) 570 return u; 571 else if(is_anc(v, u)) 572 return v; 573 for (int i = k - 1;i >= 0;i--) { 574 if (!is_anc(up[u][i], v) && up[u][i] > 0) 575 u = up[u][i]; 576 } 577 return up[u][0]; 578 } 579 580 int OR(int u, int dis) { 581 int res = a[u]; 582 for (int j = 0;j < bits;j++) { 583 if (dis & (1 << j)) { 584 res |= r[u][j]; 585 u = up[u][j]; 586 } 587 } 588 return res; 589 } 590 591 int Qry(int u, int v) { 592 int lc = lca(u, v); 593 return OR(u, d[u] - d[lc]) | OR(v, d[v] - d[lc]); 594 } 595 596 signed main() 597 { 598 int tt = 1; 599 cin >> tt; 600 while(tt--) { 601 cin >> n; 602 timer = 0; 603 for (int i = 1;i <= n;i++) 604 g[i].clear(); 605 for (int i = 1;i <= n;i++) 606 cin >> a[i]; 607 for (int i = 1;i <= n - 1;i++) { 608 int x, y; 609 cin >> x >> y; 610 g[x].push_back(y); 611 g[y].push_back(x); 612 } 613 vector<int> temp(30, -1); 614 dfs(1, 0, temp); 615 cin >> q; 616 for (int i = 1;i <= q;i++) { 617 int x, y; 618 cin >> x >> y; 619 int LCA = lca(x, y); 620 vector<int> t; 621 t.push_back(x); 622 t.push_back(y); 623 for (int i = 0;i < bits;i++) { 624 if (bst[x][i] != -1 && is_anc(LCA, bst[x][i])) 625 t.push_back(bst[x][i]); 626 if (bst[y][i] != -1 && is_anc(LCA, bst[y][i])) 627 t.push_back(bst[y][i]); 628 } 629 int ans = __builtin_popcount(a[x]) + __builtin_popcount(a[y]); 630 for (auto p : t) { 631 int x1 = a[x], x2 = a[y]; 632 x1 |= Qry(x, p); 633 x2 |= Qry(y, p); 634 ans = max(ans, 1ll * __builtin_popcount(x1) + __builtin_popcount(x2)); 635 } 636 cout << ans << " "; 637 } 638 cout << "\n"; 639 } 640 return 0; 641 } 642 ```