codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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 ```