1562.md (22106B)
1 Source: https://codeforces.com/blog/entry/94278 2 3 Will we, will you... 4 Can we, can you, can we change? 5 6 [1562A - The Miracle and the Sleeper](/contest/1562/problem/A "Codeforces Round 741 (Div. 2)") 7 8 **Hint 1** 9 10 Try to consider such segments where $l \le \lfloor \frac{r}{2} \rfloor + 1$. 11 12 **Hint 2** 13 14 Now think about what to do if this condition is not satisfied. 15 16 **Solution** 17 18 Tutorial is loading... 19 20 **Code C++ (Wind_Eagle)** 21 22 ``` 23 #include <iostream> 24 25 using namespace std; 26 27 int l, r; 28 29 void solve() { 30 if (r < l * 2) { 31 cout << r - l << endl; 32 } 33 else { 34 cout << (r - 1) / 2 << endl; 35 } 36 } 37 38 int main() { 39 int t; 40 cin >> t; 41 while (t--) { 42 cin >> l >> r; 43 solve(); 44 } 45 } 46 ``` 47 48 [1562B - Scenes From a Memory](/contest/1562/problem/B "Codeforces Round 741 (Div. 2)") 49 50 **Hint 1** 51 52 Try to consider small numbers, such as those consisting of three digits. 53 54 **Hint 2** 55 56 Now think about what the maximum number of digits can be in the optimal answer. 57 58 **Solution** 59 60 Tutorial is loading... 61 62 **Code C++ (Wind_Eagle)** 63 64 ``` 65 #include <iostream> 66 67 using namespace std; 68 69 int n; 70 71 string s; 72 73 bool prime[100]; 74 75 void solve() { 76 for (int i = 0; i < n; i++) { 77 if (s[i] == '1' || s[i] == '4' || s[i] == '6' || s[i] == '8' || s[i] == '9') { 78 cout << 1 << endl; 79 cout << s[i] << endl; 80 return; 81 } 82 } 83 for (int i = 0; i < n; i++) { 84 for (int j = i + 1; j < n; j++) { 85 if (!prime[(s[i] - '0') * 10 + (s[j] - '0')]) { 86 cout << 2 << endl; 87 cout << s[i] << s[j] << endl; 88 return; 89 } 90 } 91 } 92 exit(42); 93 } 94 95 int main() { 96 for (int i = 2; i < 100; i++) { 97 prime[i] = true; 98 for (int j = 2; j * j <= i; j++) { 99 if (i % j == 0) { 100 prime[i] = false; 101 } 102 } 103 } 104 int t; 105 cin >> t; 106 while (t--) { 107 cin >> n; 108 cin >> s; 109 solve(); 110 } 111 } 112 ``` 113 114 **Additional Problem 1** 115 116 Try to prove that the author's solution works for $O(k)$ for one test case. 117 118 **Solution of Additional Problem 1** 119 120 Finding an answer consisting of one digit works in $O(k)$. Now let's see how long the loop takes to complete. Indeed, it is easy to see that once the pairs of indexes $(0,1)$, $(0,2)$, and $(1,2)$ are considered, an answer will always be found. This is so because in any number of three digits you can find an answer consisting of two digits (this was proved earlier). So this is equivalent to removing all but the first three digits, and then solving the problem for them (assuming that the length of the optimal answer is two). 121 122 **Additional Problem 2** 123 124 Try to think of a way to search index pairs and a test such that this search works for $O(k^2)$ per test case. 125 126 **Solution of Additional Problem 2** 127 128 Let's take the string \t{3737 \ldots 37} as a string. We will search pairs of indices in the following way: first we will search all pairs of indices with different parities, and then all pairs of indices with the same parity. It is easy to see that such a search will work for $O(k^2)$ for one test case, because all pairs of indices with different parity will give numbers $37$ and $73$, which are prime, and there are $O(k^2)$ such pairs. 129 130 [1562C - Rings](/contest/1562/problem/C "Codeforces Round 741 (Div. 2)") 131 132 **Hint 1** 133 134 Think about whether a suitable $k$ (such that $f(t) = f(w) \cdot k$) can be made small? What small $k$ is easy to multiply binary numbers by? 135 136 **Hint 2** 137 138 Such $k$ can be the numbers $0$, $1$, and $2$~--- multiplying by $0$ gives $0$, multiplying by $1$ leaves the number as is, and multiplying by $2$ adds a zero to the end. Think about how you can take advantage of this. 139 140 **Solution** 141 142 Tutorial is loading... 143 144 **Code C++ (Wind_Eagle)** 145 146 ``` 147 #include <iostream> 148 149 using namespace std; 150 151 int main() { 152 int t; 153 cin >> t; 154 while (t--) { 155 int n; 156 cin >> n; 157 string s; 158 cin >> s; 159 bool solved = false; 160 for (int i = 0; i < n; i++) { 161 if (s[i] == '0') { 162 solved = true; 163 if (i >= n / 2) { 164 cout << 1 << " " << i + 1 << " " << 1 << " " << i << endl; 165 break; 166 } else { 167 cout << i + 2 << " " << n << " " << i + 1 << " " << n << endl; 168 break; 169 } 170 } 171 } 172 if (!solved) { 173 cout << 1 << " " << n - 1 << " " << 2 << " " << n << endl; 174 } 175 } 176 } 177 ``` 178 179 **Additional Problem 1** 180 181 Think about how the problem would be solved if any other number system was chosen, given all the previous conditions (the string consists of the digits $0$ and $1$, the string contains at least one one). 182 183 **Solution of Additional Problem 1** 184 185 The solution would not change in any way. In fact, in a number system with base $k$, adding a zero to the left side does not change the number (multiplication by $1$), but adding a zero to the right side increases the number $k$ times (multiplication by $k$). 186 187 **Additional Problem 2** 188 189 Think about how the problem would be solved if the condition sounded like this: \textit{it is necessary that $f(t)$ is divisible by $f(w)$. There are at least one one in the array. Zero is divisible by all numbers, but no number is divisible by zero. Zero is not divisible by zero.} 190 191 **Solution of Additional Problem 2** 192 193 In fact, the problem gets a little more complicated. For example, consider this test: \t{111000000}. In this case, we could not output $4$ $9$ $5$ $9$ because zero is not divisible by zero. 194 195 We will perform the old solution, but check that we are not trying to divide zero by zero (if we divide something by zero, we will swap the numbers). And if the answer is not found, then either the whole left half of the string consists of zeros, or the whole right half. Let the leftmost unit have position $p1$, and the rightmost unit ~--- position $p2$. Then in the first case you can output $1$ $p2$ $2$ $p2$, and in the second case~--- $p1$ $n$ $p1$ $n-1$. 196 197 It is not hard to see that such a solution will always find the answer. 198 199 In fact, we can solve the problem even simpler: when we meet zero in the left half, we additionally check whether there is at least one one among the characters on the right. If there is, we print the answer, otherwise we move on. Similarly, when we encounter zero in the right half, we additionally check if there is at least one one among the characters on the left. We can show that this solution will also always find the answer. 200 201 It is interesting that we have solved \textbf{a stronger version of the problem}, since the solution we obtained works correctly for the old problem as well. 202 203 [1562D1 - Two Hundred Twenty One (easy version)](/contest/1562/problem/D1 "Codeforces Round 741 (Div. 2)") 204 205 **Hint 1** 206 207 Think about: how is the parity of the length of the segment and the parity of the number of elements to be removed related? 208 209 **Hint 2** 210 211 Think about how much and how the value of the sign-variable sum differs when only one element is removed, and when only its neighbor is removed. 212 213 **Hint 3** 214 215 Consider odd-length segments. Try to take small segments and for each element find out what the sign-variable sum will be after it is removed. After that you may notice something interesting. 216 217 **Solution** 218 219 Tutorial is loading... 220 221 **Code C++ (Wind_Eagle)** 222 223 ``` 224 #include <iostream> 225 226 using namespace std; 227 228 int a[1000000 + 5], p[1000000 + 5]; 229 230 int get_sum(int l, int r) { 231 if (l > r) { 232 return 0; 233 } 234 return (l % 2 == 1) ? p[r] - p[l - 1] : p[l - 1] - p[r]; 235 } 236 237 int main() { 238 ios_base::sync_with_stdio(false); 239 cin.tie(nullptr); 240 int t; 241 cin>>t; 242 while (t--) { 243 int n, q; 244 cin >> n >> q; 245 string ss; 246 cin >> ss; 247 for (int i = 1; i <= n; i++) { 248 a[i] = (ss[i - 1] == '+' ? 1 : -1); 249 } 250 p[0] = 0; 251 for (int i = 1; i <= n; i++) { 252 p[i] = p[i - 1] + (i % 2 == 1 ? a[i] : -a[i]); 253 } 254 for (int o = 0; o < q; o++) { 255 int l, r; 256 cin >> l >> r; 257 if (get_sum(l, r) == 0) { 258 cout << "0\n"; 259 continue; 260 } 261 if ((r - l + 1) % 2 == 0) { 262 cout << "2\n"; 263 } 264 else { 265 cout << "1\n"; 266 } 267 } 268 } 269 } 270 ``` 271 272 [1562D2 - Two Hundred Twenty One (hard version)](/contest/1562/problem/D2 "Codeforces Round 741 (Div. 2)") 273 274 **Hints 1-3** 275 276 See the corresponding hints from Problem D1. 277 278 **Hint 4** 279 280 Consider how to quickly check the value of a sign-variable sum on a segment if you know that exactly one element is removed from it (and know the number of that element). 281 282 **Hint 5** 283 284 From the solution of Problem D1 it is clear that for any odd segment only one element has to be removed. Consider how to find such an element, based on the proof of its existence given above. 285 286 **Solution** 287 288 Tutorial is loading... 289 290 **Code C++ (Wind_Eagle)** 291 292 ``` 293 #include <iostream> 294 295 using namespace std; 296 297 int a[1000000 + 5], p[1000000 + 5]; 298 299 int get_sum(int l, int r) { 300 if (l > r) { 301 return 0; 302 } 303 return (l % 2 == 1) ? p[r] - p[l - 1] : p[l - 1] - p[r]; 304 } 305 306 int check_elimination(int l, int r, int m) { 307 return ((m - l + 1) % 2 == 1) 308 ? get_sum(l, m - 1) + get_sum(m + 1, r) 309 : get_sum(l, m - 1) - get_sum(m + 1, r); 310 } 311 312 int get_sign(int m) { 313 return m > 0 ? 1 : -1; 314 } 315 316 int calculate_odd_segment(int l, int r) { 317 if (l == r) { 318 return l; 319 } 320 int pos = 0; 321 int lb = l; 322 int rb = r; 323 while (lb < rb) { 324 int mb = (lb + rb) / 2; 325 int lq = check_elimination(l,r,lb); 326 int mq = check_elimination(l,r,mb); 327 int rq = check_elimination(l,r,rb); 328 if (lq == 0) { 329 pos = lb; 330 break; 331 } 332 if (mq == 0) { 333 pos = mb; 334 break; 335 } 336 if (rq == 0) { 337 pos = rb; 338 break; 339 } 340 if (get_sign(lq) == get_sign(mq)) { 341 lb = mb; 342 } else { 343 rb = mb; 344 } 345 } 346 return pos; 347 } 348 349 int main() { 350 ios_base::sync_with_stdio(false); 351 cin.tie(nullptr); 352 int t; 353 cin>>t; 354 while (t--) { 355 int n, q; 356 cin >> n >> q; 357 string ss; 358 cin >> ss; 359 for (int i = 1; i <= n; i++) { 360 a[i] = (ss[i - 1] == '+' ? 1 : -1); 361 } 362 p[0] = 0; 363 for (int i = 1; i <= n; i++) { 364 p[i] = p[i - 1] + (i % 2 == 1 ? a[i] : -a[i]); 365 } 366 for (int o = 0; o < q; o++) { 367 int l, r; 368 cin >> l >> r; 369 if (get_sum(l, r) == 0) { 370 cout << "0\n"; 371 continue; 372 } 373 bool even = false; 374 if ((r - l + 1) % 2 == 0) { 375 even = true; 376 l++; 377 } 378 int pos = calculate_odd_segment(l, r); 379 if (even) { 380 cout << "2\n" << l - 1 << " "<< pos << '\n'; 381 } else { 382 cout << "1\n" << pos << '\n'; 383 } 384 } 385 } 386 } 387 ``` 388 389 **Interesting question** 390 391 Is there a solution with asymptotics $O(n + q)$ for a single test case? 392 393 [1562E - Rescue Niwen!](/contest/1562/problem/E "Codeforces Round 741 (Div. 2)") 394 395 **Hint 1** 396 397 To solve it, you will need to quickly (in O(1)) find the largest common prefix of two substring. 398 399 **Hint 2** 400 401 Take some small strings and try to build the largest increasing subsequence. Maybe there's something special about it. 402 403 **Hint 3** 404 405 Use dynamic programming. 406 407 **Solution** 408 409 Tutorial is loading... 410 411 **Code C++ (Wind_Eagle)** 412 413 ``` 414 #include <iostream> 415 416 using namespace std; 417 418 int16_t lcp[10000 + 5][10000 + 5]; 419 420 int dp[10000 + 5]; 421 422 bool is_greater(const string& s, int x, int y) { 423 if (lcp[x][y] == static_cast<int>(s.size()) - x) { 424 return false; 425 } 426 return s[x + lcp[x][y]] > s[y + lcp[x][y]]; 427 } 428 429 int get_score(const string& s, int x, int y) { 430 if (is_greater(s, x, y)) { 431 return dp[y] + static_cast<int>(s.size()) - x - lcp[x][y]; 432 } 433 return 0; 434 } 435 436 int main() { 437 int t; 438 cin >> t; 439 while (t--) { 440 int n; 441 cin >> n; 442 string s; 443 cin >> s; 444 if (s.size() != n) return 42; 445 for (int i = 0; i <= n; i++) { 446 for (int j = 0; j <= n; j++) { 447 lcp[i][j] = 0; 448 } 449 } 450 for (int i = n - 1; i >= 0; i--) { 451 for (int j = n - 1; j >= 0; j--) { 452 if (i == j) { 453 lcp[i][j] = n - i; 454 } else 455 if (s[i] != s[j]) { 456 lcp[i][j] = 0; 457 } else { 458 lcp[i][j] = lcp[i + 1][j + 1] + 1; 459 } 460 } 461 } 462 int ans = n; 463 dp[0] = n; 464 for (int i = 1; i < n; i++) { 465 dp[i] = n - i; 466 for (int j = 0; j < i; j++) { 467 dp[i] = max (dp[i], get_score(s, i, j)); 468 } 469 ans = max(ans, dp[i]); 470 } 471 cout << ans << '\n'; 472 } 473 } 474 ``` 475 476 **Interesting question** 477 478 As far as I know, using trie, you can sort all substrings of a given string in $O(n^2)$. Also, as far as I know, in C++ programming language *std::lower_bound* works so fast that in an array of size $1.25 \cdot 10^7$ the same number of *std::lower_bound* operations is done in a little less than a second. It is also known that *std::lower_bound* can be used to write a search for the largest increasing subsequence in an array. The question is: can we use this to write a $O(n^2 \cdot log(n))$ solution that passes the tests? 479 480 [1562F - Tubular Bells](/contest/1562/problem/F "Codeforces Round 741 (Div. 2)") 481 482 **Hint 1** 483 484 Come up with a solution that uses $\frac{n \cdot (n-1)}{2}$ queries. 485 486 **Hint 2** 487 488 At $n \lt 100$, apply a solution that uses $\frac{n \cdot (n-1)}{2}$ queries. Now suppose $n \geq 100$. Come up with a solution that would use $\lceil\frac{3n}{2}rceil$ queries. 489 490 **Hint 3** 491 492 When $n \lt 10000$, apply a solution that uses $2n$ queries. Now suppose $n \geq 5000$. Most likely, in the $2n$ queries solution you come up with, you need to find the largest prime number on the segment. Think about it, do you really need **the largest** prime number? Maybe just **enough large** prime number would be enough? How can you find such a number? 493 494 **Hint 4** 495 496 Use probabilistic algorithms to find such a number. Use probabilistic algorithms to also make sure that you have found the right number. 497 498 **Hint 5** 499 500 Now use the prime number you have found to find the largest prime number. You will probably already know most of the numbers when you find it, and you can use the largest prime number to find the rest. 501 502 **Solution** 503 504 Tutorial is loading... 505 506 **Code C++ (Wind_Eagle)** 507 508 ``` 509 #include <iostream> 510 #include <vector> 511 #include <algorithm> 512 #include <cmath> 513 #include <ctime> 514 #include <random> 515 516 using namespace std; 517 518 #define int long long 519 520 mt19937 rnd(time(NULL)); 521 522 int swnmb[1000000+5]; 523 524 int swnmbr[1000000+5]; 525 526 int b[1000000+5]; 527 528 bool p[1000000+5]; 529 530 vector<int> primes; 531 532 int get_lcm(int x, int y) 533 { 534 cout<<"? "<<swnmb[x]<<" "<<swnmb[y]<<endl; 535 int u; 536 cin>>u; 537 return u; 538 } 539 540 int max_fact(int d) 541 { 542 for (int j=(int)primes.size()-1; j>=0; j--) 543 { 544 if (d%primes[j]==0) return primes[j]; 545 } 546 } 547 548 vector<int> fact(int d) 549 { 550 vector<int> ans; 551 for (auto j:primes) 552 { 553 if (d==1) break; 554 while (d%j==0) 555 { 556 ans.push_back(j); 557 d/=j; 558 } 559 } 560 return ans; 561 } 562 563 bool is_prime(int d) 564 { 565 for (int j=0; j<(int)primes.size(); j++) 566 { 567 if (primes[j]>500) return true; 568 if (d%primes[j]==0) return false; 569 } 570 return true; 571 } 572 573 int paired_get_lcm[100+5][100+5]; 574 575 void solve_quadric(int n) 576 { 577 for (int i=1; i<=n; i++) { 578 for (int j=i+1; j<=n; j++) { 579 paired_get_lcm[i][j]=get_lcm(i,j); 580 paired_get_lcm[j][i]=paired_get_lcm[i][j]; 581 } 582 } 583 int m1=0; 584 int m2=0; 585 int mx=0; 586 for (int i=1; i<=n; i++) { 587 for (int j=i+1; j<=n; j++) { 588 if (paired_get_lcm[i][j]>mx) 589 { 590 mx=paired_get_lcm[i][j]; 591 m1=i; 592 m2=j; 593 } 594 } 595 } 596 int u=0; 597 for (int i=1; i<=200000; i++) 598 { 599 if (mx==i*(i+1)) 600 { 601 u=i+1; 602 break; 603 } 604 } 605 for (int i=1; i<=n; i++) 606 { 607 if (i==m1||i==m2) continue; 608 if (paired_get_lcm[m1][i]%u!=0) 609 { 610 swap(m1,m2); 611 break; 612 } 613 } 614 b[m1]=u; 615 int pos=m2; 616 for (int v=u-1; v>u-n-1; v--) 617 { 618 int m0=0; 619 int mx=0; 620 for (int j=1; j<=n; j++) { 621 if (b[j]!=0) continue; 622 if (pos==j) continue; 623 if (paired_get_lcm[pos][j]>mx) 624 { 625 mx=paired_get_lcm[pos][j]; 626 m0=j; 627 } 628 } 629 b[pos]=v; 630 pos=m0; 631 } 632 b[pos]=u-n+1; 633 } 634 635 void solve_pair(int n) 636 { 637 int maxnum=0; 638 int maxpos=0; 639 int notmaxpos=0; 640 for (int i=1; i<=n; i+=2) 641 { 642 int u; 643 if (i!=n) u=get_lcm(i,i+1); 644 else u=get_lcm(i-1,i); 645 int w=max_fact(u); 646 if (w>maxnum) 647 { 648 maxnum=w; 649 maxpos=min(i+1,n); 650 } else { 651 notmaxpos=i; 652 } 653 } 654 int cur=get_lcm(notmaxpos,maxpos); 655 if (cur%maxnum!=0) { 656 maxpos--; 657 } 658 b[maxpos]=maxnum; 659 for (int i=1; i<=n; i++) 660 { 661 if (i==maxpos) continue; 662 int u=get_lcm(i,maxpos)/maxnum; 663 b[i]=u; 664 } 665 } 666 667 void print_ans(int n) 668 { 669 cout<<"! "; 670 for (int i=1; i<=n; i++) { 671 cout<<b[swnmbr[i]]; 672 if (i!=n) cout<<" "; 673 } 674 cout<<endl; 675 } 676 677 int32_t main() 678 { 679 for (int i=2; i<=200000; i++) 680 { 681 if (p[i]) continue; 682 for (int j=i*i; j<=200000; j+=i) 683 { 684 p[j]=true; 685 } 686 primes.push_back(i); 687 } 688 int t; 689 cin>>t; 690 while (t--) 691 { 692 int n; 693 cin>>n; 694 for (int i=1; i<=n; i++) { 695 swnmb[i]=0; 696 swnmbr[i]=0; 697 b[i]=0; 698 } 699 for (int i=1; i<=n; i++) { 700 swnmb[i]=i; 701 } 702 for (int i=1; i<=n*5; i++) { 703 swap(swnmb[rnd()%n+1], swnmb[rnd()%n+1]); 704 } 705 for (int i=1; i<=n; i++) { 706 swnmbr[swnmb[i]]=i; 707 } 708 if (n<100) { 709 solve_quadric(n); 710 print_ans(n); 711 continue; 712 } 713 if (n<10000) { 714 solve_pair(n); 715 print_ans(n); 716 continue; 717 } 718 int t1=0; 719 int t2=0; 720 int pos1=0; 721 int pos2=0; 722 for (int i=1; i<=4000; i++) 723 { 724 int i1=rnd()%n+1; 725 int i2=rnd()%n+1; 726 while (i1 == i2) { 727 i2=rnd()%n+1; 728 } 729 vector<int> f=fact(get_lcm(i1,i2)); 730 if (f.size()==2&&f[0]>500&&f[1]>500) 731 { 732 bool first1=true; 733 bool first2=true; 734 for (int j=0; j<100; j++) 735 { 736 int t=rnd()%n+1; 737 while (t==i1||t==i2) 738 { 739 t=rnd()%n+1; 740 } 741 if (get_lcm(i1,t)%f[0]!=0) 742 { 743 first1=false; 744 break; 745 } 746 } 747 for (int j=0; j<100; j++) 748 { 749 int t=rnd()%n+1; 750 while (t==i1||t==i2) 751 { 752 t=rnd()%n+1; 753 } 754 if (get_lcm(i1,t)%f[1]!=0) 755 { 756 first2=false; 757 break; 758 } 759 } 760 if (first1&&first2) 761 { 762 bool second1=true; 763 for (int j=0; j<100; j++) 764 { 765 int t=rnd()%n+1; 766 while (t==i1||t==i2) 767 { 768 t=rnd()%n+1; 769 } 770 if (get_lcm(i2,t)%f[1]!=0) 771 { 772 second1=false; 773 break; 774 } 775 } 776 if (second1) 777 { 778 t2=f[0]*f[1]; 779 t1=f[0]; 780 } 781 else 782 { 783 t2=f[0]*f[1]; 784 t1=f[1]; 785 } 786 pos1=i2; 787 pos2=i1; 788 } 789 else 790 { 791 if (!first1) 792 { 793 t1=f[1]; 794 t2=f[0]; 795 } 796 else 797 { 798 t1=f[0]; 799 t2=f[1]; 800 } 801 pos1=i1; 802 pos2=i2; 803 } 804 b[pos1]=t1; 805 b[pos2]=t2; 806 int posf=0; 807 int maxf=0; 808 for (int j=1; j<=n; j++) 809 { 810 if (j==i1||j==i2) continue; 811 int u=get_lcm(pos1,j); 812 if (u/t1>500) 813 { 814 b[j]=u/t1; 815 if (is_prime(b[j])) 816 { 817 if (b[j]>maxf) 818 { 819 maxf=b[j]; 820 posf=j; 821 } 822 } 823 } 824 } 825 for (int j=1; j<=n; j++) 826 { 827 if (b[j]!=0) continue; 828 b[j]=get_lcm(posf,j)/b[posf]; 829 } 830 break; 831 } 832 } 833 print_ans(n); 834 } 835 } 836 ```