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