1392.md (36818B)
1 Source: https://codeforces.com/blog/entry/81565 2 3 We hope you liked the problems! We apologize for the weak pretests for A and B -- that was a major oversight on our part. Hopefully you were still able to enjoy the contest regardless :) 4 5 We have to apologize to [antontrygubO_o](/profile/antontrygubO_o "Grandmaster antontrygubO_o") a bit here -- the rejection count mentioned in the [editorial](https://codeforces.com/blog/entry/79974) for [Codeforces Round 655 (Div. 2)](/contest/1372 "Codeforces Round 655 (Div. 2)") actually also included this round, as the problems from that round and problems A through G in this round were created together. We did have one more problem rejected after that round happened, bringing up the total to 73. For reference, here are the overall rejection counts for each problem: 6 7 **Rejection Counts** 8 9 * A: 12 10 * B: 16 11 * C: **6** 12 * D: 19 13 * E: 18 14 * F: 2 15 16 Total: **73** 17 18 Without further ado, here are the tutorials for each of the problems: 19 20 Tutorial is loading... 21 22 **Solution (Kotlin) by golions** 23 24 ``` 25 import java.io.* 26 import java.util.* 27 import kotlin.math.* 28 29 fun main(){ 30 val f = BufferedReader(InputStreamReader(System.`in`)) 31 32 for(q in 1..f.readLine().toInt()){ 33 val n = f.readLine().toInt() 34 val array = f.readLine().split(" ").map{it.toInt()}.toHashSet() 35 36 if(array.size == 1){ 37 println(n) 38 } else { 39 println(1) 40 } 41 } 42 } 43 ``` 44 45 **Solution (Java) by MagentaCobra** 46 47 ``` 48 /* 49 Omkar orz 50 */ 51 import java.util.*; 52 import java.io.*; 53 import java.math.*; 54 55 public class ModelPasswordA 56 { 57 public static void main(String omkar[]) throws Exception 58 { 59 BufferedReader infile = new BufferedReader(new InputStreamReader(System.in)); 60 StringTokenizer st = new StringTokenizer(infile.readLine()); 61 int T = Integer.parseInt(st.nextToken()); 62 StringBuilder sb = new StringBuilder(); 63 while(T-->0) 64 { 65 int N = Integer.parseInt(infile.readLine()); 66 int[] arr = new int[N]; 67 st = new StringTokenizer(infile.readLine()); 68 for(int i=0; i < N; i++) 69 arr[i] = Integer.parseInt(st.nextToken()); 70 int res = N; 71 for(int i=1; i < N; i++) 72 if(arr[i] != arr[i-1]) 73 res = 1; 74 sb.append(res+"\n"); 75 } 76 System.out.print(sb); 77 } 78 } 79 ``` 80 81 **Solution (C++) by hugopm** 82 83 ``` 84 #include <bits/stdc++.h> 85 #define len(v) ((int)((v).size())) 86 #define all(v) (v).begin(), (v).end() 87 #define rall(v) (v).rbegin(), (v).rend() 88 #define chmax(x, v) x = max((x), (v)) 89 #define chmin(x, v) x = min((x), (v)) 90 using namespace std; 91 using ll = long long; 92 93 void solve() { 94 int n; cin >> n; 95 vector<int> vec(n); 96 for (int i = 0; i < n; ++i) { 97 cin >> vec[i]; 98 } 99 sort(all(vec)); 100 if (vec.front() == vec.back()) cout << n << "\n"; 101 else cout << "1\n"; 102 } 103 104 int main() { 105 ios::sync_with_stdio(false); 106 cin.tie(0); 107 108 int nbTests; 109 cin >> nbTests; 110 for (int iTest = 0; iTest < nbTests; ++iTest) { 111 solve(); 112 } 113 } 114 ``` 115 116 Idea: [gotexans](/profile/gotexans "Master gotexans") and [qlf9](/profile/qlf9 "Expert qlf9") 117 118 Preparation: [gotexans](/profile/gotexans "Master gotexans") 119 120 Tutorial is loading... 121 122 **Solution (Kotlin) by Tlatoani** 123 124 ``` 125 import java.io.BufferedReader 126 import java.io.InputStreamReader 127 128 fun main() { 129 val jin = BufferedReader(InputStreamReader(System.`in`)) 130 val out = StringBuilder() 131 for (c in 1..jin.readLine().toInt()) { 132 val line = jin.readLine().split(" ") 133 val n = line[0].toInt() 134 val k = line[1].last().toString().toInt() % 2 135 val array = jin.readLine().split(" ").map { it.toLong() }.toLongArray() 136 var m = array.max()!! 137 for (j in 0 until n) { 138 array[j] = m - array[j] 139 } 140 if (k == 0) { 141 m = array.max()!! 142 for (j in 0 until n) { 143 array[j] = m - array[j] 144 } 145 } 146 out.appendln(array.joinToString(" ")) 147 } 148 print(out) 149 } 150 ``` 151 152 **Solution (Java) by MagentaCobra** 153 154 ``` 155 //Omkar, Holy Light 156 import java.util.*; 157 import java.io.*; 158 import java.math.*; 159 160 public class ModelB 161 { 162 public static void main(String omkar[]) throws Exception 163 { 164 //query based 165 BufferedReader infile = new BufferedReader(new InputStreamReader(System.in)); 166 StringTokenizer st = new StringTokenizer(infile.readLine()); 167 int T = Integer.parseInt(st.nextToken()); 168 StringBuilder sb = new StringBuilder(); 169 while(T-->0) 170 { 171 st = new StringTokenizer(infile.readLine()); 172 int N = Integer.parseInt(st.nextToken()); 173 long K = Long.parseLong(st.nextToken())%2; 174 if(K == 0) K = 2; 175 int[] arr = new int[N]; 176 st = new StringTokenizer(infile.readLine()); 177 for(int i=0; i < N; i++) 178 arr[i] = Integer.parseInt(st.nextToken()); 179 for(int turns=0; turns < K; turns++) 180 { 181 int max = arr[0]; 182 for(int x: arr) 183 max = Math.max(max, x); 184 for(int i=0; i < N; i++) 185 arr[i] = max-arr[i]; 186 } 187 for(int i=0; i < N; i++) 188 { 189 sb.append(arr[i]); 190 if(i+1 < N) 191 sb.append(" "); 192 } 193 sb.append("\n"); 194 } 195 System.out.print(sb); 196 } 197 } 198 ``` 199 200 **Solution (C++) by tfg** 201 202 ``` 203 #include <iostream> 204 #include <vector> 205 #include <chrono> 206 #include <random> 207 #include <cassert> 208 209 std::mt19937 rng((int) std::chrono::steady_clock::now().time_since_epoch().count()); 210 211 int main() { 212 std::ios_base::sync_with_stdio(false); std::cin.tie(NULL); 213 int t; 214 std::cin >> t; 215 while(t--) { 216 int n; 217 long long k; 218 std::cin >> n >> k; 219 std::vector<int> a(n); 220 for(int i = 0; i < n; i++) { 221 std::cin >> a[i]; 222 } 223 if(k > 1) { 224 k = 2 + k % 2; 225 } 226 while(k--) { 227 int mx = -1000000000; 228 for(int i = 0; i < n; i++) { 229 mx = std::max(mx, a[i]); 230 } 231 for(int i = 0; i < n; i++) { 232 a[i] = mx - a[i]; 233 } 234 } 235 for(int i = 0; i < n; i++) { 236 std::cout << a[i] << (i + 1 == n ? '\n' : ' '); 237 } 238 } 239 } 240 ``` 241 242 Idea: [gotexans](/profile/gotexans "Master gotexans") 243 244 Preparation: [gotexans](/profile/gotexans "Master gotexans") 245 246 Tutorial is loading... 247 248 **Solution (Kotlin) by Tlatoani** 249 250 ``` 251 import kotlin.math.max 252 253 fun main() { 254 for (c in 1..readLine()!!.toInt()) { 255 val n = readLine()!!.toInt() 256 val hs = readLine()!!.split(" ").map { it.toLong() } 257 var answer = 0L 258 for (j in 1 until n) { 259 answer += max(0L, hs[j - 1] - hs[j]) 260 } 261 println(answer) 262 } 263 } 264 ``` 265 266 **Solution (Java) by qlf9** 267 268 ``` 269 import java.util.*; 270 import java.io.*; 271 272 public class OmkarAndWaterslide { 273 public static void main(String[] args) throws IOException{ 274 BufferedReader f = new BufferedReader(new InputStreamReader(System.in)); 275 PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out)); 276 int t = Integer.parseInt(f.readLine()); 277 while(t-->0){ 278 int n = Integer.parseInt(f.readLine()); 279 long[] arr = new long[n]; 280 StringTokenizer st = new StringTokenizer(f.readLine()); 281 for(int i = 0; i < n; i++){ 282 arr[i] = Integer.parseInt(st.nextToken()); 283 } 284 long ans = 0; 285 for(int i = 0; i < n-1; i++){ 286 ans+=Math.max(0, arr[i]-arr[i+1]); 287 } 288 out.println(ans); 289 } 290 out.close(); 291 } 292 } 293 ``` 294 295 **Solution (C++) by tfg** 296 297 ``` 298 #include <iostream> 299 #include <vector> 300 #include <chrono> 301 #include <random> 302 #include <cassert> 303 304 std::mt19937 rng((int) std::chrono::steady_clock::now().time_since_epoch().count()); 305 306 int main() { 307 std::ios_base::sync_with_stdio(false); std::cin.tie(NULL); 308 int t; 309 std::cin >> t; 310 while(t--) { 311 int n; 312 std::cin >> n; 313 long long last = 0; 314 long long ans = 0; 315 while(n--) { 316 long long x; 317 std::cin >> x; 318 x += ans; 319 if(x >= last) { 320 last = x; 321 } else { 322 ans += last — x; 323 } 324 } 325 std::cout << ans << '\n'; 326 } 327 } 328 ``` 329 330 Idea: [qlf9](/profile/qlf9 "Expert qlf9") 331 332 Preparation: [qlf9](/profile/qlf9 "Expert qlf9") 333 334 Tutorial is loading... 335 336 **Solution (Kotlin) by Tlatoani** 337 338 ``` 339 import java.io.BufferedReader 340 import java.io.InputStreamReader 341 342 fun main() { 343 val jin = BufferedReader(InputStreamReader(System.`in`)) 344 val out = StringBuilder() 345 for (c in 1..jin.readLine().toInt()) { 346 val n = jin.readLine().toInt() 347 val s = jin.readLine() 348 if (s.all { it == s[0] }) { 349 out.appendln((n + 2) / 3) 350 } else { 351 var k = 0 352 while (s[k] == s[0]) { 353 k++ 354 } 355 var answer = 0 356 var curr = 0 357 var chara = s[k] 358 for (j in k until k + n) { 359 if (s[j % n] == chara) { 360 curr++ 361 } else { 362 answer += curr / 3 363 curr = 1 364 chara = s[j % n] 365 } 366 } 367 answer += curr / 3 368 out.appendln(answer) 369 } 370 } 371 print(out) 372 } 373 ``` 374 375 **Solution (Java) by qlf9** 376 377 ``` 378 import java.util.*; 379 import java.io.*; 380 381 public class OmkarAndBedWars { 382 public static void main(String[] args) throws IOException{ 383 BufferedReader f = new BufferedReader(new InputStreamReader(System.in)); 384 PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out)); 385 int t = Integer.parseInt(f.readLine()); 386 while(t-->0){ 387 int n = Integer.parseInt(f.readLine()); 388 String str = f.readLine(); 389 boolean same = true; 390 for(int i = 1; i < n; i++){ 391 if(str.charAt(i) != str.charAt(0)){ 392 same = false; 393 break; 394 } 395 } 396 if(same){ 397 out.println((n+2)/3); 398 continue; 399 } 400 ArrayList<Integer> count = new ArrayList<Integer>(); 401 int last = 0; 402 int cnt = 1; 403 for(int i = 1; i < n; i++){ 404 if(str.charAt(i) == str.charAt(last)){ 405 cnt++; 406 }else{ 407 count.add(cnt); 408 last = i; 409 cnt = 1; 410 } 411 } 412 if(str.charAt(n-1) == str.charAt(0)){ 413 count.set(0, count.get(0)+cnt); 414 }else{ 415 count.add(cnt); 416 } 417 int sum = 0; 418 for(int i: count) sum+=(i/3); 419 out.println(sum); 420 421 } 422 out.close(); 423 } 424 425 } 426 ``` 427 428 **Solution (C++) by Ari** 429 430 ``` 431 #include <bits/stdc++.h> 432 using namespace std; 433 434 void solve() { 435 int n, ans = 0; 436 cin >> n; 437 string s; 438 cin >> s; 439 int cnt = 0; 440 while(s.size() && s[0] == s.back()) { 441 cnt++; 442 s.pop_back(); 443 } 444 if(s.empty()) { 445 if(cnt <= 2) { 446 cout << "0\n"; 447 return; 448 } 449 if(cnt == 3) { 450 cout << "1\n"; 451 return; 452 } 453 cout << (cnt + 2) / 3 << '\n'; 454 return; 455 } 456 s.push_back('$'); 457 for(int i = 0; i + 1 < s.size(); i++) { 458 cnt++; 459 if(s[i] != s[i + 1]) { 460 ans += cnt / 3; 461 cnt = 0; 462 } 463 } 464 cout << ans << '\n'; 465 } 466 467 int main() { 468 ios_base::sync_with_stdio(false); 469 cin.tie(0); 470 471 int t; 472 cin >> t; 473 while(t--) 474 solve(); 475 } 476 ``` 477 478 Idea: [Tlatoani](/profile/Tlatoani "International Grandmaster Tlatoani") 479 480 Preparation: [Tlatoani](/profile/Tlatoani "International Grandmaster Tlatoani") 481 482 Tutorial is loading... 483 484 **Solution (Kotlin) by Tlatoani** 485 486 ``` 487 fun main() { 488 val n = readLine()!!.toInt() 489 for (x in 1..n) { 490 for (y in 1..n) { 491 if (x % 2 == 0) { 492 print(1L shl (x + y)) 493 } else { 494 print(0) 495 } 496 print(" ") 497 } 498 println() 499 } 500 val q = readLine()!!.toInt() 501 for (j in 1..q) { 502 val k = readLine()!!.toLong() 503 var x = 1 504 var y = 1 505 print("1 1 ") 506 for (e in 3..2 * n) { 507 if ((x % 2 == 0) == (((k shr e) % 2L) == 1L)) { 508 y++ 509 } else { 510 x++ 511 } 512 print("$x $y ") 513 } 514 println() 515 } 516 } 517 ``` 518 519 **Solution (Java) by golions** 520 521 ``` 522 //make sure to make new file! 523 import java.io.*; 524 import java.util.*; 525 526 public class DuckSolution{ 527 528 public static void main(String[] args)throws IOException{ 529 BufferedReader f = new BufferedReader(new InputStreamReader(System.in)); 530 PrintWriter out = new PrintWriter(System.out); 531 532 int n = Integer.parseInt(f.readLine()); 533 534 long[][] board = new long[n][n]; 535 board[0][0] = 0L; 536 board[n-1][n-1] = 0L; 537 538 for(int k = 0; k < n; k++){ 539 for(int j = 0; j < n; j++){ 540 if(k == 0 && j == 0) continue; 541 if(k == n-1 && j == n-1) continue; 542 543 if(k%2 == 0){ 544 board[k][j] = 1L << k+j; 545 } 546 } 547 } 548 549 for(int k = 0; k < n; k++){ 550 StringJoiner sj = new StringJoiner(" "); 551 for(int j = 0; j < n; j++){ 552 sj.add("" + board[k][j]); 553 } 554 out.println(sj.toString()); 555 } 556 557 out.flush(); 558 559 int q = Integer.parseInt(f.readLine()); 560 for(int t = 0; t < q; t++){ 561 long i = Long.parseLong(f.readLine()); 562 563 ArrayList<Integer> x = new ArrayList<Integer>(); 564 ArrayList<Integer> y = new ArrayList<Integer>(); 565 566 int curx = 0; 567 int cury = 0; 568 569 x.add(1); 570 y.add(1); 571 572 while(curx < n-1 || cury < n-1){ 573 if(curx == n-1){ 574 cury++; 575 } else if(cury == n-1){ 576 curx++; 577 } else { 578 long and = Math.max(board[curx+1][cury],board[curx][cury+1]); 579 if(((i & and) > 0) ^ (board[curx+1][cury] > 0)){ 580 cury++; 581 } else { 582 curx++; 583 } 584 585 586 } 587 588 x.add(curx+1); 589 y.add(cury+1); 590 } 591 592 StringJoiner sj = new StringJoiner(" "); 593 for(int k = 0; k < x.size(); k++){ 594 sj.add("" + x.get(k) + " " + y.get(k)); 595 } 596 out.println(sj.toString()); 597 out.flush(); 598 } 599 600 601 602 603 604 605 606 607 out.close(); 608 } 609 610 611 } 612 ``` 613 614 **Solution (C++) by hugopm** 615 616 ``` 617 #include <bits/stdc++.h> 618 #define len(v) ((int)((v).size())) 619 #define all(v) (v).begin(), (v).end() 620 #define rall(v) (v).rbegin(), (v).rend() 621 #define chmax(x, v) x = max((x), (v)) 622 #define chmin(x, v) x = min((x), (v)) 623 using namespace std; 624 using ll = long long; 625 626 int main() { 627 ios::sync_with_stdio(false); 628 cin.tie(0); 629 int side; cin >> side; 630 vector<vector<ll>> grid(side, vector<ll>(side, 0)); 631 for (int i = 0; i < side; ++i) { 632 for (int j = 0; j < side; ++j) { 633 if ((i-j+side)&2LL) grid[i][j] = (1LL << (i+j)); 634 cout << grid[i][j] << " \n"[j==side-1]; 635 } 636 } 637 cout << flush; 638 int nbQuery; cin >> nbQuery; 639 for (int iQuery = 0; iQuery < nbQuery; ++iQuery) { 640 ll sum; cin >> sum; 641 cout << "1 1"; 642 int row = 0, col = 0; 643 for (int diag = 0; diag < 2*side-2; ++diag) { 644 ll should = sum&(1LL<<(diag+1)); 645 if (row+1<side && grid[row+1][col] == should) ++row; 646 else ++col; 647 cout << " " << row+1 << " " << col+1; 648 } 649 cout << endl << flush; 650 } 651 } 652 ``` 653 654 Idea: [Tlatoani](/profile/Tlatoani "International Grandmaster Tlatoani") 655 656 Preparation: [Tlatoani](/profile/Tlatoani "International Grandmaster Tlatoani") and [malachi_toney_goat](/profile/malachi_toney_goat "Master malachi_toney_goat") 657 658 Tutorial is loading... 659 660 **EDIT:** The fact that the order of operations doesn't matter turned out to be harder to prove than I thought (thanks to the comments for pointing this out), so I decided to add the following proof: 661 662 If you have two sequences of maximal operations, then what we want to show is that they have to consist of the same operations (possibly in different orders). Since they are both maximal, they must either both be empty or both be nonempty. If they are both empty then we are done. 663 664 If they are both nonempty: consider the current state of the vector (before applying either sequence of operations). Since the sequences are nonempty, there is at least one operation $\alpha$ that can be immediately applied on the vector. 665 666 Here we should make the observation that applying an operation at some index cannot prevent operations at other indexes from being able to be applied (it can only allow other operations to be applied). 667 668 Therefore, applying other (different) operations cannot prevent operation $\alpha$ from being able to be applied, so operation $\alpha$ must occur in both sequences. From our observation, we can see that if, in either sequence, operation $\alpha$ does not occur initially, then operation $\alpha$ can be applied initially because by performing it earlier we are not preventing any of the operations in between from being applied. 669 670 Thus, the first operation of each sequence is now the same, so we can apply the same argument to the remainder of the sequence (since it must be finite). 671 672 **Solution (Kotlin) by Tlatoani** 673 674 ``` 675 import java.io.BufferedReader 676 import java.io.InputStreamReader 677 import java.util.* 678 679 fun main() { 680 val jin = BufferedReader(InputStreamReader(System.`in`)) 681 val n = jin.readLine().toLong() 682 val tokenizer = StringTokenizer(jin.readLine()) 683 var sum = 0L 684 for (j in 0L until n) { 685 sum += tokenizer.nextToken().toLong() - j 686 } 687 val joiner = StringJoiner(" ") 688 for (j in 0L until n) { 689 joiner.add(((sum / n) + (if (j < sum % n) 1L else 0L) + j).toString()) 690 } 691 println(joiner) 692 } 693 ``` 694 695 **Solution (Java) by qlf9** 696 697 ``` 698 import java.util.*; 699 import java.io.*; 700 701 public class OmkarAndLandslideNumber2 { 702 public static void main(String[] args) throws IOException{ 703 BufferedReader f = new BufferedReader(new InputStreamReader(System.in)); 704 PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out)); 705 long n = Long.parseLong(f.readLine()); 706 long sum = 0; 707 StringTokenizer st = new StringTokenizer(f.readLine()); 708 for(int i = 0; i < n; i++){ 709 sum+=Long.parseLong(st.nextToken()); 710 } 711 long k = ((sum - n*(n - 1)/2) / n); 712 long diff = sum - (n*k + n*(n - 1)/2); 713 StringBuilder ans = new StringBuilder(); 714 for(long i = 0; i < n; i++){ 715 if(i < diff){ 716 ans.append(k+i+1L); 717 ans.append(" "); 718 }else{ 719 ans.append(k+i); 720 ans.append(" "); 721 } 722 } 723 out.println(ans.toString().trim()); 724 out.close(); 725 } 726 } 727 ``` 728 729 **Solution (C++) by Devil** 730 731 ``` 732 #include <bits/stdc++.h> 733 734 using namespace std; 735 736 typedef long long ll; 737 738 int main() 739 { 740 ios_base::sync_with_stdio(0), cin.tie(0); 741 ll n; 742 cin >> n; 743 ll s = 0; 744 for (ll x, i = 0; i < n; ++i) 745 cin >> x, s += x; 746 747 ll l = (s - n * (n-1) / 2) / n + 1; 748 s = l * n + n * (n-1) / 2 - s; 749 for (int i = 0; i < n; ++i) 750 cout << l + i - (n-i <= s) << " \n"[i+1==n]; 751 752 return 0; 753 } 754 ``` 755 756 Idea: [Tlatoani](/profile/Tlatoani "International Grandmaster Tlatoani") 757 758 Preparation: [Tlatoani](/profile/Tlatoani "International Grandmaster Tlatoani") and [qlf9](/profile/qlf9 "Expert qlf9") 759 760 Tutorial is loading... 761 762 **Solution (Kotlin) by Tlatoani** 763 764 ``` 765 import java.io.BufferedReader 766 import java.io.InputStreamReader 767 import kotlin.math.max 768 import kotlin.math.min 769 770 fun main() { 771 val jin = BufferedReader(InputStreamReader(System.`in`)) 772 var line = jin.readLine().split(" ") 773 val n = line[0].toInt() 774 val m = line[1].toInt() 775 val k = line[2].toInt() 776 val dpLeft = IntArray(1 shl k) { n + 1 } 777 val dpRight = IntArray(1 shl k) { -1 } 778 var original = jin.readLine().reversed().toInt(2) 779 var goal = jin.readLine().reversed().toInt(2) 780 val permutation = IntArray(k) { it } 781 dpLeft[original] = 0 782 dpRight[goal] = 0 783 for (j in 1..n) { 784 line = jin.readLine().split(" ") 785 val a = line[0].toInt() - 1 786 val b = line[1].toInt() - 1 787 var c = (original shr permutation[a]) and 1 788 var d = (original shr permutation[b]) and 1 789 original -= c shl permutation[a] 790 original -= d shl permutation[b] 791 original += d shl permutation[a] 792 original += c shl permutation[b] 793 c = (goal shr permutation[a]) and 1 794 d = (goal shr permutation[b]) and 1 795 goal -= c shl permutation[a] 796 goal -= d shl permutation[b] 797 goal += d shl permutation[a] 798 goal += c shl permutation[b] 799 dpLeft[original] = min(dpLeft[original], j) 800 dpRight[goal] = j 801 c = permutation[a] 802 d = permutation[b] 803 permutation[a] = d 804 permutation[b] = c 805 } 806 var best = -1 807 var l = -1 808 var r = -1 809 for (mask in (1 shl k) - 1 downTo 0) { 810 for (e in 0 until k) { 811 if ((mask shr e) and 1 != 0) { 812 dpLeft[mask - (1 shl e)] = min(dpLeft[mask - (1 shl e)], dpLeft[mask]) 813 dpRight[mask - (1 shl e)] = max(dpRight[mask - (1 shl e)], dpRight[mask]) 814 } 815 } 816 if (dpLeft[mask] + m <= dpRight[mask] && Integer.bitCount(mask) > best) { 817 best = Integer.bitCount(mask) 818 l = dpLeft[mask] + 1 819 r = dpRight[mask] 820 } 821 } 822 println(k - Integer.bitCount(original) - Integer.bitCount(goal) + (2 * best)) 823 println("$l $r") 824 } 825 ``` 826 827 **Solution (Java) by qlf9** 828 829 ``` 830 import java.io.*; 831 import java.util.*; 832 833 public class OmkarAndPies { 834 public static int INF = Integer.MAX_VALUE/2; 835 public static void main(String[] args) throws IOException{ 836 BufferedReader f = new BufferedReader(new InputStreamReader(System.in)); 837 PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out)); 838 StringTokenizer st = new StringTokenizer(f.readLine()); 839 int n = Integer.parseInt(st.nextToken()); 840 int m = Integer.parseInt(st.nextToken()); 841 int k = Integer.parseInt(st.nextToken()); 842 int bitstr = Integer.parseInt(f.readLine(), 2); 843 int goal = Integer.parseInt(f.readLine(), 2); 844 int[] arr1 = new int[n]; 845 int[] arr2 = new int[n]; 846 for(int i = 0; i < n; i++){ 847 st = new StringTokenizer(f.readLine()); 848 arr1[i] = Integer.parseInt(st.nextToken()); 849 arr2[i] = Integer.parseInt(st.nextToken()); 850 } 851 int[] lefts = new int[n+1]; 852 int[] rights = new int[n+1]; 853 rights[0] = goal; 854 lefts[0] = bitstr; 855 int[] permutation = new int[k]; 856 int[] indices = new int[k]; 857 for(int i = 0; i < k; i++){ 858 permutation[i] = i; 859 indices[i] = i; 860 } 861 for(int i = 0; i < n; i++){ 862 int temp = indices[arr1[i]-1]; 863 indices[arr1[i]-1] = indices[arr2[i]-1]; 864 indices[arr2[i]-1] = temp; 865 permutation[indices[arr1[i]-1]] = arr1[i]-1; 866 permutation[indices[arr2[i]-1]] = arr2[i]-1; 867 lefts[i+1] = applyPermutation(indices, bitstr, k); 868 rights[i+1] = applyPermutation(indices, goal, k); 869 } 870 int[] dpLeft = new int[(1 << k)]; 871 int[] dpRight = new int[(1 << k)]; 872 Arrays.fill(dpLeft, INF); 873 Arrays.fill(dpRight, -INF); 874 for(int i = 0; i <= n; i++){ 875 dpLeft[lefts[i]] = Math.min(dpLeft[lefts[i]], i); 876 dpRight[rights[i]] = Math.max(dpRight[rights[i]], i); 877 } 878 for(int i = (1 << k)-1; i > 1; i--){ 879 int temp = i; 880 int count = 0; 881 while(temp != 0){ 882 if(temp % 2 == 1){ 883 dpLeft[i-(1 << count)] = Math.min(dpLeft[i-(1 << count)], dpLeft[i]); 884 dpRight[i-(1 << count)] = Math.max(dpRight[i-(1 << count)], dpRight[i]); 885 } 886 temp/=2; 887 count++; 888 } 889 } 890 for(int i = 0; i < (1 << k); i++){ 891 if(dpLeft[i] == 2 && dpRight[i] == 8){ 892 System.out.println(i); 893 } 894 } 895 int maxVal = -INF; 896 int intLeft = -1; 897 int intRight = -1; 898 for(int i = 0; i < (1 << k); i++){ 899 if(dpRight[i]-dpLeft[i] < m) continue; 900 int a1 = lefts[dpLeft[i]]; 901 int a2 = rights[dpRight[i]]; 902 int count = 0; 903 for(int j = 0; j < k; j++){ 904 if(a1 % 2 == a2 % 2) count++; 905 a1/=2; 906 a2/=2; 907 } 908 if(count > maxVal){ 909 maxVal = count; 910 intLeft = dpLeft[i]+1; 911 intRight = dpRight[i]; 912 } 913 } 914 out.println(maxVal); 915 out.println(intLeft + " " + intRight); 916 out.close(); 917 918 } 919 public static int applyPermutation(int[] permutation, int bitstr, int k){ 920 int ans = 0; 921 for(int i = k-1; i >= 0; i--){ 922 if(bitstr % 2 == 1){ 923 ans += (1 << (k-permutation[i]-1)); 924 } 925 bitstr/=2; 926 } 927 return ans; 928 } 929 } 930 ``` 931 932 **Solution (C++) by mohammedehab2002** 933 934 ``` 935 #include <bits/stdc++.h> 936 using namespace std; 937 int p[20],dp[2][(1<<20)]; 938 int getmask(string s) 939 { 940 int ans=0; 941 for (int i=0;i<s.size();i++) 942 ans|=((s[i]-'0')<<i); 943 return ans; 944 } 945 int main() 946 { 947 int n,m,k; 948 scanf("%d%d%d",&n,&m,&k); 949 string a,b; 950 cin >> a >> b; 951 for (int i=0;i<k;i++) 952 p[i]=i; 953 for (int i=0;i<(1<<k);i++) 954 { 955 dp[0][i]=1e9; 956 dp[1][i]=-1e9; 957 } 958 dp[0][getmask(a)]=0; 959 dp[1][getmask(b)]=0; 960 for (int i=1;i<=n;i++) 961 { 962 int x,y; 963 scanf("%d%d",&x,&y); 964 x--; 965 y--; 966 swap(p[x],p[y]); 967 string aa(k,'0'),bb(k,'0'); 968 for (int j=0;j<k;j++) 969 { 970 aa[p[j]]=a[j]; 971 bb[p[j]]=b[j]; 972 } 973 dp[0][getmask(aa)]=min(dp[0][getmask(aa)],i); 974 dp[1][getmask(bb)]=i; 975 } 976 int o1=count(a.begin(),a.end(),'1'),o2=count(b.begin(),b.end(),'1'); 977 pair<int,pair<int,int> > ans(0,{0,0}); 978 for (int i=(1<<k)-1;i>=0;i--) 979 { 980 if (dp[1][i]-dp[0][i]>=m) 981 ans=max(ans,make_pair(k-(o1+o2-2*__builtin_popcount(i)),make_pair(dp[0][i]+1,dp[1][i]))); 982 for (int j=0;j<k;j++) 983 { 984 if (i&(1<<j)) 985 { 986 dp[0][i^(1<<j)]=min(dp[0][i^(1<<j)],dp[0][i]); 987 dp[1][i^(1<<j)]=max(dp[1][i^(1<<j)],dp[1][i]); 988 } 989 } 990 } 991 printf("%d\n%d %d",ans.first,ans.second.first,ans.second.second); 992 } 993 ``` 994 995 Idea: [Tlatoani](/profile/Tlatoani "International Grandmaster Tlatoani") 996 997 Preparation: [Tlatoani](/profile/Tlatoani "International Grandmaster Tlatoani") 998 999 Tutorial is loading... 1000 1001 **Solution (C++) by zscoder** 1002 1003 ``` 1004 #include <bits/stdc++.h> 1005 #include <ext/pb_ds/assoc_container.hpp> 1006 #include <ext/pb_ds/tree_policy.hpp> 1007 1008 using namespace std; 1009 using namespace __gnu_pbds; 1010 1011 #define fi first 1012 #define se second 1013 #define mp make_pair 1014 #define pb push_back 1015 #define fbo find_by_order 1016 #define ook order_of_key 1017 1018 typedef long long ll; 1019 typedef pair<ll,ll> ii; 1020 typedef vector<int> vi; 1021 typedef long double ld; 1022 typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds; 1023 1024 const int MOD = 998244353; 1025 1026 vector<int> fact; 1027 vector<int> ifact; 1028 vector<int> pow2; 1029 int add(int a, int b) 1030 { 1031 a+=b; 1032 while(a>=MOD) a-=MOD; 1033 return a; 1034 } 1035 void radd(int &a, int b) 1036 { 1037 a=add(a,b); 1038 } 1039 int mult(int a, int b) 1040 { 1041 return (a*1LL*b)%MOD; 1042 } 1043 void rmult(int &a, int b) 1044 { 1045 a=mult(a,b); 1046 } 1047 int modpow(int a, int b) 1048 { 1049 int r=1; 1050 while(b) 1051 { 1052 if(b&1) r=mult(r,a); 1053 a=mult(a,a); 1054 b>>=1; 1055 } 1056 return r; 1057 } 1058 int choose(int a, int b) 1059 { 1060 if(a<0) return 0; 1061 if(b<0) return 0; 1062 if(a<b) return 0; 1063 if(b==0) return 1; 1064 if(a==b) return 1; 1065 return mult(fact[a],mult(ifact[b],ifact[a-b])); 1066 } 1067 int inverse(int a) 1068 { 1069 return modpow(a,MOD-2); 1070 } 1071 void init(int _n) 1072 { 1073 fact.clear(); ifact.clear(); pow2.clear(); 1074 fact.resize(_n+1); 1075 ifact.resize(_n+1); 1076 pow2.resize(_n+1); 1077 pow2[0]=1; 1078 ifact[0]=1; 1079 fact[0]=1; 1080 for(int i=1;i<=_n;i++) 1081 { 1082 pow2[i]=add(pow2[i-1],pow2[i-1]); 1083 fact[i]=mult(fact[i-1],i); 1084 //ifact[i]=mult(ifact[i-1],inv[i]); 1085 } 1086 ifact[_n] = inverse(fact[_n]); 1087 for(int i=_n-1;i>=1;i--) 1088 { 1089 ifact[i] = mult(ifact[i + 1], i + 1); 1090 } 1091 } 1092 1093 int solve_slow(int n, int m) 1094 { 1095 vi f(n+1,0); 1096 for(int k=1;k<=n;k++) 1097 { 1098 int sum=0; 1099 for(int l=1;l<=k;l++) 1100 { 1101 for(int i=0;i<=n;i++) 1102 { 1103 int coeff = mult(mult(choose(k,l),mult(choose(n-k,i-l), mult(fact[i], mult(m, fact[n+m-i-1])))), ifact[n+m]); 1104 radd(sum, mult(coeff, add(f[k-l],i+1))); 1105 } 1106 } 1107 { 1108 int l=0; 1109 int sumcoeff=0; 1110 for(int i=0;i<=n;i++) 1111 { 1112 int coeff = mult(mult(choose(k,l),mult(choose(n-k,i-l), mult(fact[i], mult(m, fact[n+m-i-1])))), ifact[n+m]); 1113 radd(sum, mult(coeff, i+1)); 1114 radd(sumcoeff,coeff); 1115 } 1116 int actualcoeff = add(1,MOD-sumcoeff); 1117 assert(actualcoeff!=0); 1118 f[k]=mult(inverse(actualcoeff),sum); 1119 } 1120 } 1121 return f[n]; 1122 } 1123 1124 int solve_fast(int n, int m) 1125 { 1126 vi f(n+1,0); 1127 int presum=0; 1128 for(int k=1;k<=n;k++) 1129 { 1130 int sum=mult(presum,choose(n+m,m+k)); 1131 radd(sum,mult(fact[m-1],mult(choose(m+k+1,m+1),choose(n+m+1,m+k+1)))); 1132 int outsidecoeff = mult(fact[k],mult(fact[n-k],mult(ifact[n+m],m))); 1133 sum = mult(sum, outsidecoeff); 1134 f[k]=mult(mult(m+k,mult(ifact[k],fact[k-1])),sum); 1135 //f[k]=mult(mult(k,mult(fact[m+k-1],ifact[m+k])),sum); 1136 radd(presum,mult(fact[m+k-1],mult(ifact[k],f[k]))); 1137 } 1138 return f[n]; 1139 } 1140 1141 int main() 1142 { 1143 ios_base::sync_with_stdio(0); cin.tie(0); 1144 init(int(1e7)+100); 1145 int n,m; cin>>n>>m; 1146 //cout<<solve_slow(n,m)<<'\n'; 1147 cout<<solve_fast(n,m)<<'\n'; 1148 } 1149 ``` 1150 1151 **Solution (Java) by qlf9** 1152 1153 ``` 1154 import java.util.*; 1155 import java.io.*; 1156 1157 public class ZSShufflesCards { 1158 public static long MOD = 998244353; 1159 public static long[] fact; 1160 public static long[] invfact; 1161 public static long[] pow2; 1162 public static int MAX = 4000005; 1163 public static void main(String[] args) throws IOException{ 1164 BufferedReader f = new BufferedReader(new InputStreamReader(System.in)); 1165 PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out)); 1166 StringTokenizer st = new StringTokenizer(f.readLine()); 1167 int n = Integer.parseInt(st.nextToken()); 1168 int m = Integer.parseInt(st.nextToken()); 1169 fact = new long[MAX]; 1170 invfact = new long[MAX]; 1171 pow2 = new long[MAX]; 1172 fact[0] = 1; 1173 invfact[0] = 1; 1174 pow2[0] = 1; 1175 for(int i = 1; i < MAX; i++){ 1176 pow2[i] = add(pow2[i-1], pow2[i-1]); 1177 fact[i] = mult(fact[i-1], i); 1178 } 1179 invfact[MAX-1] = inverse(fact[MAX-1]); 1180 for(int i = MAX-2; i >= 1; i--){ 1181 invfact[i] = mult(invfact[i+1], i+1); 1182 } 1183 long[] ans = new long[n+1]; 1184 long currsum = 0; 1185 for(int k = 1; k <= n; k++){ 1186 long sum = mult(currsum, ncr(n+m, m+k)); 1187 sum = add(sum,mult(fact[m-1],mult(ncr(m+k+1,m+1),ncr(n+m+1,m+k+1)))); 1188 long outsidecoeff = mult(fact[k],mult(fact[n-k],mult(invfact[n+m],m))); 1189 sum = mult(sum, outsidecoeff); 1190 ans[k]=mult(mult(m+k,mult(invfact[k],fact[k-1])),sum); 1191 currsum = add(currsum,mult(fact[m+k-1],mult(invfact[k],ans[k]))); 1192 } 1193 out.println(ans[n]); 1194 out.close(); 1195 1196 } 1197 public static long add(long a, long b){ 1198 return((a+b)%MOD+MOD)%MOD; 1199 } 1200 public static long mult(long a, long b){ 1201 return((a*b)%MOD+MOD)%MOD; 1202 } 1203 public static long pow(long a, long b){ 1204 long ans = 1; 1205 while(b > 0){ 1206 if((b&1) == 1) ans = mult(ans, a); 1207 a = mult(a, a); 1208 b>>=1; 1209 } 1210 return ans; 1211 } 1212 public static long ncr(long a, long b){ 1213 if(a<0) return 0; 1214 if(b<0) return 0; 1215 if(a<b) return 0; 1216 if(b==0) return 1; 1217 if(a==b) return 1; 1218 return mult(fact[(int)a],mult(invfact[(int)b],invfact[(int)(a-b)])); 1219 } 1220 public static long inverse(long a){ 1221 return pow(a, MOD-2); 1222 } 1223 } 1224 ``` 1225 1226 **Solution (Kotlin) by Tlatoani** 1227 1228 ``` 1229 const val MOD = 998244353L 1230 1231 fun main() { 1232 val (n, m) = readLine()!!.split(" ").map { it.toInt() } 1233 val factorial = LongArray(4000002) 1234 factorial[0] = 1L 1235 for (j in 1..4000001) { 1236 factorial[j] = (j.toLong() * factorial[j - 1]) % MOD 1237 } 1238 val factInv = LongArray(4000002) 1239 factInv[4000001] = factorial[4000001] pow -1 1240 for (j in 4000000 downTo 0) { 1241 factInv[j] = ((j + 1).toLong() * factInv[j + 1]) % MOD 1242 } 1243 fun choose(a: Int, b: Int) = if (a < 0 || b < 0 || b > a) 0L else (factorial[a] * ((factInv[b] * factInv[a - b]) % MOD)) % MOD 1244 val answer = LongArray(n + 1) 1245 var currSum = 0L 1246 for (k in 1..n) { 1247 var sum = currSum * choose(n + m, m + k) 1248 sum %= MOD 1249 sum += factorial[m - 1] * ((choose(m + k + 1, m + 1) * choose(n + m + 1, m + k + 1)) % MOD) 1250 sum %= MOD 1251 sum *= (factorial[k] * ((factorial[n - k] * ((factInv[n + m] * m.toLong()) % MOD)) % MOD)) % MOD 1252 sum %= MOD 1253 answer[k] = sum * (((m + k).toLong() * ((factInv[k] * factorial[k - 1]) % MOD)) % MOD) 1254 answer[k] %= MOD 1255 currSum += factorial[m + k - 1] * ((factInv[k] * answer[k]) % MOD) 1256 currSum %= MOD 1257 } 1258 println(answer[n]) 1259 } 1260 1261 const val MOD_TOTIENT = MOD.toInt() - 1 1262 1263 infix fun Long.pow(power: Int): Long { 1264 var e = power 1265 e %= MOD_TOTIENT 1266 if (e < 0) { 1267 e += MOD_TOTIENT 1268 } 1269 if (e == 0 && this == 0L) { 1270 return this 1271 } 1272 var b = this % MOD 1273 var res = 1L 1274 while (e > 0) { 1275 if (e and 1 != 0) { 1276 res *= b 1277 res %= MOD 1278 } 1279 b *= b 1280 b %= MOD 1281 e = e shr 1 1282 } 1283 return res 1284 } 1285 ``` 1286 1287 Idea: [zscoder](/profile/zscoder "International Grandmaster zscoder") 1288 1289 Preparation: [zscoder](/profile/zscoder "International Grandmaster zscoder") 1290 1291 Tutorial is loading... 1292 1293 **Solution (C++) by KLPP** 1294 1295 ``` 1296 #include<bits/stdc++.h> 1297 1298 using namespace std; 1299 #define MAX 262144 1300 #define MAXN 1000000 1301 long long int a[MAXN],b[MAXN]; 1302 1303 using cd = complex<double>; 1304 const double PI = acos(-1); 1305 vector<cd> A(MAX),B(MAX); 1306 vector<cd> Amx(MAX),Bmx(MAX); 1307 vector<cd> Amn(MAX),Bmn(MAX); 1308 vector<cd> E11(MAX),E12(MAX),E21(MAX),E22(MAX); 1309 vector<cd> SQ1(MAX),SQ2(MAX); 1310 vector<cd> V(MAX); 1311 vector<long long int> A1(MAX),A2(MAX); 1312 1313 void fft(vector<cd> & a, bool invert) { 1314 int n = a.size(); 1315 1316 for (int i = 1, j = 0; i < n; i++) { 1317 int bit = n >> 1; 1318 for (; j & bit; bit >>= 1) 1319 j ^= bit; 1320 j ^= bit; 1321 1322 if (i < j) 1323 swap(a[i], a[j]); 1324 } 1325 1326 for (int len = 2; len <= n; len <<= 1) { 1327 double ang = 2 * PI / len * (invert ? -1 : 1); 1328 cd wlen(cos(ang), sin(ang)); 1329 for (int i = 0; i < n; i += len) { 1330 cd w(1); 1331 for (int j = 0; j < len / 2; j++) { 1332 cd u = a[i+j], v = a[i+j+len/2] * w; 1333 a[i+j] = u + v; 1334 a[i+j+len/2] = u - v; 1335 w *= wlen; 1336 } 1337 } 1338 } 1339 1340 if (invert) { 1341 for (cd & x : a) 1342 x /= n; 1343 } 1344 } 1345 void prod(vector<cd> &a, vector<cd> &b, vector<cd> &c){ 1346 for(int i=0;i<a.size();i++){ 1347 c[i]=a[i]*b[i]; 1348 } 1349 } 1350 1351 int main(){ 1352 long long int n,m,q; 1353 scanf("%lld %lld %lld",&n,&m,&q); 1354 1355 for(int i=0;i<n;i++){ 1356 scanf("%lld",&a[i]); 1357 } 1358 for(int i=0;i<m;i++){ 1359 scanf("%lld",&b[i]); 1360 } 1361 for(int i=0;i<MAX;i++){ 1362 A[i]=cd(0,0); 1363 Amn[i]=cd(0,0); 1364 Amx[i]=cd(0,0); 1365 B[i]=cd(0,0); 1366 Bmn[i]=cd(0,0); 1367 Bmx[i]=cd(0,0); 1368 } 1369 for(int i=0;i<n;i++){ 1370 A[a[i]]+=cd(1,0); 1371 } 1372 for(int i=0;i<n-1;i++){ 1373 Amn[min(a[i],a[i+1])]+=cd(1,0); 1374 } 1375 for(int i=0;i<n-1;i++){ 1376 Amx[max(a[i],a[i+1])]+=cd(1,0); 1377 } 1378 for(int i=0;i<m;i++){ 1379 B[b[i]]+=cd(1,0); 1380 } 1381 for(int i=0;i<m-1;i++){ 1382 Bmn[min(b[i],b[i+1])]+=cd(1,0); 1383 } 1384 for(int i=0;i<m-1;i++){ 1385 Bmx[max(b[i],b[i+1])]+=cd(1,0); 1386 } 1387 1388 fft(A,0); 1389 fft(Amn,0); 1390 fft(Amx,0); 1391 fft(B,0); 1392 fft(Bmn,0); 1393 fft(Bmx,0); 1394 prod(A,Bmn,E11); 1395 prod(Amn,B,E12); 1396 prod(Amx,B,E21); 1397 prod(A,Bmx,E22); 1398 prod(Amn,Bmn,SQ1); 1399 prod(Amx,Bmx,SQ2); 1400 prod(A,B,V); 1401 fft(E11,1); 1402 fft(E12,1); 1403 fft(E21,1); 1404 fft(E22,1); 1405 fft(SQ1,1); 1406 fft(SQ2,1); 1407 fft(V,1); 1408 for(int i=0;i<MAX;i++){ 1409 A1[i]=round(SQ1[i].real())-round(E11[i].real())-round(E12[i].real())+round(V[i].real()); 1410 A2[i]=round(SQ2[i].real())-round(E21[i].real())-round(E22[i].real())+round(V[i].real()); 1411 } 1412 for(int i=1;i<MAX;i++){ 1413 A2[i]+=A2[i-1]; 1414 } 1415 for(int i=MAX-2;i>-1;i--){ 1416 A1[i]+=A1[i+1]; 1417 } 1418 for(int i=0;i<q;i++){ 1419 int query; 1420 scanf("%d",&query); 1421 //cout<<A1[query]<<" "<<A2[query-1]<<endl; 1422 printf("%lld\n",A1[query]-A2[query-1]); 1423 } 1424 return 0; 1425 } 1426 ``` 1427 1428 Idea: [KLPP](/profile/KLPP "Master KLPP") 1429 1430 Preparation: [KLPP](/profile/KLPP "Master KLPP")