1498.md (36003B)
1 Source: https://codeforces.com/blog/entry/89137 2 3 # [1498A - GCD Sum](/contest/1498/problem/A "CodeCraft-21 and Codeforces Round 711 (Div. 2)") 4 5 #### [**Video Editorial**](https://www.youtube.com/watch?v=lV5cb8wh3sE) 6 7 **Author and Problemsetting:** [ninja_28](/profile/ninja_28 "Candidate Master ninja_28") 8 **Editorialist:** [sigma_g](/profile/sigma_g "Master sigma_g") 9 10 **Hint** 11 12 Can you think of the simplest properties that relate a number and its sum of digits? 13 14 **Hint 2** 15 16 Note that if $X$ is a multiple of 3, then **both** $X$ as well as the sum of digits of $X$ are a multiple of 3! Can you put this property to use here? 17 18 **Hint 3** 19 20 If $X$ is a multiple of 3, then $\texttt{gcd-sum}(X) \ge 3$. Therefore, we are guaranteed that at least every third number will satisfy the constraints required by our problem $(\texttt{gcd-sum}(X) \gt 1)$. 21 22 **Solution** 23 24 Therefore, for the input $n$, we can simply check which one of $n$, $n+1$, and $n+2$ has its gcd-sum $ \gt 1$, and print the lowest of them. 25 26 **Corner cases** 27 28 Note that you must take `long long`, as input integers exceed the range of int. 29 30 Moreover, simply outputting $\text{ceil}((n / 3) \times 3)$ is incorrect as some non-multiples of three may also may have gcd-sum $ \gt 1$, for example, 26. 31 32 **C++ solution** 33 34 ``` 35 #include <bits/stdc++.h> 36 using namespace std; 37 38 long long int gcd_sum(long long int num) { 39 // returns gcd-sum 40 long long int tmp = num, digitsum = 0; 41 42 while (tmp > 0) { 43 digitsum += tmp % 10; 44 tmp /= 10; 45 } 46 47 long long int gcd = __gcd(num, digitsum); 48 return gcd; 49 } 50 51 int main(void) { 52 int t; 53 cin >> t; 54 55 while (t--) { 56 long long int n; 57 cin >> n; 58 if (gcd_sum(n) != 1) { 59 cout << n << endl; 60 } else if (gcd_sum(n + 1) != 1) { 61 cout << n + 1 << endl; 62 } else if (gcd_sum(n + 2) != 1) { 63 cout << n + 2 << endl; 64 } 65 } 66 return 0; 67 } 68 ``` 69 70 **Python solution** 71 72 ``` 73 from math import gcd 74 75 def valid(x): 76 return gcd(x, sum([ord(c) - ord('0') for c in str(x)])) != 1 77 78 t = int(input()) 79 80 while t > 0: 81 t -= 1 82 83 n = int(input()) 84 while not valid(n): 85 n += 1 86 87 print(n) 88 ``` 89 90 # [1498B - Box Fitting](/contest/1498/problem/B "CodeCraft-21 and Codeforces Round 711 (Div. 2)") 91 92 #### [**Video Editorial**](https://www.youtube.com/watch?v=gC4dcf1PN40) 93 94 **Author and Editorialist:** [sigma_g](/profile/sigma_g "Master sigma_g") 95 **Problemsetting:** [ninja_28](/profile/ninja_28 "Candidate Master ninja_28") 96 97 **Hint** 98 99 There can exist multiple optimal packings for a given set of rectangles. However, all of them can always be rearranged to follow a specific pattern, based on the rectangles' sizes. 100 101 **Hint 2** 102 103 Can you show that it is always possible to replace a set of consecutive small blocks with a single large block? (of same or larger size) 104 105 **Solution summary** 106 107 We follow a greedy strategy: 108 109 1. Initialize height of box as 1. 110 2. Initialize current layer size as $W$. 111 3. Pick the largest available rectangle that can fit into the current layer, and place it there. Repeat until this layer cannot fit any more rectangles. 112 4. If more rectangles remain, increment height by 1 and now repeat the last three steps. Else, output the current value of height. 113 114 **Solution implementation** 115 116 First count sort the given rectangles based on their widths. There can only be 20 distinct rectangle widths in the range $[1, 10^9]$, so the following works: 117 118 ``` 119 counts = [0 for w in range(0, 20)] 120 for w in widths: 121 counts[log2(w)] += 1 122 ``` 123 124 The solution can be implemented by iterating $N$ times. 125 126 At each iteration, step through the `counts` array and take the largest available rectangle that can fit into the current space. If no rectangle was able to fit, increment height by 1 and reset box width to $W$. 127 128 This has complexity $\mathcal{O}(n\log(w_\text{max}))$. 129 130 **Another implementation** 131 132 It is also possible to implement the solution with a `multiset` and `upper_bound`, for a complexity of $\mathcal{O}(n\log(n))$. 133 134 Store all rectangle sizes in a multiset. At each iteration, find using `upper_bound` the largest rectangle that can fit into the current space we have, and fit it in. If no rectangle can fit in this space, reset the space to maximum, increment height, and repeat. 135 136 **Proof of correctness - brief** 137 138 It is always possible to replace several smaller blocks with a single larger block if it is available. Because all blocks are powers of two, it must so happen that smaller powers of two will sum to a larger power. Therefore, we can always place a larger block first if it can be placed there. 139 140 **Proof of correctness - elaborate** 141 142 This elaborate proof isn't actually required for solving the problem. The intuition in the brief proof is sufficient for solving the problem. This proof is for correctness purpose only. 143 144 Let's first note a property: if $a_1 + \ldots + a_n \gt a_0$, then there exists some $i$ such that $a_1+ \ldots +a_i=a_0$, when all $a_i$ are powers of 2 AND $a_1$ to $a_n$ is a non-increasing sequence (AND $a_1 \lt = a_0$, of course). Why is this so? You can take an example and observe this intuitively, this is a common property of powers of two. For example, $4+2+2+1+1 \gt 8$, but $4+2+2$ (prefix) $=8$. Formally: if $a_1 =a_0$, this property is trivially true. If $a_1 \lt a_0$, we can splilt $a_0=2^ka_1$ for some $k$ into $2^k$ parts and — by strong induction — claim this property holds. 145 146 Let us now compare some optimal solution and our greedy solution. Before comparing, we first sort all blocks in each layer of the optimal solution in decreasing order. This does not affect the final answer but helps in our comparison. This comparison goes from bottom to top, left to right. Let us look at the first point of difference: when the block placed by us ($B_G$) is different from the block placed by the optimal solution ($B_O$). There are three cases. 147 148 If $B_O \gt B_G$: this is impossible, as in our greedy solution, we are always placing the largest possible block. We wouldn't place $B_G$ in there if $B_O$ was also possible. If $B_O == B_G$: we have nothing to worry about (this isn't a point of difference) 149 150 If $B_O \lt B_G$: let us assume that the optimal solution places several consecutive small blocks, and not just one $B_O$. Since the blocks are in decreasing order, none of them would be bigger than $B_G$. Note that either all of these blocks will sum to less than $B_G$ or a prefix of them will be exactly equal to $B_G$. In either case, we can swap them with one single large block $B_G$ (swapping with a $B_G$ which was placed in some higher layer in the optimal solution) 151 152 Hence, in the last case, we have shown that any optimal solution (an arrangement of blocks) can be rearranged such that each layer fits the largest possible block first. This is also what is done in our greedy strategy. Therefore, with this proof by rearrangement, we conclude that our greedy strategy gives the same minimum height as that of the optimal answer. 153 154 **Alternate implementation with easier proof** 155 156 There is a binary search method to solve this problem. We binary search for the minimum height required. Given a height $h$ — how to check if it can fit all rectangles? 157 158 We first preprocess the given array to construct a new array $c_i$ = number of rectangles of width $1 « i$. The size of this array is < 20. 159 160 We iterate from largest width to smallest width. Let its width is $w_i$. Then, we know that it fits only $W / w_i$ times in one layer. Therefore, with height $h$, the box can only fit in $f_i = h \times (W / w_i)$. So, we can say that if $f_i \lt c_i$, then this height is insufficient. 161 162 Therefore, we now know that for any $i$, if $f_i \lt c_i$, then the height is insufficient. Do we need more conditions to provably state that the given height is sufficient? 163 164 Yes! We also need to check if we can fit in the $i$-th block *in combination with* tthe $i+1$-th block. That is, when checking if the $i$-th block has enough space, we need to account for the space that **has already been used** by the $i + 1$-th block. So, we need to update $c_i = c_i + 2\times c_{i+1} + 4\times c_{i+2} \ldots$. 165 166 Therefore, we only need to compute the suffix sum $c_i$ like so and then check the above conditions. Complexity is $\mathcal{O}(n+\log(w_{max})\log(n))$. 167 168 **Does this solution work when block widths are not a power of two?** 169 170 As we understood in the proof, this solution only works when it's guaranteed that smaller blocks will always exactly sum to any larger block. Therefore, if the blocks are not powers of two, this guarantee does not hold. 171 172 The following counterexample suffices: 173 174 ``` 175 6 13 176 6 6 4 4 3 3 177 ``` 178 179 As you can see here the smaller blocks are not guaranteed to sum to the larger block (no prefix of $4,3,3$ sums to $6$). Our greedy solution gives minimum height 3, but best possible minimum height is $2$ (first layer: $6,4,3$, second layer: $6,4,3$) 180 181 **C++ solution** 182 183 ``` 184 #include <cmath> 185 #include <iostream> 186 #include <vector> 187 using namespace std; 188 189 int main() { 190 int t; 191 cin >> t; 192 193 while (t--) { 194 int n, box_width, w; 195 cin >> n >> box_width; 196 197 vector<int> counts(20); 198 for (int i = 0; i < n; i++) { 199 cin >> w; 200 counts[log2(w)]++; 201 } 202 203 int height = 1, space_left = box_width; 204 205 for (int iter = 0; iter < n; iter++) { 206 int largest = -1; 207 208 for (int size = 19; size >= 0; size--) { 209 if (counts[size] and (1 << size) <= space_left) { 210 largest = size; 211 break; 212 } 213 } 214 215 if (largest == -1) { 216 space_left = box_width; 217 height++; 218 for (int size = 19; size >= 0; size--) { 219 if (counts[size] and (1 << size) <= space_left) { 220 largest = size; 221 break; 222 } 223 } 224 } 225 226 counts[largest] -= 1; 227 space_left -= 1 << largest; 228 } 229 230 cout << height << endl; 231 } 232 233 } 234 ``` 235 236 **Python solution** 237 238 ``` 239 from math import log2 240 241 def solve_tc(): 242 n, w = list(map(int, input().split())) 243 widths = list(map(int, input().split())) 244 245 counts = [0 for _ in range(20)] 246 247 for width in widths: 248 counts[int(log2(width))] += 1 249 250 space = w 251 height = 1 252 253 for it in range(n): 254 largest = -1 255 256 for size, count_width in list(enumerate(counts))[::-1]: 257 if counts[size] > 0 and (2 ** size) <= space: 258 largest = size 259 break 260 261 if largest == -1: 262 space = w 263 height += 1 264 265 for size, count_width in list(enumerate(counts))[::-1]: 266 if counts[size] > 0 and (2 ** size) <= space: 267 largest = size 268 break 269 270 assert(largest != -1) 271 counts[largest] -= 1 272 space -= 2 ** largest 273 274 print(height) 275 276 t = int(input()) 277 278 while t > 0: 279 t -= 1 280 281 solve_tc() 282 ``` 283 284 **C++ solution - multiset** 285 286 ``` 287 #include <bits/stdc++.h> 288 using namespace std; 289 290 int main() { 291 int t; 292 cin >> t; 293 294 while (t--) { 295 int n, w; 296 int box_width; 297 cin >> n >> box_width; 298 299 multiset<int> st; 300 for (int i = 0; i < n; i++) { 301 cin >> w; 302 st.insert(w); 303 } 304 305 int height = 1, space_left = box_width; 306 307 while (!st.empty()) { 308 auto it = st.upper_bound(space_left); 309 if (it != st.begin()) { 310 it--; 311 int val = *it; 312 space_left -= val; 313 st.erase(it); 314 } else { 315 space_left = box_width; 316 height++; 317 } 318 } 319 320 cout << height << endl; 321 } 322 return 0; 323 324 } 325 ``` 326 327 **C++ solution for easier proof** 328 329 ``` 330 #include <array> 331 #include <cassert> 332 #include <cmath> 333 #include <iostream> 334 using namespace std; 335 336 #define PW 20 337 array<int, PW> arr; 338 int n, w; 339 340 bool valid(int height) { 341 for (int pw = 0; pw < PW; pw++) { 342 long long units_i_have = 1ll * height * (w / (1 << pw)); 343 if (units_i_have < arr[pw]) return false; 344 } 345 346 return true; 347 } 348 349 int main() { 350 int t; cin >> t; 351 352 while (t--) { 353 cin >> n >> w; 354 355 for (int i = 0; i < PW; i++) arr[i] = 0; 356 357 for (int _ = 0; _ < n; _++) { 358 int w; cin >> w; 359 arr[log2(w)] += 1; 360 } 361 362 // suffix cumulative count 363 for (int i = PW - 2; i >= 0; i--) arr[i] += 2 * arr[i + 1]; 364 365 int beg = 1, end = n, ans = -1; 366 while (beg <= end) { 367 int mid = (beg + end) / 2; 368 369 if (valid(mid)) { 370 end = mid - 1; 371 ans = mid; 372 } else { 373 beg = mid + 1; 374 } 375 } 376 377 assert(ans != -1); 378 cout << ans << endl; 379 } 380 } 381 ``` 382 383 # [1498C - Planar Reflections](/contest/1498/problem/C "CodeCraft-21 and Codeforces Round 711 (Div. 2)") 384 385 #### [**Video Editorial**](https://www.youtube.com/watch?v=VFNzluTWIBc) 386 387 **Author, Problemsetter and Editorialist:** [sigma_g](/profile/sigma_g "Master sigma_g") 388 389 **Hint 1** 390 391 We can use dynamic programming to store the state of the simulation at a given time. Therefore, we can simulate the entire situation by reusing the dp states. 392 393 **Solution idea** 394 395 I will describe the most intuitive solution. Naturally, looking at the constraints as well as at the output that is required, we can store a 3-state dp: `dp[n][k][2]`. Here, `dp[n][k][d]` indicates the total number of particles (at the end of the simulation) when one particle of decay age $k$ hits the $n$-th plane in the direction $d$. ($d$ is either $0$ or $1$, and indicates the direction (left/right) in which the particle is going) 396 397 There can be two directions, $N$ planes and maximum decay age is $K$. So, this dp requires $2\times1000\times1000\times4$ bytes $\approx 24MB$ which is well within our memory constraints. 398 399 **Solution details** 400 401 How to update the DP states? If $k = 1$, the value of `dp[n][1][d]` for any $n$ or $d$ is obviously $1$ (as no copies are produced). 402 403 So, let us consider a particle $P$ with $k \gt 1$. This particle $P$ produces a copy $P'$ going in the opposite direction. We can count the number of particles produced by $P'$ as `dp[n - 1][k - 1][1 - d]`, as it hits the previous plane with a smaller decay age and in the opposite direction. Moreover, the particle $P$ itself hits the next plane and continues to produce more stuff. We can calculate its number of particles produced as `dp[n + 1][k][d]`, as it hits the next plane with the same decay age and the same direction! 404 405 Finally, we can combine these two values to get the value of `dp[n][k][d]`. 406 407 **Implementation details** 408 409 We can implement this is easily as a recursive dp with memoization. At each state, we only need to iterate in the correct order (in one case, from right to left, and in the other, from left to right), and update states as required. Look at the implementation for more details. The total complexity of this algorithm is $\mathcal{O}(nk)$ 410 411 **Note** 412 413 Obviously, there exist much better solutions which do not use a third state and are much sleaker. However, I wanted to describe the simplest idea required to solve the problem. 414 415 **C++ solution** 416 417 ``` 418 #include <cstring> 419 #include <iostream> 420 #include <vector> 421 422 using namespace std; 423 424 const int N = 1001; 425 const int K = 1001; 426 427 int n, k; 428 const int mod = 1e9 + 7; 429 430 int dp[N][K][2]; 431 432 int solve(int curr, int k, int dir) { 433 if (k == 1) { 434 return 1; 435 } 436 437 if (dp[curr][k][dir] != -1) { 438 return dp[curr][k][dir]; 439 } 440 441 int ans = 2; // me and my copy 442 443 if (dir == 1) { 444 if (curr < n) 445 ans += solve(curr + 1, k, dir) - 1; 446 447 ans %= mod; 448 449 if (curr > 1) 450 ans += solve(curr - 1, k - 1, 1 - dir) - 1; 451 452 ans %= mod; 453 dp[curr][k][dir] = ans; 454 } else { 455 if (curr > 1) 456 ans += solve(curr - 1, k, dir) - 1; 457 458 ans %= mod; 459 460 if (curr < n) 461 ans += solve(curr + 1, k - 1, 1 - dir) - 1; 462 463 ans %= mod; 464 dp[curr][k][dir] = ans; 465 } 466 467 return ans; 468 } 469 470 int main() { 471 int t; 472 cin >> t; 473 474 while (t--) { 475 cin >> n >> k; 476 memset(dp, -1, sizeof(dp)); 477 cout << solve(1, k, 1) << endl; 478 } 479 } 480 ``` 481 482 **Python Iterative solution** 483 484 ``` 485 mod = int(1e9 + 7) 486 487 def iter_solver(N, K): 488 dp = [[[-1 for _ in range(2)] for __ in range(K + 1)] for ___ in range(N + 1)] 489 for i in range(1, N + 1): 490 dp[i][1][0] = dp[i][1][1] = 1 491 492 for k in range(2, K + 1): 493 # forward dir 494 for n in range(N, 0, -1): 495 ans = 2 496 497 if n < N: 498 ans += dp[n + 1][k][0] - 1 499 ans %= mod 500 501 if n > 1: 502 ans += dp[n - 1][k - 1][1] - 1 503 ans %= mod 504 505 dp[n][k][0] = ans 506 507 # backward dir 508 for n in range(1, N + 1): 509 ans = 2 510 511 if n < N: 512 ans += dp[n + 1][k - 1][0] - 1 513 ans %= mod 514 515 if n > 1: 516 ans += dp[n - 1][k][1] - 1 517 ans %= mod 518 519 dp[n][k][1] = ans 520 521 return dp[1][K][0] 522 523 t = int(input()) 524 525 while t > 0: 526 t -= 1 527 528 n, k = list(map(int, input().split())) 529 530 print(iter_solver(n, k)) 531 ``` 532 533 # [1498D - Bananas in a Microwave](/contest/1498/problem/D "CodeCraft-21 and Codeforces Round 711 (Div. 2)") 534 535 #### [**Video Editorial**](https://www.youtube.com/watch?v=nsrKedxfyvU) 536 537 **Author:** [shash42](/profile/shash42 "Candidate Master shash42") 538 **Problemsetting and Editorialist:** [sigma_g](/profile/sigma_g "Master sigma_g") 539 540 **Brute force solution** 541 542 We have a brute force $\mathcal{O}(N\cdot M^2)$ solution. 543 544 At every timestep $t$, for each banana $b_i$ that has already been reached previously, apply this timestep's operation $y_t$ times on $b_i$. For all the $y_t$ bananas reachable from $b_i$, update their minimum reachability time if they hadn't been reached previously. 545 546 Why is this correct? Simply because we are simulating each possible step of the algorithm exactly as it is described. Therefore, we cannot get an answer that's better or worse than that of the optimal solution. 547 548 **Optimizing the brute force: hint** 549 550 Observe if we can reduce our search space when we visit nodes that have already been visited previously. 551 552 **Optimizing the brute force: hint 2** 553 554 Let us take an example. We have some timestep $t,x,y = 1,5,10$. If we start visiting from $k=10$, we will visit $k=15,20,\ldots,55,60$. Let us say that $k=40$ was an already visited state. Do we now need to continue visiting $k=45,\ldots,60$ or can we stop our search here? 555 556 **Optimizing the brute force: details** 557 558 We can actually stop our search as soon as we reach a previouly visited node! Why is this so? This is because — within the same iteration — that already visited node will once again start its own search, and will hit all the points that we were going to hit, and some more! 559 560 For example, let us say we would reach points $a, a\cdot x, a\cdot x^2, \ldots, a\cdot x^{y-1}$. Now, assume that $a\cdot x^5$ had been previously reached, then it is better to stop at $a\cdot x^5$, as this node itself will reach $a\cdot x^5, a\cdot x^6, \ldots, a\cdot x^{y-2}, a\cdot x^{y-1},a\cdot x^{y}, \ldots, a\cdot x^{5+y-1}$. Note the latter range includes as a prefix the entire remaining suffix of the former range! Therefore, in this approach, nodes that would *have* been visited, will eventually be visited, and get assigned the minimum timestamp. 561 562 **Optimized solution implementation** 563 564 We can implement the optimized solution by simply adding an extra `if already_visited[k]: break` to our inner loop. Yup, really, that's all it takes to solve this question! 565 566 Complexity analysis: We can show that each node is visited at most twice: an unvisited node is reached atmost once, whereas a visited node is reached atmost twice (once during the main loop and once when searching from the immediately previous visited node) There are $N$ iterations, and in each iteration, each of the $M$ nodes is visited at most twice. Therefore, the total complexity is $\mathcal{O}(2NM)$. 567 568 **Common mistakes** 569 570 1. Integer overflows: $x'$ does not fit in integer range 571 2. Out of bounds access: simulating the $y_t$ steps of the algorithm even when $k$ exceeds $M$ prematurely 572 573 **C++ solution** 574 575 ``` 576 #include <iostream> 577 #include <vector> 578 579 using namespace std; 580 using LL = long long; 581 582 const int DIV = 1e5; 583 inline LL ceil(LL x, LL y) { 584 return (x + y - 1) / y; 585 } 586 587 int main() { 588 int T, M; cin >> T >> M; 589 590 vector<bool> is_seen(M + 1, false); 591 is_seen[0] = true; 592 vector<int> answer(M + 1, -1); 593 answer[0] = 0; 594 595 for (int timestep = 1; timestep <= T; timestep++) { 596 auto new_is_seen = is_seen; 597 598 int t, y; LL x; 599 cin >> t >> x >> y; 600 601 auto operation = [&] (long long &curr) { 602 if (t == 1) { 603 curr = curr + ceil(x, DIV); 604 } else { 605 curr = ceil(curr * x, DIV); 606 } 607 }; 608 609 for (int k = 0; k <= M; k++) { 610 if (is_seen[k]) { 611 long long curr = k; 612 operation(curr); 613 614 for (int a = 1; a <= y;) { 615 if (curr > M) break; 616 if (is_seen[curr]) break; 617 618 new_is_seen[curr] = true; 619 answer[curr] = timestep; 620 621 a++; 622 operation(curr); 623 } 624 } 625 } 626 627 is_seen = new_is_seen; 628 } 629 630 for (int i = 1; i <= M; i++) 631 cout << answer[i] << " "; 632 633 cout << endl; 634 } 635 ``` 636 637 **Python solution** 638 639 ``` 640 import sys 641 input = lambda: sys.stdin.readline().rstrip() 642 643 DIV = int(1e5) 644 645 def ceil(x, y): 646 return (x + y - 1) // y 647 648 T, M = list(map(int, input().split())) 649 650 is_seen = [0 for _ in range(M + 1)] 651 is_seen[0] = 1 652 answer = [-1 for _ in range(M + 1)] 653 answer[0] = 0 654 655 o = 0 656 657 for timestep in range(1, T + 1): 658 t, x, y = list(map(int, input().split())) 659 660 def operation(val): 661 if t == 1: 662 return curr + ceil(x, DIV) 663 else: 664 return ceil(curr * x, DIV) 665 666 k = 0 667 668 setting = [] 669 670 while k <= M: 671 if is_seen[k]: 672 curr = k 673 674 i = 0 675 while i < y: 676 i += 1 677 678 o += 1 679 680 curr = operation(curr) 681 682 if curr > M: 683 break 684 if is_seen[curr]: 685 break 686 687 setting.append(curr) 688 answer[curr] = timestep 689 690 k += 1 691 692 for idx in setting: 693 is_seen[idx] = 1 694 695 sys.stdout.write(" ".join(map(str, answer[1:]))) 696 ``` 697 698 # [1498E - Two Houses](/contest/1498/problem/E "CodeCraft-21 and Codeforces Round 711 (Div. 2)") 699 700 **Author, Problemsetting and Editorialist:** [dixitgarg](/profile/dixitgarg "Master dixitgarg") 701 702 **Description** 703 704 In this problem we have to output two nodes $a$ and $b$ such that there is a path from $a$ to $b$ and $b$ to $a$ and the absolute value of the difference of the indegree $(|k_a - k_b|)$ should be maximum. First of all, let us think of bireachability only i.e how to find two nodes $a$ and $b$ such that they are both reachable from each other? How can we verify this from the judge? Because if we ask $"? \ a \ b"$ i.e whether there is a path from $a$ to $b$ or not, then if the judge answers "Yes", we can't ask further queries. So we have to ask queries for those pairs $(a,b)$ for which we are sure that there is a path from $b$ to $a$. So how to ensure whether there is a path from $b$ to $a$ or not? 705 706 **Hint1** 707 708 The answer lies in the fact that the given graph is not an ordinary graph, it is a special one. For every pair of vertices in this graph, there is a directed edge. So this type of graph has some interesting properties which we are going to see now. 709 710 Image how the compressed SCC of the graph will look like. For every pair of nodes of compressed SCC, there will be an edge, so it will have exactly one source, one sink and there would be only one possible topological sorting of this compressed SCC. 711 712 **Proof of unique topological sorting** 713 714 Since there is an edge between every pair of nodes, for every pair of nodes in the compresses SCC also, there would be an edge. And we know that if there is an edge between node $a$ to node $b$, then node $a$ comes before node $b$ in the topological sort. So for every pair of nodes of compressed SCC, we know which node would come first in the topological sorting, so it would result in a unique topological sorting. 715 716 **Hint2** 717 718 Now we'll see one interesting and important property of this graph. 719 720 Property: Consider two consecutive strongly connected components in the topological sorting, then all nodes present in the left component will have indegree strictly less than all nodes present in the right component. Here left denotes lower enumeration in the topological sorting. 721 722 **Proof** 723 724 Consider two nodes $u$ and $v$ from the left component and right component respectively. Since the contribution to the indegree from the nodes which don't lie in these two components would be the same for both $u$ and $v$ (because $u$ and $v$ lie in adjacent components), we are ignoring it as we have to just compare their values. If we consider all the edges between the nodes of the left component and the right component, then all of them would be directed from the node in the left component to the node in the right component. So the node $v$ would have minimum indegree of $Size of Left Component$. The node $u$ would have the maximum indegree of $Size of Left Component - 1$. This is because there is no edge directed from the right component to the node $u$ and the maximum indegree will be when all other nodes in the left component have an edge directed towards node $u$. In that case, it would be $Size of Left Component -1$. So the indegree of $u$ is strictly less than the indegree of $v$. Since $u$ and $v$ are arbitrary nodes, it is true for all pairs of nodes. 725 726 **Hint3** 727 728 Using the above property we can argue that if indegree of node $a$ is greater than the indegree of node $b$, then node $a$ is reachable from node $b$. Because either node $a$ lies in the same SCC or to the SCC of higher enumeration in topological sorting. In both cases $a$ is reachable from $b$. 729 730 So we can store all pairs of nodes $(a,b), 1 \leq a \leq n, 1 \leq b \leq n, a \lt b$ in an array and sort it according to decreasing order of absolute value of difference of indegrees i.e $|k_a - k_b|$. And if we pick a pair, let it be ($a$,$b$) and $indegree[b] \gt indegree[a]$, then we are sure that $b$ is reachable from $a$ so we need to check whether $a$ is reachable from $b$ or not, so we ask $"? \ b \ a"$ and if the judge responds by "Yes", then it means both $a$ and $b$ are reachable from each other. Since we were iterating in the decreasing order of $|k_a - k_b|$, we get the optimal answer. If the judge never outputs "Yes" in the whole process, then there is no pair of nodes that are reachable from each other. So we will output $"? \ 0 \ 0"$ 731 732 Overall Complexity : $O(n^2 \log_2 n)$ 733 734 **C++ solution** 735 736 ``` 737 #include <bits/stdc++.h> 738 using namespace std; 739 740 int main() { 741 int n; 742 cin >> n; 743 vector<int> indegree(n); 744 for (int i = 0; i < n; i++) { 745 cin >> indegree[i]; 746 } 747 vector<pair<int, pair<int, int>>> vec; 748 for (int i = 0; i < n; ++i) { 749 for (int j = i + 1; j < n; ++j) { 750 if (indegree[i] > indegree[j]) 751 vec.push_back({indegree[i] - indegree[j], {i, j}}); 752 else 753 vec.push_back({indegree[j] - indegree[i], {j, i}}); 754 } 755 } 756 sort(vec.rbegin(), vec.rend()); 757 for (auto it : vec) { 758 if (it.first < 0) 759 break; 760 761 int a = it.second.first, b = it.second.second; 762 cout << "? " << a + 1 << " " << b + 1 << endl; 763 cout.flush(); 764 string str; 765 cin >> str; 766 if (str == "Yes") { 767 cout << "! " << a + 1 << " " << b + 1 << endl; 768 cout.flush(); 769 return 0; 770 } 771 } 772 773 cout << "! 0 0" << endl; 774 cout.flush(); 775 776 return 0; 777 } 778 ``` 779 780 **Python solution** 781 782 ``` 783 import sys 784 input = lambda: sys.stdin.readline().rstrip() 785 786 n = int(input()) 787 788 indegs = list(map(int, input().split())) 789 790 pairs = [] 791 for i in range(n): 792 for j in range(i + 1, n): 793 if indegs[i] > indegs[j]: 794 pairs.append((indegs[i] - indegs[j], (i, j))) 795 else: 796 pairs.append((indegs[j] - indegs[i], (j, i))) 797 798 pairs = sorted(pairs, reverse=True) 799 l = len(pairs) 800 801 for _, nodes in pairs: 802 ni, nj = nodes 803 804 sys.stdout.write(f"? {ni + 1} {nj + 1}\n") 805 sys.stdout.flush() 806 807 s = input() 808 if s == "Yes": 809 sys.stdout.write(f"! {ni + 1} {nj + 1}\n") 810 exit(0) 811 812 sys.stdout.write("! 0 0\n") 813 ``` 814 815 # [1498F - Christmas Game](/contest/1498/problem/F "CodeCraft-21 and Codeforces Round 711 (Div. 2)") 816 817 **Author:** [nikhil_c](/profile/nikhil_c "Expert nikhil_c") 818 **Problemsetting and editorialist:** [sigma_g](/profile/sigma_g "Master sigma_g") 819 820 **How do we solve a standard Nim game on arrays?** 821 822 By the Sprague-Grundy theorem, we know that the current player has a winning strategy if $a_1 \oplus a_2 \oplus \ldots \oplus a_n$ (xorsum of sizes of the existing piles) is non-zero. For a proof, read details on [CP-algorithms](https://cp-algorithms.com/game_theory/sprague-grundy-nim.html). 823 824 **How to solve tree nim game for one rooting if K = 1: classifying odd/even steps** 825 826 Let us classify nodes into odd or even depending on their depth relative to the root. Note that even steps do not affect the game state. Let us prove how: 827 828 Let us say it's Alice's turn. If Alice moves some coins from an even step to an odd step, then Bob can move *exactly those same coins* from that odd step back to an even step. After this transition, once again it's Alice's move. In fact, we realize that Bob can "revert" every even->odd move by Alice. 829 830 Therefore, if Alice wants to win, she has to play at least one odd->even move. Moves that go from even->odd do not affect the game state at all, as the other player can always play another move that reverts them. Therefore, we can say that any coins present on even steps will not change the game state. 831 832 **How to solve tree nim game for one rooting if K = 1: how bad are even steps** 833 834 Let us now analyze what happens if some coins move from the odd steps to even steps. We know that any coins on even nodes will not contribute to the game state. In fact, we realize that it does not matter whether these coins were present on the even nodes before the game started or whether they came by on the even nodes during the game. Once they are on an even step, they no longer contribute to the game state. 835 836 Hence, we can conclude that moving a coin from odd step to an even step is as good as taking a coin from the odd step and throwing it away. 837 838 **Reducing tree nim game to linear array: the stair case nim** 839 840 As we can see, we have effectively reduced the Nim game on tree to a linear nim game where only the odd positioned nodes determine the winning strategy. This is known as the staircase nim. The result is the following: the current player has a winning strategy if xorsum of all values at the odd steps is non-zero. 841 842 **Extending to general K** 843 844 In general $K$, we can extend this idea to: parity of $d' = \lfloor \frac d K \rfloor$ where $d$ is the depth of this node (zero-indexed). All nodes — such that $d'$ is odd for them — will contribute to the final xorsum. Take a moment to digest this. 845 846 How to calculate these xors? At each node $x$, we store a vector of size $D(n) = 2\cdot K$ where $D(n)_i$ is the xorsum of all nodes having their depth = $i$ — relative to node $x$ — in the subtree of node $n$. 847 848 **Calculating the answer for all roots** 849 850 How to propagate these values in a DFS? We know that the nodes at depth `i` is at depth `i + 1` for my child nodes. So, we can simply cycle through them and update the values. Check the implementation for details. 851 852 **C++ solution** 853 854 ``` 855 #include <iostream> 856 #include <vector> 857 858 using namespace std; 859 860 const int N = 1e5 + 1; 861 const int K = 20 + 1; 862 863 using VI = vector<unsigned int>; 864 using VVI = vector<vector<unsigned int>>; 865 866 VVI dp(N, VI(2 * K)); 867 VI a(N); 868 vector<bool> win(N); 869 int n, k, k2; 870 871 void dfs(VVI &adj, int node, int prev) { 872 dp[node][0] = a[node]; 873 874 for (auto neigh : adj[node]) { 875 if (neigh == prev) continue; 876 dfs(adj, neigh, node); 877 878 for (int rem = 1; rem < k2; rem++) 879 dp[node][rem] ^= dp[neigh][rem - 1]; 880 881 dp[node][0] ^= dp[neigh][k2 - 1]; 882 } 883 } 884 885 void dfs2(const VVI &adj, const int node, const int prev, const vector<unsigned int> &my_xors) { 886 vector<unsigned int> final_xors(k2); 887 for (int i = 0; i < k2; i++) 888 final_xors[i] = my_xors[i] ^ dp[node][i]; 889 890 unsigned int odd_layer_xor = 0; 891 for (int i = k; i < k2; i++) 892 odd_layer_xor ^= final_xors[i]; 893 win[node] = odd_layer_xor > 0; 894 895 for (auto neigh : adj[node]) { 896 if (neigh == prev) continue; 897 898 auto xor_send = final_xors; 899 900 // remove all contribution of this subtree 901 for (int i = 1; i < k2; i++) 902 xor_send[i] ^= dp[neigh][i - 1]; 903 904 xor_send[0] ^= dp[neigh][k2 - 1]; 905 906 // whatever was depth k for me is depth k+1 for my child node 907 int last = xor_send.back(); 908 for (int i = k2 - 1; i > 0; i--) 909 xor_send[i] = xor_send[i - 1]; 910 911 xor_send[0] = last; 912 913 dfs2(adj, neigh, node, xor_send); 914 } 915 } 916 917 int main() { 918 cin >> n >> k; 919 k2 = 2 * k; 920 921 VVI adj(n + 1); 922 923 for (int i = 0; i < n - 1; i++) { 924 int x, y; cin >> x >> y; 925 adj[x].push_back(y); 926 adj[y].push_back(x); 927 } 928 929 for (int i = 1; i <= n; i++) cin >> a[i]; 930 931 dfs(adj, 1, 0); 932 dfs2(adj, 1, 0, vector<unsigned int>(k2)); 933 934 for (int i = 1; i <= n; i++) cout << (win[i] ? 1 : 0) << " "; 935 936 return 0; 937 } 938 ``` 939 940 **Python solution** 941 942 ``` 943 n, k = list(map(int, input().split())) 944 k2 = 2 * k 945 946 dp = [[0 for _ in range(k2)] for _ in range(n + 1)] 947 adj = [[] for _ in range(n + 1)] 948 949 for _ in range(n - 1): 950 _x, _y = list(map(int, input().split())) 951 adj[_x].append(_y) 952 adj[_y].append(_x) 953 954 a = [0] + list(map(int, input().split())) 955 956 win = [0 for _ in range(n + 1)] 957 958 parent = [0 for _ in range(n + 1)] 959 960 def dfs(node): 961 global parent 962 global dp 963 964 stack = [node] 965 966 pass_num = [0 for _ in range(n + 1)] 967 968 while stack: 969 node = stack[-1] 970 971 pass_num[node] += 1 972 973 if pass_num[node] == 1: 974 for neigh in adj[node]: 975 if neigh == parent[node]: 976 continue 977 978 parent[neigh] = node 979 stack.append(neigh) 980 981 continue 982 983 dp[node][0] = a[node] 984 stack.pop() 985 986 for neigh in adj[node]: 987 if neigh == parent[node]: 988 continue 989 990 for rem in range(1, k2): 991 dp[node][rem] ^= dp[neigh][rem - 1] 992 993 dp[node][0] ^= dp[neigh][k2 - 1] 994 995 def dfs2(node): 996 global win 997 998 stack = [[node, [0 for __ in range(k2)]]] 999 1000 global dp 1001 1002 while stack: 1003 node, prev_xors = stack[-1] 1004 stack.pop() 1005 1006 final_xors = [x ^ y for x, y in zip(prev_xors, dp[node])] 1007 1008 for neigh in adj[node]: 1009 if neigh == parent[node]: 1010 continue 1011 1012 send_xors = [x for x in final_xors] 1013 for i in range(1, k2): 1014 send_xors[i] ^= dp[neigh][i - 1] 1015 send_xors[0] ^= dp[neigh][k2 - 1] 1016 1017 send_xors = [send_xors[-1]] + send_xors[:-1] 1018 stack.append([neigh, send_xors]) 1019 1020 odd_xor = 0 1021 for i in range(k, k2): 1022 odd_xor ^= final_xors[i] 1023 1024 win[node] = 1 if odd_xor > 0 else 0 1025 1026 dfs(1) 1027 dfs2(1) 1028 print(" ".join(list(map(str, win[1:])))) 1029 ```