codeforces-scrape

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

1919.md (55506B)


      1 Source: https://codeforces.com/blog/entry/124220
      2 
      3 ### [1919A - Wallet Exchange](/contest/1919/problem/A "Hello 2024")
      4 
      5 Author: [maomao90](/profile/maomao90 "Grandmaster maomao90")
      6 
      7 **Hint 1**
      8 
      9 When does the game end?
     10 
     11 **Solution**
     12 
     13 Depending on whether the player chooses to exchange wallets with their opponent on step $1$, $1$ coins will be removed from either the opponent's wallet or the player's wallet. This means that if either of the players still has remaining coins, the game will not end as at least one of the choices will still be valid.
     14 
     15 The only way that the game ends is when both players have $0$ coins. Since each operation decreases the total amount of coins by exactly $1$, the only way for Alice to win the game is if $a + b$ is odd.
     16 
     17 **Code**
     18 
     19 ```
     20 #include <bits/stdc++.h>
     21 using namespace std;
     22 
     23 int main() {
     24     int t; cin >> t;
     25     while (t--) {
     26         int a, b; cin >> a >> b;
     27         if ((a + b) % 2 == 0) {
     28             cout << "Bob\n";
     29         } else {
     30             cout << "Alice\n";
     31         }
     32     }
     33 }
     34 ```
     35 
     36 ### [1919B - Plus-Minus Split](/contest/1919/problem/B "Hello 2024")
     37 
     38 Author: [maomao90](/profile/maomao90 "Grandmaster maomao90")
     39 
     40 **Hint 1**
     41 
     42 Try to find a lower bound.
     43 
     44 **Solution**
     45 
     46 The answer is $|a_1 + a_2 + \ldots + a_n|$. Intuitively, whenever we have a subarray with a sum equal to $0$, it will be helpful for us as its penalty will become $0$. Hence, we can split $a$ into subarrays with a sum equal to $0$ and group up the remaining elements into individual subarrays of size $1$. A formal proof is given below.
     47 
     48 Let us define an alternative penalty function $p2(l, r) = |a_l + a_{l+1} + \ldots + a_r|$. We can see that $p2(l, r) \le p(l, r)$ for all $1\le l\le r\le n$. Since the alternative penalty function does not have the $(r - l + 1)$ term, there is no reason for us to partition $a$ into two or more subarrays as $|x| + |y| \ge |x + y|$ for all integers $x$ and $y$, so the answer for the alternative penalty function is $|a_1 + a_2 + \ldots + a_n|$.
     49 
     50 Since $p2(l, r)\le p(l, r)$, this means that the answer to our original problem cannot be smaller than $|a_1 + a_2 + \ldots + a_n|$. In fact, this lower bound is always achievable. Let us prove this by construction.
     51 
     52 Note that if we flip every "$\mathtt{+}$" to "$\mathtt{-}$" and every "$\mathtt{-}$" to "$\mathtt{+}$", our answer will remain the same since our penalty function involves absolute values. Hence, we can assume that the sum of elements of $a$ is non-negative.
     53 
     54 If the sum of elements of $a$ is $0$, we can split $a$ into a single array equal to itself $b_1 = a$ and obtain a penalty of $0$. Otherwise, we find the largest index $i$ where $a_1 + a_2 + \ldots + a_i = 0$. Then we let the first subarray be $b_1 = [a_1, a_2, \ldots, a_i]$ and the second subarray be $b_2 = [a_{i + 1}]$, so we have $p(b_1) = 0$ and $p(b_2) = 1$. Since $i$ is the largest index, $a_{i + 1}$ has to be equal to $1$ as if $a_{i + 1}$ is $-1$ instead, there has to be a larger index where the prefix sum becomes $0$ again for the prefix sum to go from negative to the final positive total sum. This means that for the remaining elements of the array $a_{i+2\ldots n}$, the sum of its elements decreases by $1$, so we can continue to use the same procedure to split the remaining elements which decrease the sum by $1$ and increase the penalty by $1$ each time until the sum of elements becomes $0$. Hence, the total penalty will be equal to the sum of elements of $a$.
     55 
     56 **Code**
     57 
     58 ```
     59 #include <bits/stdc++.h> 
     60 using namespace std;
     61 
     62 int t;
     63 int n;
     64 string s;
     65 
     66 int main() {
     67     cin >> t;
     68     while (t--) {
     69         cin >> n;
     70         cin >> s;
     71         int sm = 0;
     72         for (int i = 0; i < n; i++) {
     73             sm += s[i] == '+' ? 1 : -1;
     74         }
     75         cout << abs(sm) << '\n';
     76     }
     77 }
     78 ```
     79 
     80 ### [1919C - Grouping Increases](/contest/1919/problem/C "Hello 2024")
     81 
     82 Author: [maomao90](/profile/maomao90 "Grandmaster maomao90")
     83 
     84 **Hint 1**
     85 
     86 Consider a greedy approach.
     87 
     88 **Solution 1**
     89 
     90 Consider the following approach. We start with empty arrays $b$ and $c$, then insert elements of the array $a$ one by one to the back of $b$ or $c$. Our penalty function only depends on adjacent elements, so at any point in time, we only care about the value of the last element of arrays $b$ and $c$. Suppose we already inserted $a_1, a_2, \ldots, a_{i - 1}$ into arrays $b$ and $c$ and we now want to insert $a_i$. Let $x$ and $y$ be the last element of arrays $b$ and $c$ respectively (if they are empty, use $\infty$). Note that swapping arrays $b$ and $c$ does not matter, so without loss of generality, assume that $x\le y$. We will use the following greedy approach.
     91 
     92 1. If $a_i\le x$, insert $a_i$ to the back of the array with a smaller last element.
     93 2. If $y \lt a_i$, insert $a_i$ to the back of the array with a smaller last element.
     94 3. If $x \lt a_i\le y$, insert $a_i$ to the back of the array with a bigger last element.
     95 
     96 The proof of why the greedy approach is optimal is given below:
     97 
     98 1. $a_i\le x$. In this case, $a_i$ is not greater than the last element of both arrays, so inserting $a_i$ to the back of either array will not add additional penalties. However, it is better to insert $a_i$ into the array with a smaller last element so that in the future, we can insert a wider range of values into the new array without additional penalty.
     99 2. $y \lt a_i$. In this case, $a_i$ is greater than the last element of both arrays, so inserting $a_i$ to the back of either array will contribute to $1$ additional penalty. However, it is better to insert $a_i$ into the array with a smaller last element so that in the future, we can insert a wider range of values into the new array without additional penalty.
    100 3. $x \lt a_i\le y$. In this case, if we insert $a_i$ to the back of the array with the larger last element, there will not be any additional penalty. However, if we insert $a_i$ to the back of the array with the smaller last element, there will be an additional penalty of $1$. The former option is always better than the latter. This is because if we consider making the same choices for the remaining elements $a_{i+1}$ to $a_n$ in both scenarios, there will be at most one time where the former scenario will add one penalty more than the latter scenario as the former scenario has a smaller last element after inserting $a_i$. After that happens, the back of the arrays in both scenarios will become the same and hence, the former case will never be less optimal.
    101 
    102 Following the greedy approach for all 3 cases will result in a correct solution that runs in $O(n)$ time.
    103 
    104 **Hint 1**
    105 
    106 Consider a dynamic programming approach.
    107 
    108 **Hint 2**
    109 
    110 Let $dp_{i, v}$ represent the minimum penalty when we are considering splitting $a_{1\ldots i}$ into two subarrays where the last element of one subarray is $a_i$ while the last element of the second subarray is $v$.
    111 
    112 **Hint 3**
    113 
    114 Speed up the transition by storing the state in a segment tree.
    115 
    116 **Solution 2**
    117 
    118 Let us consider a dynamic programming solution. Let $dp_{i, v}$ represent the minimum penalty when we are considering splitting $a_{1\ldots i}$ into two subarrays where the last element of one subarray is $a_i$ while the last element of the second subarray is $v$. Then, our transition will be $dp_{i, v} = dp_{i - 1, v} + [a_{i - 1} \lt a_i]$ for all $1\le v\le n, v\neq a_{i - 1}$ and $dp_{i, a_{i - 1}} = \min(dp_{i - 1, a_{i - 1}} + [a_{i - 1} \lt a_i], \min_{1\le x\le n}(dp_{i - 1, x} + [x \lt a_i]))$.
    119 
    120 To speed this up, we use a segment tree to store the value of $dp_{i - 1, p}$ at position $p$. To transition to $dp_i$, notice that the first transition is just a range increment on the entire range $[1, n]$ of the segment tree if $a_{i - 1} \lt a_i$. For the second transition, we can do two range minimum queries on ranges $[1, a_i - 1]$ and $[a_i, n]$. The final time complexity is $O(n\log n)$.
    121 
    122 **Code (Solution 1)**
    123 
    124 ```
    125 #include <bits/stdc++.h> 
    126 using namespace std;
    127 
    128 const int INF = 1000000005;
    129 const int MAXN = 200005;
    130 
    131 int t;
    132 int n;
    133 int a[MAXN];
    134 
    135 int main() {
    136     ios::sync_with_stdio(0), cin.tie(0);
    137     cin >> t;
    138     while (t--) {
    139         cin >> n;
    140         for (int i = 1; i <= n; i++) {
    141             cin >> a[i];
    142         }
    143         int t1 = INF, t2 = INF;
    144         int ans = 0;
    145         for (int i = 1; i <= n; i++) {
    146             if (t1 > t2) {
    147                 swap(t1, t2);
    148             }
    149             if (a[i] <= t1) {
    150                 t1 = a[i];
    151             } else if (a[i] <= t2) {
    152                 t2 = a[i];
    153             } else {
    154                 t1 = a[i];
    155                 ans++;
    156             }
    157         }
    158         cout << ans << '\n';
    159     }
    160 }
    161 ```
    162 
    163 **Code (Solution 2)**
    164 
    165 ```
    166 #include <bits/stdc++.h> 
    167 using namespace std;
    168 
    169 const int INF = 1000000005;
    170 const int MAXN = 200005;
    171 
    172 int t;
    173 int n;
    174 int a[MAXN];
    175 
    176 int mn[MAXN * 4], lz[MAXN * 4];
    177 void init(int u = 1, int lo = 1, int hi = n) {
    178     mn[u] = lz[u] = 0;
    179     if (lo != hi) {
    180         int mid = lo + hi >> 1;
    181         init(u << 1, lo, mid);
    182         init(u << 1 ^ 1, mid + 1, hi);
    183     }
    184 }
    185 void propo(int u) {
    186     if (lz[u] == 0) {
    187         return;
    188     }
    189     lz[u << 1] += lz[u];
    190     lz[u << 1 ^ 1] += lz[u];
    191     mn[u << 1] += lz[u];
    192     mn[u << 1 ^ 1] += lz[u];
    193     lz[u] = 0;
    194 }
    195 void incre(int s, int e, int x, int u = 1, int lo = 1, int hi = n) {
    196     if (lo >= s && hi <= e) {
    197         mn[u] += x;
    198         lz[u] += x;
    199         return;
    200     }
    201     propo(u);
    202     int mid = lo + hi >> 1;
    203     if (s <= mid) {
    204         incre(s, e, x, u << 1, lo, mid);
    205     }
    206     if (e > mid) {
    207         incre(s, e, x, u << 1 ^ 1, mid + 1, hi);
    208     }
    209     mn[u] = min(mn[u << 1], mn[u << 1 ^ 1]);
    210 }
    211 int qmn(int s, int e, int u = 1, int lo = 1, int hi = n) {
    212     if (s > e) {
    213         return INF;
    214     }
    215     if (lo >= s && hi <= e) {
    216         return mn[u];
    217     }
    218     propo(u);
    219     int mid = lo + hi >> 1;
    220     int res = INF;
    221     if (s <= mid) {
    222         res = min(res, qmn(s, e, u << 1, lo, mid));
    223     }
    224     if (e > mid) {
    225         res = min(res, qmn(s, e, u << 1 ^ 1, mid + 1, hi));
    226     }
    227     return res;
    228 }
    229 
    230 int main() {
    231     ios::sync_with_stdio(0), cin.tie(0);
    232     cin >> t;
    233     while (t--) {
    234         cin >> n;
    235         for (int i = 1; i <= n; i++) {
    236             cin >> a[i];
    237         }
    238         init();
    239         for (int i = 1; i <= n; i++) {
    240             int ndp = min(qmn(1, a[i] - 1) + 1, qmn(a[i], n));
    241             if (i > 1) {
    242                 if (a[i - 1] < a[i]) {
    243                     incre(1, n, 1);
    244                 }
    245                 int dp = qmn(a[i - 1], a[i - 1]);
    246                 if (ndp < dp) {
    247                     incre(a[i - 1], a[i - 1], ndp - dp);
    248                 }
    249             }
    250         }
    251         cout << qmn(1, n) << '\n';
    252     }
    253 }
    254 ```
    255 
    256 **Bonus**
    257 
    258 Solve the problem if you have to split the array into $k$ subsequences, where $k$ is given in the input ($k = 2$ for the original problem).
    259 
    260 **Solution**
    261 
    262 #### Modified statement
    263 
    264 There is an array $A$ of size $N$ and an array $T$ of size $K$. Initially, $T_i = \infty$ for all $1 \le i \le K$. For each time $t$ from $1$ to $N$, the following will happen:
    265 
    266 * Select an index $1 \le i \le K$. If $A_t \gt T_i$, we increase the cost by $1$. Then, we set $T_i := A_t$.
    267 
    268 Find the minimum possible cost after time $N$ if we select the indices optimally.
    269 
    270 #### Greedy
    271 
    272 The order of $T$ does not matter. Hence for convenience, we will maintain $T$ in non-decreasing order. At each time $t$, we will use the following algorithm:
    273 
    274 1. If $A_t \gt T_K$, do the operation on index $1$.
    275 2. Otherwise, find the smallest index $1 \le i \le K$ where $A_t \le T_i$ and do the operation on index $i$.
    276 
    277 #### Proof
    278 
    279 Suppose there exists an optimal solution that does not follow our algorithm. We will let $OT_{t, i}$ denote the value of $T_i$ before the operation was done at time $t$ in the optimal solution. Let $et$ be the earliest time that the operation done by the optimal solution differs from that of the greedy solution.
    280 
    281 * Case 1: $A_{et} \gt OT_{et,K}$. Since we are maintaining $T$ in the sorted order, having $A_{et} \gt OT_{et,K}$ means that $A_{et}$ is larger than all elements of $T$. This means that no matter which index $i$ we choose to do the operation on, the cost will always increase by $1$. Suppose an index $i \gt 1$ was chosen in the optimal solution. We can always choose to do the operation on index $1$ instead of index $i$ and the answer will not be less optimal. This is because if we let $T'$ be the array $T$ after the operation was done on index $1$, $T'_p \le OT_{et+1,p}$ for all $1 \le p \le K$ since $T'_p = \begin{cases}OT_{et,p+1}&\text{if }p \lt K\newline A_{et}&\text{if }p=K\end{cases}$ while $OT_{et+1,p} = \begin{cases}OT_{et,p}&\text{if }p \lt i\newline OT_{et,p+1}&\text{if }i\le p \lt K\newline A_{et}&\text{if }p=K\end{cases}$.
    282 * Case 2: $A_{et} \le OT_{et,K}$. For convenience, we will denote that the operation was done on index $i$ in the greedy solution while the operation was done on index $j$ based on the optimal solution during time $et$.
    283   + Case 2A: $i \lt j$. In this case, the cost does not increase for both the optimal solution and the greedy solution. However, we can always do an operation on index $i$ instead of index $j$ and the answer will not be less optimal. This is because if we let $T'$ be the array $T$ after the operation was done on index $i$, $T'_p\le OT_{et+1,p}$ for all $1\le p\le K$ since $T'_p = \begin{cases}OT_{et,p}&\text{if }p\neq i\newline A_{et}&\text{if }p=i\end{cases}$ while $OT_{et+1,p} = \begin{cases}OT_{et,p}&\text{if }p \lt i\newline A_{et}&\text{if }p=i\newline OT_{et,p-1}&\text{if }i \lt p\le j\newline OT_{et,p}&\text{if }j \lt p\le K\end{cases}$.
    284   + Case 2B: $i \gt j$. For this case, the cost increases for the optimal solution while the cost does not change for the greedy solution. However, it is not trivial to prove that the greedy solution is more optimal as even though it has a smaller cost, it results in a less optimal array $T$. Hence, we will prove this case below.
    285 
    286 **Case 2B**
    287 
    288 We want to come up with a modified solution that does the same operations as the optimal solution for time $1\le t \lt et$ and does an operation on index $i$ during time $et$. Adopting a similar notation to $OT$, we will let $MT_{t, i}$ denote the value of $T_i$ before the operation was done at time $t$ in this modified solution. Then, $MT_{et+1,p} = \begin{cases}OT_{et,p}&\text{if }p\neq i\newline A_{et}&\text{if } p=i\end{cases}$ and $OT_{et+1,p}=\begin{cases}OT_{et,p} &\text{if } p \lt j\newline OT_{et,p+1}&\text{if }j\le p \lt i-1\newline A_{et}&\text{if }p=i-1\newline OT_{et,p}&\text{if }i\le p\le K\end{cases}$. Note that in this case, $MT_{et+1,p}\le OT_{et+1,p}$ for all $1\le p\le K$, which means that our modified solution results in a less optimal state than the optimal solution. However, since our modified solution requires one less cost up to this point, we will be able to prove that our modified solution will not perform worse than the optimal solution.
    289 
    290 Notice that $OT_{et+1,p}\le MT_{et+1,p+1}$ for all $1\le p \lt K$. We denote that the index that the optimal solution operates on during time $t$ is $x_t$. Let $r$ be the minimum time where $et+1\le r\le N$ and $e_r=N$. Due to the above property that $OT_{et+1,p}\le MT_{et+1,p+1}$ for all $1\le p \lt K$, we can let our modified solution do the operation on index $x_t+1$ for all time $et+1\le t \lt r$ and the cost will not be more than the optimal solution. This is because the property that $OT_{t+1,p}\le MT_{t+1,p+1}$ for all $1\le p \lt K$ still holds throughout that time range even after each update. Note that if such an $r$ does not exist, we can let our modified solution do the operation on index $x_t+1$ for all time $et+1\le t\le K$ and we completed coming up with the modified solution with a cost not more than the optimal solution.
    291 
    292 However, if such an $r$ exists, then at time $r$, since $x_r=N$, we are no longer able to use the same method. However, let us consider what happens if we let our modified solution do an operation on index $1$ during time $r$.
    293 
    294 If $A_r \gt MT_{r,K}$, it will mean that $MT_{r+1,p}=\begin{cases}MT_{r,p+1}&\text{if }p \lt K\newline A_r&\text{if }p=K\end{cases}$ while $OT_{r+1,p}=\begin{cases}OT_{r,p}&\text{if }p \lt K\newline A_r&\text{if }p=K\end{cases}$ since $OT_{r,K-1}\le MT_{r,K} \lt A_r$. Even though during this time, it might be possible that the cost of the modified solution increases by $1$ while the cost of the optimal solution remains the same, recall that previously during time $i$ our modified solution used one less cost than the optimal solution. As a result, the modified solution will end up having a cost of not more than the optimal solution. At the same time, $OT_{r+1,p}\le MT_{r+1,p}$ for all $1\le p\le K$. Hence, for all time $r \lt t\le K$, we can let our modified solution do the operation on the same index as the optimal solution $x_t$ and the cost of our modified solution will not be more than that of the optimal solution.
    295 
    296 On the other hand, suppose $A_r\le MT_{r,K}$. Let $v$ be the minimum position such that $A_r\le MT_{r,v}$ and let $w$ be the minimum position such that $A_r\le OT_{r,w}$. Then, $MT_{r+1,p}=\begin{cases}MT_{r,p+1}&\text{if }p \lt v-1\newline A_r&\text{if }p=v-1\newline MT_{r,p}&\text{if }p\ge v\end{cases}$ and $OT_{r+1,p}=\begin{cases}OT_{r,p}&\text{if }p \lt w\newline A_r&\text{if }p=w\newline OT_{r,p-1}&\text{if }p \gt w\end{cases}$. In the same way, the cost of our modified solution might increase while the cost of the optimal solution stays the same, however, $OT_{r+1,p}\le MT_{r+1,p}$ for all $1\le p\le K$. - For $p \lt v-1$ and $p \gt w$, the condition holds since $OT_{r,p}\le MT_{r,p+1}$ for all $1\le p \lt K$. Note that $v-1\le w$ because of the same inequality as well. - Suppose $v-1=w$. Then for $p=v-1$, $OT_{r+1,p}=A_r\le A_r=MT_{r+1,p}$. From now on, we suppose $v-1\neq w$ - For $p=v-1$, $OT_{r,v-1}\le A_r$ as $w$ is defined as the minimum position that $A_r\le OT_{r,w}$ and $v-1 \lt w$. - For $v\le p \lt w$, $OT_{r,p}\le MT_{r,p}$ as $OT_{r,p} \lt A_r\le MT_{r,p}$ - For $p=w$, $A_r\le MT_{r,w}$ as $v$ is defined as the minimum position that $A_r\le MT_{r,v}$ and $v-1 \lt w$
    297 
    298 Now that we managed to construct a modified solution which follows the greedy algorithm from time $1\le t\le et$ and is not less optimal than the optimal solution, we can let the optimal solution be our modified solution and find the new $et$ to get a new modified solution. Hence by induction, our greedy solution is optimal.
    299 
    300 ### [1919D - 01 Tree](/contest/1919/problem/D "Hello 2024")
    301 
    302 Author: [maomao90](/profile/maomao90 "Grandmaster maomao90")
    303 
    304 **Hint 1**
    305 
    306 What does the distance of two leaves that share the same parent look like?
    307 
    308 **Hint 2**
    309 
    310 What happens if we delete two leaves that share the same parent?
    311 
    312 **Solution**
    313 
    314 Consider two leaves that share the same parent. They will be adjacent to each other in the dfs order, so their distances will be adjacent in array $a$. Furthermore, their distances to the root will differ by exactly $1$ since one of the edges from the parent to its children will have weight $0$ while the other will have weight $1$.
    315 
    316 If we delete two leaves that share the same parent, the parent itself will become the leaf. Since one of the edges from the parent to the child has weight $0$, the distance from the parent to the root is equal to the smaller distance between its two children. This means that deleting two leaves that share the same parent is the same as selecting an index $i$ such that $a_i = a_{i - 1} + 1$ or $a_i = a_{i + 1} + 1$, then removing $a_i$ from array $a$.
    317 
    318 Consider the largest value in $a$. If it is possible to delete it (meaning there is a value that is exactly one smaller than it to its left or right), we can delete it immediately. This is because keeping the largest value will not help to enable future operations as it can only help to delete elements that are $1$ greater than it, which is not possible for the largest value.
    319 
    320 Now, all we have to do is to maintain all elements that can be deleted and choose the element with the largest value each time. Then, whenever we delete an element, we need to check whether the two adjacent elements become deletable and update accordingly. We can do this using a priority_queue and a linked list in $O(n\log n)$. Note that many other implementations exist, including several $O(n)$ solutions.
    321 
    322 **Code**
    323 
    324 ```
    325 #include<bits/stdc++.h>
    326 using namespace std;
    327 
    328 const int MAXN = 200005;
    329 
    330 int n;
    331 int a[MAXN];
    332 int prv[MAXN],nxt[MAXN];
    333 bool in[MAXN];
    334 
    335 bool good(int i) {
    336     if (i < 1 || i > n) {
    337         return 0;
    338     }
    339     return a[prv[i]] == a[i] - 1 || a[nxt[i]] == a[i] - 1;
    340 }
    341 int main(){
    342     ios::sync_with_stdio(0), cin.tie(0);
    343     int t; cin >> t;
    344     while (t--) {
    345         cin >> n;
    346         priority_queue<pair<int, int>> pq;
    347         for (int i = 1; i <= n; i++) {
    348             prv[i] = i - 1;
    349             nxt[i] = i + 1;
    350             in[i] = 0;
    351             cin >> a[i];
    352         }
    353         a[n + 1] = a[0] = -2;
    354         for (int i = 1; i <= n; i++) {
    355             if (good(i)) {
    356                 in[i] = 1;
    357                 pq.push({a[i], i});
    358             }
    359         }
    360         while (!pq.empty()) {
    361             auto [_, i] = pq.top(); pq.pop();
    362             nxt[prv[i]] = nxt[i];
    363             prv[nxt[i]] = prv[i];
    364             if (!in[prv[i]] && good(prv[i])) {
    365                 in[prv[i]]=1;
    366                 pq.push({a[prv[i]], prv[i]});
    367             }
    368             if (!in[nxt[i]] && good(nxt[i])) {
    369                 in[nxt[i]]=1;
    370                 pq.push({a[nxt[i]], nxt[i]});
    371             }
    372         }
    373         int mn = n, bad = 0;
    374         for (int i = 1; i <= n; i++) {
    375             bad += !in[i];
    376             mn = min(a[i], mn);
    377         }
    378         if (bad == 1 && mn == 0) {
    379             cout << "YES\n";
    380         } else {
    381             cout << "NO\n";
    382         }
    383     }
    384 }
    385 ```
    386 
    387 ### [1919E - Counting Prefixes](/contest/1919/problem/E "Hello 2024")
    388 
    389 Author: [maomao90](/profile/maomao90 "Grandmaster maomao90")
    390 
    391 **Hint 1**
    392 
    393 Try solving the problem if the sum of elements of array $a$ is equal to $s$. If we can do this in $O(n)$ time, we can iterate through all possible values of $p_1 \le s \le p_n$ and sum up the number of ways for each possible sum.
    394 
    395 **Hint 2**
    396 
    397 Consider starting with array $a = [1, 1, \ldots, 1, -1, -1, \ldots, -1]$ where there are $p_n$ occurences of $1$ and $p_n - s$ occurrences of $-1$. Then, try inserting $(-1, 1)$ into the array to fix the number of occurrences of prefix sum starting from the largest value ($p_n$) to the smallest value ($p_1$).
    398 
    399 **Solution**
    400 
    401 Let us try to solve the problem if the sum of elements of array $a$ is equal to $s$. Consider starting array $a = [1, 1, \ldots, 1, -1, -1, \ldots, -1]$ where there are $p_n$ occurrences of $1$ and $p_n - s$ occurrences of $-1$. Notice that when we insert $(-1, 1)$ into array $a$ between positions $i$ and $i + 1$ where the sum of $a$ from $1$ to $i$ is $s$, two new prefix sums $s - 1$ and $s$ will be formed while the remaining prefix sums remain the same. Let us try to fix the prefix sums starting from the largest prefix sum to the smallest prefix sum.
    402 
    403 In the starting array $a$, we only have $1$ occurrence of prefix sum with value $p_n$. We can insert $(-1, 1)$ right after it $k$ times to increase the number of occurrences of prefix sum with value $p_n$ by $k$. In the process of doing so, the number of occurrences of prefix sum with value $p_n - 1$ also increased by $k$. Now, we want to fix the number of occurrences of prefix sum with value $p_n - 1$. If we already have $x$ occurrences but we require $y \gt x$ occurrences, we can choose to insert $y - 1$ pairs of $(-1, 1)$ right after any of the $x$ occurrences. We can calculate the number of ways using [stars and bars](https://en.wikipedia.org/wiki/Stars_and_bars_%28combinatorics%29) to obtain the formula $y - 1\choose y - x$.
    404 
    405 We continue using a similar idea to fix the number of occurrences of $p_n - 2, p_n - 3, \ldots, p_1$, each time considering the additional occurrences that were contributed from the previous layer. Each layer can be calculated in $O(1)$ time after precomputing binomial coefficients, so the entire calculation to count the number of array $a$ whose sum is $s$ and has prefix sum consistent to the input takes $O(n)$ time. Then, we can iterate through all possible $p_1 \le s \le p_n$ and sum up the answers to obtain a solution that works in $O(n^2)$ time.
    406 
    407 **Code**
    408 
    409 ```
    410 #include <bits/stdc++.h> 
    411 using namespace std;
    412 
    413 typedef long long ll;
    414 const int INF = 1000000005;
    415 const int MAXN = 200005;
    416 const int MOD = 998244353;
    417 
    418 ll fact[MAXN * 2], ifact[MAXN * 2];
    419 int t;
    420 int n;
    421 int f[MAXN * 2], d[MAXN * 2];
    422 
    423 inline ll ncr(int n, int r) {
    424     if (r < 0 || n < r) {
    425         return 0;
    426     }
    427     return fact[n] * ifact[r] % MOD * ifact[n - r] % MOD;
    428 }
    429 // count number of a_1 + a_2 + ... + a_n = x
    430 inline ll starbar(int n, int x) {
    431     if (n == 0 && x == 0) {
    432         return 1;
    433     }
    434     return ncr(x + n - 1, x);
    435 }
    436 
    437 int main() {
    438     ios::sync_with_stdio(0), cin.tie(0);
    439     fact[0] = 1;
    440     for (int i = 1; i < MAXN * 2; i++) {
    441         fact[i] = fact[i - 1] * i % MOD;
    442     }
    443     ifact[0] = ifact[1] = 1;
    444     for (int i = 2; i < MAXN * 2; i++) {
    445         ifact[i] = MOD - MOD / i * ifact[MOD % i] % MOD;
    446     }
    447     for (int i = 2; i < MAXN * 2; i++) {
    448         ifact[i] = ifact[i - 1] * ifact[i] % MOD;
    449     }
    450     cin >> t;
    451     while (t--) {
    452         cin >> n;
    453         for (int i = 0; i < n * 2 + 5; i++) {
    454             f[i] = 0;
    455         }
    456         n++;
    457         for (int i = 1; i < n; i++) {
    458             int s; cin >> s;
    459             f[s + n]++;
    460         }
    461         f[n]++;
    462         int mn = INF, mx = -INF;
    463         for (int i = 0; i <= 2 * n; i++) {
    464             if (f[i]) {
    465                 mn = min(mn, i);
    466                 mx = max(mx, i);
    467             }
    468         }
    469         bool bad = 0;
    470         for (int i = mn; i <= mx; i++) {
    471             if (!f[i]) {
    472                 bad = 1;
    473                 break;
    474             }
    475         }
    476         if (bad || mn == mx) {
    477             cout << 0 << '\n';
    478             continue;
    479         }
    480         ll ans = 0;
    481         for (int x = mx; x >= mn; x--) {
    482             d[mx - 1] = f[mx] + (mx > n) - (mx == x);
    483             for (int i = mx - 2; i >= mn - 1; i--) {
    484                 d[i] = f[i + 1] - d[i + 1] + (i >= x) + (i >= n);
    485             }
    486             if (d[mn - 1] != 0) {
    487                 continue;
    488             }
    489             ll res = 1;
    490             for (int i = mx - 1; i >= mn; i--) {
    491                 res = res * starbar(d[i], f[i] - d[i]) % MOD;
    492             }
    493             ans += res;
    494             if (ans >= MOD) {
    495                 ans -= MOD;
    496             }
    497         }
    498         cout << ans << '\n';
    499     }
    500 }
    501 ```
    502 
    503 **Bonus**
    504 
    505 Solve the problem in $O(n)$ time.
    506 
    507 Unfortunately, it seems like [ARC146E](https://atcoder.jp/contests/arc146/tasks/arc146_e) is identical to this problem :(
    508 
    509 ### [1919F1 - Wine Factory (Easy Version)](/contest/1919/problem/F1 "Hello 2024")
    510 
    511 Author: [maomao90](/profile/maomao90 "Grandmaster maomao90")
    512 
    513 **Hint 1**
    514 
    515 When $c_i$ and $z$ equals $10^{18}$, it means that all the remaining water will always flow into the next water tower. Hence, the answer will be the sum of $a_i$ minus the amount of water remaining at tower $n$ after the process.
    516 
    517 **Solution 1**
    518 
    519 From hint 1, our new task now is to determine the amount of water remaining at tower $n$ after the process. Let $v_i = a_i - b_i$. The remaining amount of water remaining at tower $n$ is the maximum suffix sum of $v$, or more formally $\max\limits_{1\le k\le n}\ \sum\limits_{i = k}^n v_i$. We can use a segment tree where position $p$ of the segment tree stores $\sum\limits_{i = p}^n v_i$. The updates can be done using range prefix increment and the queries can be done using range maximum.
    520 
    521 **Solution 2**
    522 
    523 Code ReLU segment tree. A similar method can be used to solve the full problem if you combine even more ReLUs. However, it is not very elegant and is much more complicated than the intended solution below.
    524 
    525 **What is ReLU segment tree?**
    526 
    527 ReLU is a common activation function used in neural networks which is defined by $f(x) = \max(x, 0)$. The objective of ReLU segment tree is to compose ReLU-like functions together. More precisely, ReLU segment tree can solve the following problem:
    528 
    529 > You are given two arrays $a$ and $b$ of length $n$. You are required to answer the following queries:  
    530 > - $\texttt{1 p x y}$. Update $a_p = x$ and $b_p = y$.  
    531 > - $\texttt{2 l r c}$. Output the value of $f_l(f_{l+1}(\ldots f_{r-1}(f_r(c))))$, where $f_i(x) = \max(x - a_i, b_i)$.
    532 
    533 The main idea to solve the problem is to observe that composing ReLU functions still results in a ReLU function, so we just need to store in each node the resultant function $f(x) = \max(x - p, q)$ after composing the functions that fall in the range of the segment tree node. For the merge function, we just need to figure out the details of composing two ReLU functions together.
    534 
    535 **Code (Solution 1)**
    536 
    537 ```
    538 #include <bits/stdc++.h> 
    539 using namespace std;
    540 
    541 typedef long long ll;
    542 const ll LINF = 1000000000000000005;
    543 const int MAXN = 500005;
    544 
    545 int n, q;
    546 int a[MAXN], b[MAXN];
    547 ll c[MAXN];
    548 ll v[MAXN], sv[MAXN];
    549 
    550 ll mx[MAXN * 4], lz[MAXN * 4];
    551 void init(int u = 1, int lo = 1, int hi = n) {
    552     lz[u] = 0;
    553     if (lo == hi) {
    554         mx[u] = sv[lo];
    555     } else {
    556         int mid = lo + hi >> 1;
    557         init(u << 1, lo, mid);
    558         init(u << 1 ^ 1, mid + 1, hi);
    559         mx[u] = max(mx[u << 1], mx[u << 1 ^ 1]);
    560     }
    561 }
    562 void propo(int u) {
    563     if (lz[u] == 0) {
    564         return;
    565     }
    566     lz[u << 1] += lz[u];
    567     lz[u << 1 ^ 1] += lz[u];
    568     mx[u << 1] += lz[u];
    569     mx[u << 1 ^ 1] += lz[u];
    570     lz[u] = 0;
    571 }
    572 void incre(int s, int e, ll x, int u = 1, int lo = 1, int hi = n) {
    573     if (lo >= s && hi <= e) {
    574         mx[u] += x;
    575         lz[u] += x;
    576         return;
    577     }
    578     propo(u);
    579     int mid = lo + hi >> 1;
    580     if (s <= mid) {
    581         incre(s, e, x, u << 1, lo, mid);
    582     }
    583     if (e > mid) {
    584         incre(s, e, x, u << 1 ^ 1, mid + 1, hi);
    585     }
    586     mx[u] = max(mx[u << 1], mx[u << 1 ^ 1]);
    587 }
    588 
    589 int main() {
    590     ios::sync_with_stdio(0), cin.tie(0);
    591     cin >> n >> q;
    592     for (int i = 1; i <= n; i++) {
    593         cin >> a[i];
    594     }
    595     for (int i = 1; i <= n; i++) {
    596         cin >> b[i];
    597     }
    598     for (int i = 1; i < n; i++) {
    599         cin >> c[i];
    600     }
    601     ll sma = 0;
    602     for (int i = n; i >= 1; i--) {
    603         v[i] = a[i] - b[i];
    604         sv[i] = v[i] + sv[i + 1];
    605         sma += a[i];
    606     }
    607     init();
    608     while (q--) {
    609         int p, x, y; ll z; cin >> p >> x >> y >> z;
    610         sma -= a[p];
    611         incre(1, p, -v[p]);
    612         a[p] = x;
    613         b[p] = y;
    614         v[p] = a[p] - b[p];
    615         sma += a[p];
    616         incre(1, p, v[p]);
    617         cout << sma - max(0ll, mx[1]) << '\n';
    618     }
    619 }
    620 ```
    621 
    622 ### [1919F2 - Wine Factory (Hard Version)](/contest/1919/problem/F2 "Hello 2024")
    623 
    624 Author: [maomao90](/profile/maomao90 "Grandmaster maomao90")
    625 
    626 **Hint 1**
    627 
    628 Try modelling this problem into a maximum flow problem.
    629 
    630 **Hint 2**
    631 
    632 Try using minimum cut to find the maximum flow.
    633 
    634 **Hint 3**
    635 
    636 Speed up finding the minimum cut using a segment tree.
    637 
    638 **Solution**
    639 
    640 Consider a flow graph with $n + 2$ vertices. Let the source vertex be $s = n + 1$ and the sink vertex be $t = n + 2$. For each $i$ from $1$ to $n$, add edge $s\rightarrow i$ with capacity $a_i$ and another edge $i\rightarrow t$ with capacity $b_i$. Then for each $i$ from $1$ to $n - 1$, add edge $i\rightarrow i + 1$ with capacity $c_i$. The maximum flow from $s$ to $t$ will be the answer to the problem.
    641 
    642 Let us try to find the minimum cut of the above graph instead.
    643 
    644 **Claim**: The minimum cut will contain exactly one of $s\rightarrow i$ or $i\rightarrow t$ for all $1\le i\le n$.
    645 
    646 *Proof*: If the minimum cut does not contain both $s\rightarrow i$ and $i\rightarrow t$, $s$ can reach $t$ through vertex $i$ and hence it is not a minimum cut. Now, we will prove why the minimum cut cannot contain both $s\rightarrow i$ and $i\rightarrow t$. Suppose there exists a minimum cut where there exists a vertex $1\le i\le n$ where $s\rightarrow i$ and $i\rightarrow t$ are both in the minimum cut. We will consider two cases:
    647 
    648 * Case 1: $s$ can reach $i$ (through some sequence of vertices $s\rightarrow j\rightarrow j+1\rightarrow \ldots \rightarrow i$ where $j \lt i$). If our minimum cut only contains $i\rightarrow t$ without $s\rightarrow i$, nothing changes as $s$ was already able to reach $i$ when $s\rightarrow i$ was removed. Hence, $s$ will still be unable to reach $t$ and we found a minimum cut that has equal or smaller cost.
    649 * Case 2: $s$ cannot reach $i$. If our minimum cut only contains $s\rightarrow i$ without $i\rightarrow t$, nothing changes as $s$ is still unable to reach $i$, so we cannot make use of the edge $i\rightarrow t$ to reach $t$ from $s$. Hence, $s$ will still be unable to reach $t$ and we found a minimum cut that has equal or smaller cost.
    650 
    651 Now, all we have to do is select for each $1\le i\le n$, whether to cut the edge $s\rightarrow i$ or the edge $i\rightarrow t$. Let us use a string $x$ consisting of characters $\texttt{A}$ and $\texttt{B}$ to represent this. $x_i = \texttt{A}$ means we decide to cut the edge $s\rightarrow i$ for a cost of $a_i$ and $x_i = \texttt{B}$ means we decide to cut the edge from $i\rightarrow t$ for a cost of $b_i$. Notice that whenever we have $x_i = \texttt{B}$ and $x_{i + 1} = \texttt{A}$, $s$ can reach $t$ through $s\rightarrow i\rightarrow i + 1\rightarrow t$. To prevent this, we have to cut the edge $i\rightarrow i + 1$ for a cost of $c_i$.
    652 
    653 To handle updates, we can use a segment tree. Each node of the segment tree stores the minimum possible cost for each of the four combinations of the two endpoints being $\texttt{A}$ or $\texttt{B}$. When merging the segment tree nodes, add a cost of $c$ when the right endpoint of the left node is $\texttt{B}$ and the left endpoint of the right node is $\texttt{A}$. The final time complexity is $O(n\log n)$ as only a segment tree is used.
    654 
    655 **Code**
    656 
    657 ```
    658 #include <bits/stdc++.h> 
    659 using namespace std;
    660 
    661 typedef long long ll;
    662 const ll LINF = 1000000000000000005ll;
    663 const int MAXN = 500005;
    664 
    665 int n, q;
    666 int a[MAXN], b[MAXN];
    667 ll c[MAXN];
    668 
    669 ll st[MAXN * 4][2][2];
    670 void merge(int u, int lo, int hi) {
    671     int mid = lo + hi >> 1, lc = u << 1, rc = u << 1 ^ 1;
    672     for (int l = 0; l < 2; l++) {
    673         for (int r = 0; r < 2; r++) {
    674             st[u][l][r] = min({st[lc][l][0] + st[rc][0][r],
    675                     st[lc][l][1] + st[rc][1][r],
    676                     st[lc][l][0] + st[rc][1][r],
    677                     st[lc][l][1] + st[rc][0][r] + c[mid]});
    678         }
    679     }
    680 }
    681 void init(int u = 1, int lo = 1, int hi = n) {
    682     if (lo == hi) {
    683         st[u][0][0] = a[lo];
    684         st[u][1][1] = b[lo];
    685         st[u][1][0] = st[u][0][1] = LINF;
    686         return;
    687     }
    688     int mid = lo + hi >> 1, lc = u << 1, rc = u << 1 ^ 1;
    689     init(lc, lo, mid);
    690     init(rc, mid + 1, hi);
    691     merge(u, lo, hi);
    692 }
    693 void upd(int p, int u = 1, int lo = 1, int hi = n) {
    694     if (lo == hi) {
    695         st[u][0][0] = a[lo];
    696         st[u][1][1] = b[lo];
    697         st[u][1][0] = st[u][0][1] = LINF;
    698         return;
    699     }
    700     int mid = lo + hi >> 1, lc = u << 1, rc = u << 1 ^ 1;
    701     if (p <= mid) {
    702         upd(p, lc, lo, mid);
    703     } else {
    704         upd(p, rc, mid + 1, hi);
    705     }
    706     merge(u, lo, hi);
    707 }
    708 
    709 int main() {
    710     ios::sync_with_stdio(0), cin.tie(0);
    711     cin >> n >> q;
    712     for (int i = 1; i <= n; i++) {
    713         cin >> a[i];
    714     }
    715     for (int i = 1; i <= n; i++) {
    716         cin >> b[i];
    717     }
    718     for (int i = 1; i < n; i++) {
    719         cin >> c[i];
    720     }
    721     init();
    722     while (q--) {
    723         int p, x, y; ll z; cin >> p >> x >> y >> z;
    724         a[p] = x; b[p] = y; c[p] = z;
    725         upd(p);
    726         cout << min({st[1][0][0], st[1][0][1], st[1][1][0], st[1][1][1]}) << '\n';
    727     }
    728 }
    729 ```
    730 
    731 ### [1919G - Tree LGM](/contest/1919/problem/G "Hello 2024")
    732 
    733 Author: [maomao90](/profile/maomao90 "Grandmaster maomao90")
    734 
    735 **Hint 1**
    736 
    737 Think about how you would construct matrix $s$ if you were given the tree.
    738 
    739 **Hint 2**
    740 
    741 If $s_{i, i} = \mathtt{0}$, what should the value of $s_{j, i}$ be for all $1\le j\le n$?
    742 
    743 **Hint 3**
    744 
    745 For some $i$ where $s_{i, i} = \mathtt{1}$, let $Z$ be a set containing all the vertices $j$ where $s_{j, i} = \mathtt{0}$. More formally, $Z = \{j\ |\ 1\le j\le n\text{ and } s_{j, i} = \mathtt{0}\}$. Does $Z$ have any special properties?
    746 
    747 **Hint 4**
    748 
    749 Using hint 3, can we break down the problem into smaller sub-problems?
    750 
    751 **Hint 5**
    752 
    753 Try solving the problem if the values in each column are a constant. In other words, $s_{i, j} = s_{j, j}$ for all $1\le i\le n$ and $1\le j\le n$.
    754 
    755 **Solution**
    756 
    757 Let us consider how we can code the checker for this problem. In other words, if we are given a tree, how can we construct matrix $s$? We can solve this using dynamic programming. $s_{i, j} = \mathtt{1}$ if and only if at least one child $c$ of vertex $j$ (when the tree is rooted at vertex $i$) has $s_{i, c} = \mathtt{0}$. This is because the player can move the coin from vertex $j$ to vertex $c$ which will cause the opponent to be in a losing state.
    758 
    759 For convenience, we will call a vertex $i$ special if there exists some $1\le j\le n$ where $s_{j, i} \neq s_{i, i}$. Suppose there exist some $i$ where $s_{i, i} = \mathtt{0}$. This means that moving the coin to any of the neighbours of $i$ results in a winning state for the opponent. If the tree was rooted at some other vertex $j\neq i$, it will still be a losing state as it reduces the options that the player can move the coin to, so $s_{j, i}$ should be $\mathtt{0}$ for all $1\le j\le n$. This means that special vertices must have $s_{i, i} = \mathtt{1}$
    760 
    761 Now, let us take a look at special vertices. Let $x$ be a special vertex, meaning $s_{x, x} = \mathtt{1}$ and there exist some $j$ where $s_{j, x} = \mathtt{0}$. Let $Z$ be a set containing all the vertices $j$ where $s_{j, x} = \mathtt{0}$. More formally, $Z = \{j\ |\ 1\le j\le n\text{ and } s_{j, x} = \mathtt{0}\}$. $Z$ cannot be empty due to the property of special vertices. Notice that whenever we choose to root at some vertex $j\neq x$, the number of children of $x$ decreases by exactly $1$. This is because the neighbour that lies on the path from vertex $x$ to vertex $j$ becomes the parent of $x$ instead of the child of $x$. If rooting the tree at vertex $x$ is a winning state but rooting the tree at some other vertex $j$ results in a losing state instead, it means that the only winning move is to move the coin from vertex $x$ to the neighbour that is on the path from vertex $x$ to $j$.
    762 
    763 Let $y$ denote the only neighbour of vertex $x$ where we can move the coin from vertex $x$ to vertex $y$ and win. In other words, $y$ is the neighbour of vertex $x$ where $y$ lies on the path of the vertices in set $Z$ and $x$. This means that $Z$ is the set of vertices that are in the subtree of $y$ rooted at vertex $x$.
    764 
    765 Now, let us try to find vertex $y$. Notice that $s_{y, y} = \mathtt{1}$. This is because $s_{y, x} = \mathtt{0}$, so the coin can be moved from vertex $y$ to vertex $x$ to result in a losing state for the opponent. Furthermore, $s_{j, y} = \mathtt{0}$ if and only if $j$ is not in $Z$, otherwise $s_{j, y} = \mathtt{1}$. This is because $s_{x, y} = \mathtt{0}$ since moving the coin from vertex $x$ to vertex $y$ is a winning move for the first player. For all other vertex $u\in Z$ that is not $y$, this property will not hold as even if $s_{u, u} = \mathtt{1}$ and $s_{x, u} = \mathtt{0}$, $s_{y, u}$ will be equal to $\mathtt{0}$ as well as the tree being rooted at $x$ has the same effect as if it was rooted at $y$. Since $y \in Z$, $s_{y, u} = \mathtt{0}$ does not satisfy $s_{j, u} = \mathtt{1}$ for all $j$ in $Z$.
    766 
    767 Since $y$ is a neighbour of vertex $x$, we know that there is an edge between vertex $y$ and $x$. Furthermore, we know that if the edge between vertex $y$ and $x$ is removed, the set of vertices $Z$ forms a single connected component containing $y$, while the set of vertices not in $Z$ forms another connected component containing $x$. This means that we can recursively solve the problem for the two connected components to check whether the values in the matrix $s$ are valid within their components.
    768 
    769 After recursively solving for each connected component, we are only left with non-special vertices ($s_{j, i} = s_{i, i}$ for all $1\le j\le n$) and some special vertices that already have an edge that connects to outside the component. Non-special vertices with $s_{i, i} = \mathtt{1}$ has to be connected to at least $2$ non-special vertices with $s_{i, i} = \mathtt{0}$. The most optimal way to do this is to form a line 0 — 1 — 0 — 1 — 0 as it requires the least amount of $s_{i, i} = \mathtt{0}$. If there is not enough $s_{i, i} = \mathtt{0}$ to form the line, a solution does not exist. Otherwise, connect the left-over $s_{i, i} = \mathtt{0}$ to any of $s_{i, i} = \mathtt{1}$. On the other hand, special vertices can either be connected to nothing, connected to other special vertices, or connected to non-special vertices with $s_{i, i} = \mathtt{1}$.
    770 
    771 For the final step, we need to check whether $s_{i, j}$ is consistent when $i$ and $j$ are in different components (i.e. ($i\in Z$ and $j\notin Z$) or ($i\notin Z$ and $j\in Z$)). Notice that $s_{i, j} = s_{x, j}$ for all $i\in Z$ and $j\notin Z$ and $j\neq x$, and $s_{i, j} = s_{y, j}$ for all $i\notin Z$ and $j\in Z$ and $j\neq y$. From the steps above, we managed to account for every value in the matrix, hence if matrix $s$ is consistent through all the steps, the constructed tree would be valid as well.
    772 
    773 We can make use of xor hash to find vertex $x$ together with its corresponding vertex $y$. With xor hash, the time complexity is $O(n^2)$. Well-optimised bitset code with time complexity of $O(\frac{n^3}{w})$ can pass as well.
    774 
    775 **Code**
    776 
    777 ```
    778 #include <bits/stdc++.h> 
    779 using namespace std;
    780  
    781 const int MAXN = 5005;
    782 
    783 mt19937_64 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
    784  
    785 int n;
    786 unsigned long long r[MAXN], hsh[MAXN], totr;
    787 string s[MAXN];
    788 vector<pair<int, int>> ans;
    789  
    790 bool done[MAXN];
    791 bool solve(vector<int> grp) {
    792     int pr = -1, pl = -1;
    793     vector<int> lft, rht;
    794     for (int i : grp) {
    795         if (s[i][i] == '0' || done[i] || hsh[i] == totr) {
    796             continue;
    797         }
    798         rht.clear();
    799         for (int j : grp) {
    800             if (s[j][i] == '0') {
    801                 lft.push_back(j);
    802             } else {
    803                 rht.push_back(j);
    804             }
    805         }
    806         if (!lft.empty()) {
    807             pr = i;
    808             break;
    809         }
    810     }
    811     if (pr == -1) {
    812         vector<int> dv, zero, one;
    813         for (int i : grp) {
    814             if (done[i]) {
    815                 dv.push_back(i);
    816             } else if (s[i][i] == '0') {
    817                 zero.push_back(i);
    818             } else {
    819                 one.push_back(i);
    820             }
    821         }
    822         for (int i = 1; i < dv.size(); i++) {
    823             ans.push_back({dv[i - 1], dv[i]});
    824         }
    825         if (one.empty() && zero.empty()) {
    826             return 1;
    827         }
    828         if (one.size() >= zero.size()) {
    829             return 0;
    830         }
    831         if (one.empty()) {
    832             if (zero.size() >= 2 || !dv.empty()) {
    833                 return 0;
    834             }
    835             return 1;
    836         }
    837         for (int i = 0; i < one.size(); i++) {
    838             ans.push_back({zero[i], one[i]});
    839             ans.push_back({one[i], zero[i + 1]});
    840         }
    841         for (int i = one.size() + 1; i < zero.size(); i++) {
    842             ans.push_back({one[0], zero[i]});
    843         }
    844         if (!dv.empty()) {
    845             ans.push_back({one[0], dv[0]});
    846         }
    847         return 1;
    848     }
    849     for (int i : lft) {
    850         if (s[i][i] == '0' || done[i] || ((hsh[i] ^ hsh[pr]) != totr)) {
    851             continue;
    852         }
    853         vector<int> trht;
    854         for (int j : grp) {
    855             if (s[j][i] == '0') {
    856                 trht.push_back(j);
    857             }
    858         }
    859         if (trht == rht) {
    860             pl = i;
    861             break;
    862         }
    863     }
    864     if (pl == -1) {
    865         return 0;
    866     }
    867     for (int i : lft) {
    868         for (int j : rht) {
    869             if (j == pr) {
    870                 continue;
    871             }
    872             if (s[i][j] != s[pr][j]) {
    873                 return 0;
    874             }
    875         }
    876     }
    877     for (int i : rht) {
    878         for (int j : lft) {
    879             if (j == pl) {
    880                 continue;
    881             }
    882             if (s[i][j] != s[pl][j]) {
    883                 return 0;
    884             }
    885         }
    886     }
    887     ans.push_back({pl, pr});
    888     done[pl] = done[pr] = 1;
    889     return solve(lft) && solve(rht);
    890 }
    891  
    892 int main() {
    893     ios::sync_with_stdio(0), cin.tie(0);
    894     cin >> n;
    895     for (int i = 0; i < n; i++) {
    896         cin >> s[i];
    897     }
    898     for (int i = 0; i < n; i++) {
    899         r[i] = rnd();
    900         totr ^= r[i];
    901     }
    902     for (int i = 0; i < n; i++) {
    903         for (int j = 0; j < n; j++) {
    904             if (s[i][j] == '1') {
    905                 hsh[j] ^= r[i];
    906             }
    907         }
    908     }
    909     bool pos = 1;
    910     for (int i = 0; i < n; i++) {
    911         if (s[i][i] == '1') {
    912             continue;
    913         }
    914         for (int j = 0; j < n; j++) {
    915             if (s[j][i] == '1') {
    916                 pos = 0;
    917                 break;
    918             }
    919         }
    920     }
    921     if (!pos) {
    922         cout << "NO\n";
    923         return 0;
    924     }
    925     vector<int> v(n, 0);
    926     iota(v.begin(), v.end(), 0);
    927     if (!solve(v)) {
    928         cout << "NO\n";
    929         return 0;
    930     }
    931     cout << "YES\n";
    932     for (auto [u, v] : ans) {
    933         cout << u + 1 << ' ' << v + 1 << '\n';
    934     }
    935 }
    936 ```
    937 
    938 ### [1919H - Tree Diameter](/contest/1919/problem/H "Hello 2024")
    939 
    940 Author: [maomao90](/profile/maomao90 "Grandmaster maomao90")  
    941 Full solution: [dario2994](/profile/dario2994 "International Grandmaster dario2994")
    942 
    943 **Background**
    944 
    945 The original problem allowed $5n$ type 1 queries and $n$ type 2 queries and was used as the last problem of a Div. 2 round. When we opened the round for testing, [dario2994](/profile/dario2994 "International Grandmaster dario2994") solved the problem using $2n$ type 1 queries, and a few days later, he managed to improve his solution to use only $n$ type 1 queries. This was what made us decide to change this round into a Div. 1 round instead of a Div. 2 round.
    946 
    947 ![Dario discord chat](/predownloaded/7e/0f/7e0f6109355289bb3b62a92326171992b995552f.png)
    948 
    949 **Hint 1**
    950 
    951 Try rooting the tree at an **edge**.
    952 
    953 **Hint 2**
    954 
    955 Use $n - 2$ of query $2$ to find the distance of every edge to the root. For convenience, we will call the distance of an edge to the root the depth of the edge.
    956 
    957 **Hint 3**
    958 
    959 We start with only the root edge, then add edges of depth $0$, followed by depth $1, 2, \ldots$
    960 
    961 **Hint 4**
    962 
    963 If we want to add a new edge with depth $i$, we need to attach it to one of the edges with depth $i - 1$. We can let the weight of the edge we want to attach be $10^9$ to force the diameter to pass through it, then let the edges of depth $i - 1$ have weights be different multiples of $n$. This way, we can determine which edges of depth $i - 1$ are used in the diameter (unless the two largest edges are used).
    964 
    965 **Hint 5**
    966 
    967 Make use of isomorphism to handle the case in hint 4 where the largest two edges are used.
    968 
    969 **Hint 6**
    970 
    971 If isomorphism cannot be used, find a leaf edge of a lower depth than the query edge and force the diameter to pass through the leaf edge and the query edge. Then, only 1 edge of depth $i - 1$ will be used and the edge weights for edges of depth $i - 1$ can follow a similar structure as hint 4.
    972 
    973 **Solution**
    974 
    975 We will root the tree at edge $1$. Then, use $n - 2$ of query $2$ to find the distance of every edge to the root. For convenience, we will call the distance of an edge to the root the depth of the edge. Our objective is to add the edges in increasing order of depth, so when we are inserting an edge of depth $i$, all edges of depth $i - 1$ are already inserted and we just have to figure out which edge of depth $i - 1$ we have to attach the edge of depth $i$ to.
    976 
    977 For convenience, the edge weights used in query $1$ will be $1$ by default unless otherwise stated. Let $c_i$ store the list of edges with depth $i$. Suppose we want to insert edge $u$ into the tree and the depth of edge $u$ is $d$. We let the weight of the edge $u$ be $10 ^ 9$ and the weight of edges in $c_{d - 1}$ be $n, 2n, 3n, \ldots, (|c_{d - 1}| - 2)n, (|c_{d - 1}| - 1)n, (|c_{d - 1}| - 1)n$. The diameter will pass through edge $u$, the parent edge of $u$, as well as one edge of weight $(|c_{d - 1}| - 1)n$. If we calculate $\left\lfloor\frac{\text{diameter} - 10^9}{n}\right\rfloor - (|c_{d - 1}| - 1)$, we will be able to tell the index of the parent edge of $u$.
    978 
    979 However, there is one exception. When the parent edge of $u$ is one of the last 2 edges of $c_{d - 1}$, we are unable to differentiate between the two of them as they have the same weight. This is not a problem if the last 2 edges are isomorphic to each other, as attaching $u$ to either parent results in the same tree. For now, we will assume that the last 2 edges of $c_{d - 1}$ are isomorphic to each other.
    980 
    981 However, after attaching edge $u$ to one last 2 edges in $c_{d - 1}$, they are no longer isomorphic. Hence, we need to use a different method to insert the remaining edges of depth $d$. Let the new edge that we want to insert be $v$. Let the weight of edges $u$ and $v$ be $10^9$ and the weights of edges in $c_{d - 1}$ be the same as before. Now, we can use $\left\lfloor\frac{\text{diameter} - 2\cdot 10^9}{n}\right\rfloor$ to determine whether edge $v$ share the same parent as $u$, and if it does not share the same parent, it can still determine the index of the parent edge of $v$. With the additional information of whether edge $v$ shares the same parent as edge $u$, we will be able to differentiate the last 2 edges of $c_{d - 1}$ from each other.
    982 
    983 Now, we just need to handle the issue where the last 2 edges of $c_{d - 1}$ are not isomorphic. When we only have the root edge at the start, the left and right ends of the edge are isomorphic (note that for the root edge, we consider it as 2 separate edges, one with the left endpoint and one with the right endpoint). We try to maintain the isomorphism as we add edges of increasing depth. Suppose the last two edges of $c_{d - 1}$ are isomorphic. Let the two edges be $a$ and $b$. Then, we insert edges of depth $d$ using the above method. Let the child edges attached to $a$ and $b$ be represented by sets $S_a$ and $S_b$ respectively. If either $S_a$ or $S_b$ has sizes at least $2$, the two edges in the same set will be isomorphic, so we can let those 2 edges be the last 2 edges of $c_d$. Now, the sizes of $S_a$ and $S_b$ are both strictly smaller than $2$. If the sizes of both sets are exactly $1$, the two edges from each set will be isomorphic as well as $a$ and $b$ are isomorphic. Now, the only case left is if at least one of the sets is empty.
    984 
    985 Without loss of generality, assume that $S_a$ is empty. Since it is no longer possible to maintain two isomorphic edges, we now change our objective to find a leaf (it will be clear why in the following paragraphs). If $S_b$ is empty as well, both $a$ and $b$ are leaves so we can choose any one of them. If $S_b$ is not empty, then $a$ and $b$ are no longer isomorphic due to their children. This means that we cannot simply use $b$ as the leaf $S_a$ might be children of $b$ instead of $a$ as we did not differentiate $a$ and $b$ in the previous paragraphs. To determine whether $S_a$ belongs to $a$ or $b$, we can make use of one type 2 query to find the distance between one of the edges in $S_a$ and $a$. If the distance is $0$, it means that $S_a$ belongs to $a$. Otherwise, the distance will be $1$ and $S_a$ belongs to $b$.
    986 
    987 Now that we found a leaf, we can use the following method to insert an edge $u$ of depth $d$. We let the weight of the edge $u$ and the leaf edge be $10 ^ 9$ and the weight of edges in $c_{d - 1}$ be $n, 2n, 3n, \ldots, (|c_{d - 1}| - 2)n, (|c_{d - 1}| - 1)n, |c_{d - 1}|n$. The diameter will pass through edge $u$, the leaf edge, and only one edge of depth $d - 1$ which is the parent edge of $u$. Hence, after finding a leaf edge, we can uniquely determine the parent edge from $\left\lfloor\frac{\text{diameter} - 2\cdot 10^9}{n}\right\rfloor$.
    988 
    989 We used $n - 2$ type 1 queries and $n - 1$ type 2 queries in total. This is because we used a single type 1 query for each non-root edge. We used $n - 2$ type 2 queries at the start, and we only used $1$ additional type 2 query when we were no longer able to maintain two isomorphic edges and changed our methodology to use a leaf edge instead.
    990 
    991 **Code**
    992 
    993 ```
    994 #include <bits/stdc++.h> 
    995 using namespace std;
    996 
    997 typedef long long ll;
    998 const int INF = 1000000000;
    999 const int MAXN = 1000;
   1000 
   1001 int n;
   1002 int lvl[MAXN + 5];
   1003 int pe[MAXN + 5];
   1004 vector<int> ch[MAXN + 5];
   1005 
   1006 ll query(vector<int> a) {
   1007     cout << "? 1";
   1008     for (int i = 1; i < n; i++) {
   1009         cout << ' ' << a[i];
   1010     }
   1011     cout << endl;
   1012     ll res; cin >> res;
   1013     return res;
   1014 }
   1015 int query(int a, int b) {
   1016     cout << "? 2 " << a << ' ' << b << endl;
   1017     int res; cin >> res;
   1018     return res;
   1019 }
   1020 
   1021 int main() {
   1022     cin >> n;
   1023     for (int i = 2; i < n; i++) {
   1024         lvl[i] = query(1, i);
   1025     }
   1026     int ptr = 3;
   1027     vector<int> base = {1, 2};
   1028     pe[1] = pe[2] = 1;
   1029     bool iso = 1;
   1030     int piv = -1;
   1031     for (int l = 0; l < n; l++) {
   1032         vector<int> a(n, 1);
   1033         int m = base.size();
   1034         for (int i = 0; i < m; i++) {
   1035             a[pe[base[i]]] = min(i + 1, m - iso) * MAXN;
   1036         }
   1037         if (!iso) {
   1038             a[pe[piv]] = INF;
   1039         }
   1040         bool ciso = 0;
   1041         for (int u = 2; u < n; u++) {
   1042             if (lvl[u] != l) {
   1043                 continue;
   1044             }
   1045             a[u] = INF;
   1046             ll res = query(a) - INF;
   1047             a[u] = 1;
   1048             if (!iso || ciso) {
   1049                 res -= INF;
   1050             }
   1051             int id = res / MAXN;
   1052             if (iso && l) {
   1053                 id -= m - 1;
   1054             }
   1055             int v = ptr++;
   1056             pe[v] = u;
   1057             if (ciso) {
   1058                 if ((l == 0 && id == 0) || id == -(m - 1)) {
   1059                     ch[base[m - 2]].push_back(v);
   1060                 } else if (id == m - 1) {
   1061                     ch[base[m - 1]].push_back(v);
   1062                 } else {
   1063                     ch[base[id - 1]].push_back(v);
   1064                 }
   1065             } else if (iso && id == m - 1) {
   1066                 ch[base[m - 2]].push_back(v);
   1067                 ciso = 1;
   1068                 a[u] = INF;
   1069             } else {
   1070                 ch[base[id - 1]].push_back(v);
   1071             }
   1072         }
   1073         if (m >= 2 && ch[base[m - 2]].size() > ch[base[m - 1]].size()) {
   1074             swap(base[m - 2], base[m - 1]);
   1075         }
   1076         vector<int> nbase;
   1077         for (int i = 0; i < m; i++) {
   1078             for (int j : ch[base[i]]) {
   1079                 nbase.push_back(j);
   1080             }
   1081         }
   1082         if (!iso || ch[base[m - 1]].size() >= 2 || ch[base[m - 2]].size() == 1) {
   1083             base = nbase;
   1084             continue;
   1085         }
   1086         if (ch[base[m - 1]].empty()) {
   1087             piv = base[m - 1];
   1088         } else {
   1089             ll res = query(pe[ch[base[m - 1]][0]], pe[base[m - 1]]);
   1090             if (res) {
   1091                 swap(base[m - 2], base[m - 1]);
   1092                 swap(ch[base[m - 2]], ch[base[m - 1]]);
   1093             }
   1094             piv = base[m - 2];
   1095         }
   1096         iso = 0;
   1097         base = nbase;
   1098     }
   1099     cout << '!' << endl;
   1100     cout << 1 << ' ' << 2 << endl;
   1101     for (int u = 1; u <= n; u++) {
   1102         for (int v : ch[u]) {
   1103             cout << u << ' ' << v << endl;
   1104         }
   1105     }
   1106 }
   1107 ```