2127.md (52847B)
1 Source: https://codeforces.com/blog/entry/145357 2 3 ### ✨ **Hope you enjoyed the problems!** ✨ 4 5 [2127A - Mix Mex Max](/contest/2127/problem/A) 6 **Idea:** [Bahamin](/profile/Bahamin "Master Bahamin") 7 **Preparation:** [Hamed_Ghaffari](/profile/Hamed_Ghaffari "Grandmaster Hamed_Ghaffari") 8 9 **Hints** 10 11 **Hint 1** 12 13 What happens if $\operatorname{mex}([a_i, a_{i+1}, a_{i+2}]) = 0$? 14 15 **Hint 2** 16 17 Now what happens if $\operatorname{mex}([a_i, a_{i+1}, a_{i+2}]) \neq 0$? 18 19 **Solution** 20 21 Let's see when does $\operatorname{mex}([a_i, a_{i+1}, a_{i+2}])$ equal $\max([a_i, a_{i+1}, a_{i+2}]) - \min([a_i, a_{i+1}, a_{i+2}])$. 22 23 **Case 1:** $\operatorname{mex}([a_i, a_{i+1}, a_{i+2}]) = 0$ 24 25 This implies that all numbers are equal and non-zero, since otherwise $\min$ would be less than $\max$ and the difference wouldn't be $0$. 26 27 **Case 2:** $\operatorname{mex}([a_i, a_{i+1}, a_{i+2}]) \neq 0$ 28 29 In this case $\min([a_i, a_{i+1}, a_{i+2}])$ should be $0$ because $0$ is in the sequence. So $\operatorname{mex}([a_i, a_{i+1}, a_{i+2}]) = \max([a_i, a_{i+1}, a_{i+2}])$ but this is not possible, since $\operatorname{mex}([a_i, a_{i+1}, a_{i+2}])$ should not be among $a_i$, $a_{i+1}$, or $a_{i+2}$. 30 31 So an array is good if all elements are equal and non-zero. Remove every $-1$ from $a$, then check whether all remaining elements are equal and non-zero. 32 33 **Code** 34 35 ``` 36 #include <bits/stdc++.h> 37 38 using namespace std; 39 40 int main() { 41 int tc; 42 cin >> tc; 43 while (tc--) { 44 int n; 45 cin>>n; 46 vector<int> v(n); 47 for (int i = 0; i < n; i++) cin >> v[i]; 48 set<int> s(v.begin(), v.end()); 49 50 s.erase(-1); 51 if (s.size()<=1 && !s.count(0)) cout<<"YES"<<endl; 52 else cout<<"NO"<<endl; 53 } 54 } 55 ``` 56 57 --- 58 59 [2127B - Hamiiid, Haaamid... Hamid?](/contest/2127/problem/B) 60 **Idea:** [_R00T](/profile/_R00T "Master _R00T") and [Error_Yuan](/profile/Error_Yuan "Grandmaster Error_Yuan") 61 **Preparation:** [_R00T](/profile/_R00T "Master _R00T") and [Hamed_Ghaffari](/profile/Hamed_Ghaffari "Grandmaster Hamed_Ghaffari") 62 63 **Hints** 64 65 **Hint 1** 66 67 The answer to the problem only depends on $x$, $n$, the index of the wall Hamid would hit if he moves to the left, and the index of the wall he would hit if he moves to the right. 68 69 **Hint 2** 70 71 If we denote the two indices defined in Hint 1 as $L$ and $R$, then in each of Hamid's turns, he can move in a way that ensures by the next time, either $L$ has decreased by at least one, or $R$ has increased by at least one, regardless of Mani's moves. So, if it's Hamid's turn, what is the maximum possible answer in terms of $L$, $R$, and $n$? 72 73 **Answer** 74 75 The answer is at most $\min(L + 1, n - R + 2)$. 76 77 **Solution** 78 79 Suppose it's Hamid's turn. If there is no wall to his right or to his left, he can escape the grid in one move. Otherwise, define: 80 81 * $L$ as the index of the wall Hamid would reach if he moves to the left. 82 * $R$ as the index of the wall he would reach if he moves to the right. 83 84 Hamid can move to the left and decrease $L$ by at least one. (Since $L$ is always to the left of Hamid's current position, when Hamid moves left, he reaches and destroys the wall at position L. As a result, on his next turn, the new L will be at least one position further to the left. meaning $L$ decreases by at least one, regardless of Mani's actions.) Similarly, Hamid can increase $R$ by at least $1$ by moving to the right and destroying the wall there. 85 86 So, since Hamid wants to escape in the minimum number of moves, he can escape the grid in at most $\min(L + 1, n - R + 2)$ moves. 87 88 On the other hand, with each of Hamid's moves, Mani can place a wall in such a way that $L$ decreases by at most one or R increases by at most one. 89 90 So the minimum number of moves Hamid needs is also $\min(L + 1, n - R + 2)$. 91 92 Therefore, assuming Hamid starts first, the answer is $\min(L + 1, n - R + 2)$. 93 94 Now consider Mani's first move. Since Mani wants to maximize the number of days Hamid needs. Moreover, with each of his moves, at least one of the $L$ or $R$ remains unchanged. So, on his first move, he can: 95 96 * maximize $L + 1$ by setting $L = x - 1$, or 97 * maximize $n - R + 2$ by minimizing $R$, setting it to $x + 1$. 98 99 So the answer becomes either $\min((x-1) + 1, n - R + 2)$ or $\min(L + 1, n - (x+1) + 1)$. 100 101 Because Mani wants the number of days to be as large as possible, the final answer is: $\max(\min(x, n - R + 2), \min(L + 1, n - x + 1))$ 102 103 We can easily find L and R with a time complexity of $\mathcal{O}(n)$. Therefore, the problem is solved in $\mathcal{O}(n)$ time complexity. 104 105 **Code** 106 107 ``` 108 #include<bits/stdc++.h> 109 using namespace std; 110 111 int32_t main() { 112 cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0); 113 int tc; 114 cin >> tc; 115 while(tc--) { 116 int n, x; 117 string s; 118 cin >> n >> x >> s; 119 if(x==1 || x==n) { 120 cout << "1\n"; 121 continue; 122 } 123 x--; 124 int inf = 1e9; 125 int lf=-inf, rg=inf; 126 for(int i=x-1; i>=0; i--) 127 if(s[i]=='#') { 128 lf=i; 129 break; 130 } 131 for(int i=x+1; i<n; i++) 132 if(s[i]=='#') { 133 rg=i; 134 break; 135 } 136 if(lf==-inf && rg==inf) { 137 cout << "1\n"; 138 continue; 139 } 140 cout << max(min(x+1, n-rg+1), min(lf+2, n-x)) << '\n'; 141 } 142 return 0; 143 } 144 ``` 145 146 --- 147 148 [2127C - Trip Shopping](/contest/2127/problem/C) 149 **Idea:** [Bahamin](/profile/Bahamin "Master Bahamin") 150 **Preparation:** [Bahamin](/profile/Bahamin "Master Bahamin") and [_R00T](/profile/_R00T "Master _R00T") 151 152 **Hints** 153 154 **Hint 1** 155 156 We can see that permuting arrays $a$ and $b$ **in the same way** or changing $a_i$ with $b_i$ for a specific index $i$ doesn't change the answer. WLOG assume $a_i \leq b_i$ is always true. 157 158 **Hint 2** 159 160 Imagine Ali selects indices $i$ and $j$ in a round of game. What are all the different new arrays Bahamin can achieve? 161 162 Can Ali ever achieve a $value$ less that the initial $value$? 163 164 **Answer** 165 166 He can't. Because Bahamin can always keep the chosen indices as they are, and so the $value$ won't change. No matter what Ali does. 167 168 **Solution** 169 170 Read the hints. 171 172 Let’s first address hint $2$. To determine all arrays that Bahamin can reach, WLOG assume $a_i \leq b_i \leq a_j \leq b_j$. The specific order doesn't matter, since Bahamin can permute them freely. Set $x_1 = a_i$, $x_2 = b_i$, $x_3 = a_j$, $x_4 = b_j$ — this makes the following cases reachable for Bahamin: 173 174 1. $a_i := x_1, b_i := x_2, a_j := x_3, b_j := x_4 \rightarrow \space value = x_2 - x_1 + x_4 - x_3$ 175 2. $a_i := x_1, b_i := x_3, a_j := x_2, b_j := x_4 \rightarrow \space value = x_3 - x_1 + x_4 - x_2$ 176 3. $a_i := x_1, b_i := x_4, a_j := x_2, b_j := x_3 \rightarrow \space value = x_4 - x_1 + x_3 - x_2$ 177 178 Other cases are similar (based on Hint $1$). We observe that the second and third options yield the same $value$, while the first option is exactly $2 \times (x_3 - x_2)$ **less** than the other two. There are now two possible cases: 179 180 **Case 1:** Ali can choose two indices $i$ and $j$ such that the ordering of $[a_i, b_i, a_j, b_j]$ already matches one of the second or third options. In this case, Bahamin cannot increase the value when he is **initially** given indices $i$ and $j$. Since Ali also cannot reduce the $value$, his optimal strategy is to always give Bahamin such indices so that the final $value$ remains equal to the initial $value$. 181 182 **Case 2:** Ali cannot find any two indices $i$ and $j$ that match the second or third option. This implies that for every pair of indices $i, j$, either $b_i \lt a_j$ or $b_j \lt a_i$. We claim the answer is $\sum\limits_{i=1}^{n} (b_i - a_i) + \min\limits_{1 \leq i, j \leq n, \space b_i \lt a_j} (2 \times (a_j - b_i))$. 183 184 A strategy for Ali is to always select the two indices $i, j$ such that $b_i \lt a_j$ and the difference $a_j - b_i$ is minimized. Bahamin can increase the $value$ only once — when he changes the configuration of indices $i, j$ from the first option to either the second or third option. We know this increases the initial $value$ by exactly $2 \times (a_j - b_i)$. Also, it's impossible for Ali to force any $value$ lower than this. Since regardless of Ali's selection, Bahamin can always change it to the second or third option, and by definition, any choice by Ali gives Bahamin a chance to increase $value$ by **at least** our claimed amount. Also Bahamin should skip his turn (i.e., make no changes) on all subsequent turns after the first. 185 186 Now to calculate the answer so that it fits the time limit, let’s first represent our array as a set of $n$ segments of the form $[a_i, b_i]$ on the number line. An interesting property of this representation is that the first option now corresponds to two completely separate intervals, while the second and third options correspond to two intersecting intervals. 187 188 Now finding the answer becomes relatively easy. Sort the intervals by their left endpoint. If there are two neighboring intervals that intersect, then the input satisfies the **Case 1** condition, and so the answer is the initial $value$. Otherwise, we observe that all pairs of intervals are non-intersecting, and thus the input satisfies the **Case 2** condition. The answer, based on **Case 2** and our earlier definitions, is $2 \times (\text{distance between closest two segments}) + (\text{initial value})$. 189 190 The two closest intervals must also be adjacent after sorting by their left endpoint. So, by computing the minimum distance between each pair of neighboring intervals, we obtain a solution in $\mathcal{O}(n \log n)$. 191 192 **Code** 193 194 ``` 195 #include <bits/stdc++.h> 196 using namespace std; 197 198 const int MXN = 2e5+5; 199 200 int n, k, a[MXN]; 201 202 void Main() { 203 cin >> n >> k; 204 for(int i=1; i<=n; i++) cin >> a[i]; 205 vector<pair<int, int>> vec; 206 long long ans = 0; 207 for(int i=1, b; i<=n; i++) { 208 cin >> b; 209 if(b<a[i]) swap(b, a[i]); 210 ans += b-a[i]; 211 vec.push_back({a[i], b}); 212 } 213 sort(vec.begin(), vec.end()); 214 for(int i=1; i<n; i++) 215 if(vec[i].first<=vec[i-1].second) { 216 cout << ans << '\n'; 217 return; 218 } 219 int mn = 2e9; 220 for(int i=1; i<n; i++) 221 mn = min(mn, vec[i].first - vec[i-1].second); 222 cout << ans + 2*mn << '\n'; 223 } 224 225 int32_t main() { 226 cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0); 227 int tc; 228 cin >> tc; 229 while(tc--) Main(); 230 } 231 ``` 232 233 **Bonus** 234 235 There were completely different versions of this problem at first. 236 237 The original version was that Ali and Bahamin would take turns, and on each turn, a player would perform **both** operations described in the problem. Their goals and the constraints were similar to what is stated in the final version of the question. 238 239 Can you solve it? 240 241 --- 242 243 [2127D - Root was Built by Love, Broken by Destiny](/contest/2127/problem/D) 244 **Idea:** [_R00T](/profile/_R00T "Master _R00T") and [Bahamin](/profile/Bahamin "Master Bahamin") 245 **Preparation:** [_R00T](/profile/_R00T "Master _R00T") and [Hamed_Ghaffari](/profile/Hamed_Ghaffari "Grandmaster Hamed_Ghaffari") 246 247 **Hints** 248 249 **Hint 1** 250 251 We can prove that the map of Destinyland contains no cycles. 252 253 **Hint 2** 254 255 Take a look at the map below: 256  257 258 **Hint 3** 259 260 Prove that a tree can be a valid Destinyland map if and only if it does **not** contain a subtree that looks like the one shown in **Hint 2**. 261 262 **Hint 4** 263 264 If we remove all the leaves from the Destinyland tree, the remaining graph forms a simple path. 265 266 **Solution** 267 268 Let $G$ be the graph of the Destinyland map. 269 270 If there exists a subgraph $H$ of $G$ that cannot be a valid Destinyland map, then $G$ itself cannot be valid either. 271 272 To prove this, assume, for contradiction, that $G$ is valid but $H$ is not. Then, by removing the vertices and edges not in $H$, we get a subgraph $H$ that should also be valid. But it isn't! This contradicts our assumption, so $G$ cannot be valid either. 273 274 **Lemma 1:** A cycle of any length **cannot** be a valid Destinyland map. 275 **Proof:** Assume the opposite. Let $v$ be the leftmost house on the northern side. It has two neighbors on the southern side. Let the one on the left be $L$ and the other one $R$. Since $L$ must have another neighbor besides $v$, that neighbor cannot be on the southern side, so it must be on the northern side. However, since $v$ is the leftmost node, this neighbor must be to the right of $v$, and the edge between $L$ and this neighbor would cross the edge $v$—$L$. This contradiction shows that $L$ cannot have another neighbor besides $v$, which contradicts our assumption that the graph is a cycle. 276 277 **Lemma 2:** The following tree **cannot** be a valid Destinyland map: 278  279 **Proof:** Vertices $2$, $3$, and $4$ are all on the side opposite vertex $1$. If we place them in order from left to right as $u_1$, $u_2$, and $u_3$, then the neighbor of $u_2$ will necessarily create a crossing either with edge $1$—$u_1$ or $1$—$u_3$. Therefore, it is impossible to arrange the vertices of this tree in a valid Destinyland layout. 280 281 282 From **Lemma 1** and **Lemma 2**, we conclude that: 283 284 * $G$ must be a tree. 285 * No vertex in $G$ can be connected to three or more non-leaf neighbors. 286 287 Now, remove all the leaf nodes. Since these leaves are always non-cut vertices (i.e., their removal doesn't disconnect the tree), the remaining graph, if it exists, is still connected. Since all remaining vertices have degree at most $2$. So the resulting structure must be a **path**. 288 289 **Case 1:** The graph becomes empty after removing leaves. 290 In this case, the original graph was just a single edge. So the answer is simply $2$. 291 292 **Case 2:** Only one vertex remains. 293 In this case, the original tree was a star. Depending on which side we place the central vertex, and how we permute the leaves, the answer is: $2\times(n−1)!$ 294 295 **Case 3:** Two connected non-leaf vertices $u$ and $v$ remain. 296 In this case, there are $4$ valid placements depending on which one is on the northern side and how their adjacent leaves are arranged around the other. ( **Note:** It's impossible for either $u$ or $v$ to have neighbors on both sides of the other.) 297 So the answer is: $4\times(d_u−1)!\times(d_v−1)!$ where $d_u$ and $d_v$ are the degrees of $u$ and $v$, respectively. 298 299 **Case 4:** The remaining structure is a path of length at least $3$. 300 In this case, we have $4$ valid ways to place it. These depend on which vertices are placed on the northern side, and how the two vertices from one side with at least two vertices are positioned. (Since the path has at least $3$ vertices, there's no conflict.) 301 302 Now, we only need to arrange the leaves adjacent to each vertex relative to each other. Because their positions relative to the other vertices depend only on the four ways to arrange the main path. The proof of that is boring, so we won’t bore you with it :) 303 304 Let $S$ be the set of vertices on the path, and let $Saha_i$ be the number of leaves connected to vertex $i$. Then the total number of valid layouts is: $4 \times \prod\limits_{r \in S} (Saha_r!)$ 305 306 To implement the solution: 307 308 1. Check if the input graph is a tree. 309 2. Verify that no vertex has more than two non-leaf neighbors. 310 3. Count the number of non-leaf vertices. 311 4. Based on that count, determine which case applies and compute the answer accordingly. 312 313 The entire algorithm runs in $\mathcal{O}(n)$ time. 314 315 **Code** 316 317 ``` 318 #include <bits/stdc++.h> 319 using namespace std; 320 321 #define SZ(x) int(x.size()) 322 323 const int MOD = 1e9 + 7; 324 const int MXN = 2e5 + 5; 325 326 int n, m, fact[MXN]; 327 vector<int> adj[MXN]; 328 329 int32_t main() { 330 cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0); 331 fact[0] = 1; 332 for (int i = 1; i < MXN; i++) 333 fact[i] = (1ll * fact[i-1] * i) % MOD; 334 int T; 335 cin >> T; 336 while (T--) { 337 cin >> n >> m; 338 for (int i = 1; i <= n; i++) adj[i].clear(); 339 for (int i = 1; i <= m; i++) { 340 int u, v; 341 cin >> u >> v; 342 adj[u].push_back(v); 343 adj[v].push_back(u); 344 } 345 346 long long ans = 2; 347 int tl = 0; 348 if (m >= n) ans = 0; 349 for (int u = 1; u <= n; u++) { 350 if (adj[u].size() > 1) { 351 int x = 0; 352 for (int v : adj[u]) { 353 x += (SZ(adj[v]) == 1); 354 } 355 if (x >= SZ(adj[u]) - 2) (ans *= fact[x]) %= MOD; 356 else ans = 0; 357 } else tl ++; 358 } 359 if (tl < n-1) tl = 2; else tl = 1; 360 cout << (ans * tl % MOD) << '\n'; 361 } 362 return 0; 363 } 364 ``` 365 366 --- 367 368 [2127E - Ancient Tree](/contest/2127/problem/E) 369 **Idea:** [Bahamin](/profile/Bahamin "Master Bahamin") 370 **Preparation:** [Bahamin](/profile/Bahamin "Master Bahamin") and [Hamed_Ghaffari](/profile/Hamed_Ghaffari "Grandmaster Hamed_Ghaffari") 371 372 **Hints** 373 374 **Hint 1** 375 376 There are some vertices that will always be *cutie*, no matter how the other vertices are colored. What are these vertices? 377 378 **Hint 2** 379 380 We can show that there exists a coloring where only the vertices mentioned in **Hint 1** become *cutie*. So, the final answer is the sum of the weights of the vertices mentioned in **Hint 1**. 381 382 **Solution** 383 384 Read the hints. 385 386 We will use a very useful and interesting technique called the **Virtual Tree** (or **Auxiliary Tree**). You can learn more here: [Virtual Tree](https://usaco.guide/plat/VT?lang=cpp). There are other solutions to this problem, but they use a similar core idea. 387 388 The **virtual tree** of a set of vertices like $S$ is defined as this set: 389 390 $A = S \cup \{\operatorname{lca}(u, v) \mid u, v \in S \}$ 391 392 Now let's build this virtual tree for the vertices of each color separately. After this, all vertices fall into three categories: 393 394 1. Vertices that are in no virtual tree. 395 2. Vertices that are in exactly one virtual tree. 396 3. Vertices that appear in more than one virtual tree. 397 398 Every vertex like $u$ of the third type will definitely be *cutie*, because no matter what color it is assigned, at least one of the colors of the virtual trees it belongs to will be different from $u$'s color. 399 400 So the answer is at least the sum of the weights of all type-3 vertices. 401 402 To construct an example with exactly this answer, run a $DFS$ algorithm. Every time you enter a vertex $u$, consider the following cases: 403 404 * It's type 2. In that case, color it with the color of the virtual tree it belongs to. 405 * It's type 3. In that case, color it with any color from its subtree (such a color exists by definition). This vertex is *cutie* anyway. 406 * It's type 1 and there is some colored vertex in its subtree. Then color this vertex with that color. 407 * It's type 1 and its entire subtree is uncolored. In that case, color this vertex with its parent's color. 408 409 To prove this coloring is valid, observe that coloring a vertex $u$ with a color from its subtree does not make any new vertices *cutie* (because any such vertex would already have become *cutie* due to the same color in $u$'s subtree). Also, no vertex strictly inside $u$'s subtree changes status. And $u$ itself doesn't increase the cost based on how we chose its color. 410 411 Now, for the case where we color $u$ with its parent’s color: if any new *cutie* vertex appears, it must be the parent. But since both have the same color, there’s no additional cost. 412 413 Also, in this constructed example, we never introduce any new colors. So all colors stay within the range $[1, k]$. 414 415 Therefore, the final answer is always the sum of the weights of **type-3 vertices**—those that appear in more than one virtual tree. These virtual trees can be constructed in $\mathcal{O}(n \log n)$. 416 417 **Code** 418 419 ``` 420 #include <bits/stdc++.h> 421 using namespace std; 422 423 using ll = long long; 424 425 const int MXN = 2e5+1, LOG = 18; 426 427 int n, k, w[MXN], c[MXN], par[LOG][MXN], stt[MXN], timer, h[MXN], cnt[MXN], col[MXN]; 428 vector<int> g[MXN], cols[MXN]; 429 bool mark[MXN], cutie[MXN]; 430 431 void dfs(int v) { 432 stt[v] = timer++; 433 for(int i=1; i<LOG; i++) par[i][v] = par[i-1][par[i-1][v]]; 434 for(int u : g[v]) 435 if(u!=par[0][v]) { 436 h[u] = h[v]+1; 437 par[0][u] = v; 438 dfs(u); 439 } 440 } 441 442 inline int jump(int v, int d) { 443 for(int i=0; i<LOG; i++) 444 if(d>>i&1) 445 v = par[i][v]; 446 return v; 447 } 448 449 inline int LCA(int u, int v) { 450 if(h[u]<h[v]) swap(u, v); 451 u = jump(u, h[u]-h[v]); 452 if(u==v) return u; 453 for(int i=LOG-1; i>=0; i--) 454 if(par[i][u]!=par[i][v]) 455 u = par[i][u], v = par[i][v]; 456 return par[0][u]; 457 } 458 459 void DFS(int v, int cc) { 460 if(c[v]) cc=c[v]; 461 else c[v]=cc; 462 for(int u : g[v]) 463 if(u!=par[0][v]) 464 DFS(u, cc); 465 } 466 467 void Main() { 468 cin >> n >> k; 469 timer = 0; 470 for(int i=1; i<=n; i++) { 471 cnt[i] = 0; 472 col[i] = 0; 473 g[i].clear(); 474 cutie[i] = 0; 475 cols[i].clear(); 476 } 477 for(int i=1; i<=n; i++) cin >> w[i]; 478 for(int i=1; i<=n; i++) cin >> c[i], cols[c[i]].push_back(i); 479 for(int i=1, u,v; i<n; i++) { 480 cin >> u >> v; 481 g[u].push_back(v); 482 g[v].push_back(u); 483 } 484 bool fnd=0; 485 for(int i=1; i<=n; i++) 486 fnd |= c[i]; 487 if(!fnd) { 488 cout << "0\n"; 489 for(int i=1; i<=n; i++) cout << "1 "; 490 cout << '\n'; 491 return; 492 } 493 dfs(1); 494 for(int i=1; i<=k; i++) { 495 sort(cols[i].begin(), cols[i].end(), [&](int u, int v) { 496 return stt[u]<stt[v]; 497 }); 498 vector<int> V; 499 for(int j=0, u, v, lca; j+1<int(cols[i].size()); j++) { 500 u = cols[i][j], v = cols[i][j+1], lca = LCA(u, v); 501 if(!mark[lca]) { 502 if(c[lca]) { 503 if(c[lca] != i) cutie[lca] = 1; 504 continue; 505 } 506 mark[lca] = 1; 507 cnt[lca]++; 508 col[lca] = i; 509 V.push_back(lca); 510 } 511 } 512 for(int v : V) mark[v] = 0; 513 cols[i].clear(); 514 } 515 ll val=0; 516 for(int i=1; i<=n; i++) { 517 if(cutie[i] || cnt[i]>1) val += w[i]; 518 if(!c[i] && cnt[i]==1) c[i] = col[i]; 519 } 520 cout << val << '\n'; 521 for(int i=1; i<=n; i++) 522 if(c[i]) { 523 DFS(1, c[i]); 524 break; 525 } 526 for(int i=1; i<=n; i++) cout << c[i] << ' '; 527 cout << '\n'; 528 } 529 530 int32_t main() { 531 cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0); 532 int tc; 533 cin >> tc; 534 while(tc--) Main(); 535 return 0; 536 } 537 ``` 538 539 --- 540 541 [2127F - Hamed and AghaBalaSar](/contest/2127/problem/F) 542 **Idea:** [Hamed_Ghaffari](/profile/Hamed_Ghaffari "Grandmaster Hamed_Ghaffari") and [_R00T](/profile/_R00T "Master _R00T") 543 **Preparation:** [Hamed_Ghaffari](/profile/Hamed_Ghaffari "Grandmaster Hamed_Ghaffari") 544 545 **Hints** 546 547 **Hint 1** 548 549 What exactly is $f(a)$? 550 551 **Answer** 552 553 $f(a)$ is the sum of maximums minus the sum of element right after a maximum minus $a_1$. 554 555 **Hint 2** 556 557 Fix the maximum. How to count the sum of maximums? 558 559 **Hint 3** 560 561 You need to solve the following sub-problem: 562 563 You are given three integers $n$, $m$, and $x$. How many arrays $a_1,a_2,\ldots,a_n$ exists such that: 564 565 * $0 \leq a_i \leq x$ for all $1 \leq i \leq n$ 566 * $a_1 + a_2 + \ldots + a_n = m$ 567 568 **Hint 4** 569 570 The sub-problem can be solved in $\mathcal{O}(m/x)$ using inclusion exclusion. 571 572 **Hint 5** 573 574 How to count the sum of an specific element in the sub-problem of **Hint 3**? 575 576 **Solution** 577 578 **Observation:** $f(a)$ is the sum of maximums minus the sum of element right after a maximum minus $a_1$. 579 580 **Proof** 581 582 Suppose that $1 = i_1 \lt i_2 \lt \ldots \lt i_k = n$ is the indices that we visit in the algorithm, and $1 \leq j_1 \lt j_2 \lt \dots \lt j_t = k$ is the indices such that $a_{i_{j_p}}$ is maximum for all $1 \leq p \leq t$. 583 584 If we group the indices like below: 585 586 * $i_1, \ldots, i_{j_1}$ 587 * $i_{j_1+1}, \ldots, i_{j_2}$ 588 * ... 589 * $i_{j_{t-1}+1}, \ldots, i_k$ 590 591 each group will be increasing and $f(a)$ will be: 592 593 $(a_{i_{j_1}}-a_{i_1}) + \ldots + (a_n - a_{i_{j_{t-1}+1}}) = \sum\limits_{p=1}^{t}a_{i_{j_p}} - \sum\limits_{p=1}^{t-1}a_{i_{j_p+1}} - a_1$ 594 595 Let $g(n, m, x)$ be the answer of the sub-problem in **Hint 3**. We can calculate $g(n, m, x)$ is $\mathcal{O}(m/x)$ using inclusion exclusion and "Stars and bars". 596 597 $g(n, m, x) = \sum\limits_{t=0}^{\lfloor \frac{m}{x+1} \rfloor}{(-1)^t \binom{n}{t} \binom{m + n - 1 - t(x+1)}{n - 1}}$ 598 599 From now we fix $a_n = x$ and calculate the sum of $f(a)$ over all *snake* arrays with maximum equal to $x$. 600 601 **Counting the sum of maximums:** 602 603 The sum of $a_n$ over all arrays is $x \cdot g(n-1,m-x,x)$. The sum of $a_i$ for all $1 \leq i \leq n-1$ such that $a_i=x$ is $x \cdot (n-1) \cdot g(n-2, m-2x, x)$. 604 605 **Counting the sum of $a_1$:** 606 607 Let $s_i$ be the sum of $a_i$ over all *snake* arrays with $a_n=x$ for all $1 \leq i \lt n$. 608 609 It turns out that $s_i = s_j$ for all $1 \leq i, j \lt n$, because we can swap $a_i$ and $a_j$ in every array and there is no difference between $i$ and $j$. 610 611 The sum of $a_1,a_2,\ldots,a_{n-1}$ in every *snake* array is $m-x$, so $s_1+s_2+\ldots+s_{n-1} = (m-x)g(n-1,m-x,x) \rightarrow \space s_1 = \frac{m-x}{n-1}g(n-1,m-x,x).$ 612 613 **Counting the sum of elements right after a maximum:** 614 615 This part is similar to $a_1$ part. Suppose that $a_{i-1}=x$, the sum is $(m-2x)g(n-2,m-2x,x)$ for all $1 \lt i \lt n$, and $x \cdot g(n-2, m-2x,x)$ for $i=n$. 616 617 Since for each $x$ we just need $g(n-1, m-x, x)$ and $g(n-2, m-2x, x)$, the solution runs in $\sum\limits_{x=0}^{m}{\frac{m}{x+1}} = \mathcal{O}(m\log m)$. 618 619 **Code** 620 621 ``` 622 #include <bits/stdc++.h> 623 using namespace std; 624 625 using ll = long long; 626 627 const int MXN = 4e5+5; 628 const int MOD = 1e9+7; 629 630 ll power(ll a, ll b) { 631 ll res = 1; 632 while(b) { 633 if(b&1) (res *= a) %= MOD; 634 (a *= a) %= MOD; 635 b >>= 1; 636 } 637 return res; 638 } 639 640 ll F[MXN], I[MXN]; 641 642 void prep() { 643 F[0] = 1; 644 for(int i=1; i<MXN; i++) F[i] = F[i-1]*i%MOD; 645 I[0] = I[1] = 1; 646 for(int i=2; i<MXN; i++) I[i] = (MOD-MOD/i)*I[MOD%i]%MOD; 647 for(int i=2; i<MXN; i++) (I[i] *= I[i-1]) %= MOD; 648 } 649 ll C(int n, int r) { 650 return r<0 || r>n ? 0 : F[n]*I[r]%MOD*I[n-r]%MOD; 651 } 652 ll g(int n, int m, int l) { 653 if(n==0) return m==0; 654 ll ans = 0; 655 for(int t=0; t<=n && t*(l+1)<=m; t++) 656 (ans += C(n,t)*C(m+n-1-t*(l+1), n-1)%MOD*(t%2 ? MOD-1 : 1)%MOD) %= MOD; 657 return ans; 658 } 659 660 void solve() { 661 ll n, m, ans=0; 662 cin >> n >> m; 663 ll inv = power(n-1, MOD-2); 664 for(ll x=0; x<=m; x++) { 665 ll g1 = g(n-1, m-x, x), g2 = g(n-2, m-2*x, x); 666 (ans += x*(g1+g2*(n-1)%MOD)) %= MOD; 667 ll bad=0; 668 (bad += (m-x)*g1%MOD*inv) %= MOD; 669 (bad += x*g2) %= MOD; 670 (bad += (m-2*x)*g2) %= MOD; 671 (ans += MOD-bad) %= MOD; 672 } 673 cout << ans << '\n'; 674 } 675 676 int32_t main() { 677 cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0); 678 prep(); 679 int tc; 680 cin >> tc; 681 while(tc--) solve(); 682 return 0; 683 } 684 ``` 685 686 --- 687 688 [2127G1 - Inter Active (Easy Version)](/contest/2127/problem/G1) 689 **Idea:** [Ali_BBN](/profile/Ali_BBN "Candidate Master Ali_BBN") 690 **Preparation:** [Hamed_Ghaffari](/profile/Hamed_Ghaffari "Grandmaster Hamed_Ghaffari") and [Ali_BBN](/profile/Ali_BBN "Candidate Master Ali_BBN") 691 692 **Hints** 693 694 **Step 0** 695 696 Consider the following graph: $i\to p_i$. We will see the permutation as the graph. 697 698 When asking a permutation $q$, the result is sum of whether $q^{-1}(i) \lt q^{-1}(p_i)$. 699 700 **Hint 1** 701 702 Why is there a condition about $k$? If we do not have $k$, can the permutation $[2, 1, 4, 3]$ be guessed out? 703 704 **Hint 2.1** 705 706 When we ask a permutation, what does asking the reverse of the permutation help us with? 707 708 **Hint 2.2** 709 710 If we ask the reverse of the permutation except the index $k$, how many times is each edge of the permutation graph counted in total? 711 712 **Hint 3** 713 714 How to choose $k$? 715 716 **Solution** 717 718 Let $x$ be a number that we have not yet fixed, and let $k = x + 1$. 719 720 This partitions the array into three segments: 721 722 $ \begin{aligned} A &= [1, x] \\ B &= [x + 2, n - x] \\ C &= [n - x + 1, n] \end{aligned} $ 723 724 This tripartition helps in controlling the query behavior. 725 726 **Queries:** 727 728 Say we want to find out who maps to vertex $i$, i.e., find $j$ such that $p_j = i$. 729 730 Here's how: 731 732 1. Construct a permutation $q$ such that $q_k = i$ 733 2. Query this permutation $→$ receive answer $a$ 734 3. Reverse all elements of $q$ **except** the position $k$ 735 4. Query the reversed permutation $→$ receive answer $b$ 736 737 If we consider the permutation graph of p: 738 739 * Any edge not involving $i$ contributes **once** to the total count. Why? 740 * The edge where $p_j = i$: 741 + Will **not** be counted if $j = q_k$. This is not possible because it is guaranteed in the question that $p_i\neq i$. 742 + Will be counted **in only one** of the two queries if $j \in q[A \cup C]$. 743 + Will be counted **neither** if $j \in q[B]$. 744 * The edge where $p_i = j$ will **not** be counted at all, because $i$ is at index $k$. 745 746 Thus, $a + b$ is one of $[n - 2, n - 1]$ and by comparing $a + b$, we can find **which segment** $j$ (the predecessor of $i$) lies in. 747 748 **Repeating the Process:** 749 750 Once you know the predecessor is in a certain half, you repeat: 751 752 * Repartition the candidate set into two 753 * Choose one half to be placed in $A \cup C$, and the other in $B$ (If we had enough capacity). 754 * Place $i$ at index $k$ again. 755 * Do the same query + reverse trick 756 757 **Choosing k:** 758 759 If we set $x = \lfloor \frac{n+1}{4} \rfloor,\quad k = x + 1$, with each iteration (both in the first query and in the rest of the queries) the size of the candidate set shrinks by a factor of 2. 760 761 So to find the predecessor of one number $i$, we need $2 \log (n - 1)$ queries. 762 763 To find the entire permutation of $n$ elements $2 n\log (n - 1)$ queries. 764 765 We stay well within the $15 \cdot n$ limit. 766 767 **Code** 768 769 ``` 770 #include <bits/stdc++.h> 771 using namespace std; 772 773 #define SZ(x) int(x.size()) 774 775 const int MXN = 1003; 776 777 int n, k, p[MXN], q[MXN], cnt=0; 778 779 int ask() { 780 cout << "? "; 781 for(int i=1; i<=n; i++) cout << q[i] << ' '; 782 cout << endl; 783 int r; 784 cin >> r; 785 return r; 786 } 787 788 void ans() { 789 cout << "! "; 790 for(int i=1; i<=n; i++) cout << p[i] << ' '; 791 cout << endl; 792 } 793 794 bool mark[MXN]; 795 796 void build(int i, vector<int> opt, vector<int> optbad) { 797 fill(mark+1, mark+n+1, 0); 798 fill(q+1, q+n+1, 0); 799 q[k] = i; 800 mark[i] = 1; 801 for(int j=1; j<k && !opt.empty(); j++) { 802 mark[q[j] = opt.back()] = 1; 803 opt.pop_back(); 804 } 805 for(int j=n; !opt.empty(); j--) { 806 mark[q[j] = opt.back()] = 1; 807 opt.pop_back(); 808 } 809 for(int j=k+1; !optbad.empty(); j++) { 810 mark[q[j] = optbad.back()] = 1; 811 optbad.pop_back(); 812 } 813 for(int j=1; j<=n; j++) 814 if(!mark[j]) 815 opt.push_back(j); 816 for(int j=1; j<=n; j++) 817 if(!q[j]) { 818 q[j] = opt.back(); 819 opt.pop_back(); 820 } 821 } 822 823 void rev() { 824 vector<int> vec; 825 for(int i=1; i<=n; i++) 826 if(i!=k) 827 vec.push_back(q[i]); 828 for(int i=1; i<=n; i++) 829 if(i!=k) { 830 q[i] = vec.back(); 831 vec.pop_back(); 832 } 833 } 834 835 void Main() { 836 cin >> n; 837 k = (n+1)/4+1; 838 cout << k << endl; 839 for(int i=1; i<=n; i++) { 840 vector<int> opt; 841 for(int j=1; j<=n; j++) 842 if(j!=i) 843 opt.push_back(j); 844 while(opt.size()>1) { 845 int sz = SZ(opt) - min((SZ(opt)+1)/2, n-(2*k-1)); 846 build(i, 847 vector<int>(opt.begin(), opt.begin()+sz), 848 vector<int>(opt.begin()+sz, opt.end())); 849 int val = ask(); 850 rev(); 851 val += ask(); 852 if(val==n-1) opt = vector<int>(opt.begin(), opt.begin()+sz); 853 else opt = vector<int>(opt.begin()+sz, opt.end()); 854 } 855 p[opt.back()] = i; 856 } 857 ans(); 858 } 859 860 int32_t main() { 861 int tc; 862 cin >> tc; 863 while(tc--) Main(); 864 } 865 ``` 866 867 **Bonus** 868 869 This way can also be implemented with $2 \log (n - 1) + \sum\limits_{x=1}^{n - 1}{2 \log x}\sim 12 \cdot n$ queries. 870 871 --- 872 873 [2127G2 - Inter Active (Hard Version)](/contest/2127/problem/G2) 874 **Solution & Analysis:** [LMydd0225](/profile/LMydd0225 "International Grandmaster LMydd0225") and [Error_Yuan](/profile/Error_Yuan "Grandmaster Error_Yuan") 875 **Preparation:** [_R00T](/profile/_R00T "Master _R00T") and [Hamed_Ghaffari](/profile/Hamed_Ghaffari "Grandmaster Hamed_Ghaffari") 876 877 This version used an almost completely different approach from G1. Here's the step-by-step analysis: 878 879 **Analysis (Steps & Hints)** 880 881 **Step 0** 882 883 Consider the following graph: $i\to p_i$. We will see the permutation as the graph. 884 885 When asking a permutation $q$, the result is sum of whether $q^{-1}(i) \lt q^{-1}(p_i)$. 886 887 **Hint 1.1** 888 889 Why is there a condition about $k$? If we do not have $k$, can the permutation $[2, 1, 4, 3]$ be guessed out? 890 891 **Step 1.2** 892 893 If there is a cycle of length $2$ in the permutation graph (that is, $p_i=j$ and $p_j=i$), exactly one of the two corresponding pairs to $(p_i, p_j)$ and $(p_j,p_i)$ will be counted in any query when we do not have $k$. So we have to use $k$ for cycles of length $2$. This inspires us to do casework on cycle length $=2$ or $\ge 3$. 894 895 **Step 2.1** 896 897 If the whole permutation graph is composed only of cycles of length $2$, can you guess out the permutation in about $\frac{1}{2}n\log n$ queries? 898 899 **Hint 2.2** 900 901 You need to use the property that the permutation graph is composed **only** of cycles of length $2$. 902 903 **Step 2.3** 904 905 Let's say you want to determine what is $p_i$. Query any permutation $q$ with $q_k=i$. If $p_i$ is among $q_1, q_2, \ldots, q_{k-1}$, the response to the query will be $\frac{n}{2}$, otherwise, $p_i$ is among $q_{k+1}, q_{k+2}, \ldots, q_n$, and the response will be $\frac{n}{2}-1$. You can verify this by yourself. Note that permutation graph is composed **only** of cycles of length $2$. 906 907 Thus, we can put $k$ around $\frac{n}{2}$ and apply binary search for a single $i\to p_i$ with $\log n$ queries. Note that when we get $p_i=j$, we also get $p_j=i$. So we only need $\frac{1}{2}n\log n$ queries in total. 908 909 **Step 3.1** 910 911 How can we distinguish $i\to p_i$ is in which kind of cycle, length of $2$ or length $\ge 3$? Try to solve this for a single $i$ in $2\log n$ queries. Note that you do **not** need to determine $p_i$, you just need to tell whether $i\to p_i$ is in a cycle of length $2$. 912 913 **Hint 3.2** 914 915 If $i\to p_i$ is in a cycle of length $\ge 3$, we have $l$ and $j$ such that $l\to i\to j$ and $l\ne j$. Otherwise, $l=j$. 916 917 **Hint 3.3** 918 919 Consider bitmasks. 920 921 **Hint 3.4** 922 923 Consider cyclic shifts. Do not use $k$. 924 925 **Step 3.5** 926 927 Consider the following two queries ($m \lt k$): 928 929 1. $[q_1, q_2, q_3, \ldots, q_m, \ldots, q_k, \ldots]$; 930 2. $[q_m, q_1, q_2, \ldots, q_{m-1}, \ldots, q_k, \ldots]$. 931 932 Only the contribution of $x\to q_m\to y$ may change: Let's say $A=\{q_1,q_2,\ldots,q_{m-1}\}$, $B=\{q_{m+1}, q_{m+2}, \ldots q_n\}$. If $x$ and $y$ are both inside $A$ or both inside $B$, responses to query **1.** and **2.** will be the same. Otherwise, answer changes by exactly $1$. If the responses are different, we can next tell whether $x_i$ is in $A$ by looking at whether the difference is $1$ or $-1$. However, if the responses are the same, we can't tell whether they are both in $A$ or both in $B$. 933 934 An idea to tell whether $x=y$ is to group numbers by their bitmasks. We can use $\log n$ times such two queries to ask for each bit (let numbers with 0 on this bit in $A$, those with 1 in $B$). In the end, we will get $x\oplus y$. Then we surely get whether $x=y$. 935 936 **Hint 3.6** 937 938 **Step 3.5** needs $2\log n$ queries for a single element. Can you use $n\log n$ queries to solve the problem in **Step 3.5** for all elements? Note that we are doing cyclic shifts. 939 940 **Step 3.7** 941 942 Note that we are doing cyclic shifts. In fact, for each $i$, we just need it to appear at $q_1$ and $q_m$ respectively, without changing the set $A$. Then, for a certain set $A$, we can do cyclic shifts $|A|$ times to get all information we need. Similar for $B$. Thus, we finished the task in **Hint 3.6** in $n\log n$ queries. 943 944 Since we will fix $k$ around $\frac{n}{2}$ for cycles with length $2$, we must ensure that $|A|$ and $|B|$ are around $\frac{n}{2}$. But this is not always true. Fortunately, we can resolve this issue by assigning each integer an unqiue number $c_i$, where $0\le c_i\le 2^{\lceil\log n\rceil}-1$, so that there will be exactly $\frac{n}{2}$ (or floor and ceil) 0s and 1s on each bit. We will group the indices by $c_i$ instead. Now we can put $k=\lceil\frac{n}{2}\rceil+1$. 945 946 **Final Steps** 947 948 Here are the final steps of this problem. First, we run the algorithm in **Step 3**. Now we get all $x_i \oplus p_i$, where $x_i\to i\to p_i$ holds. 949 950 First, we will determine all $p_i$-s on cycles of length $\ge 3$. Note that we have determined all $x_i\oplus p_i$, so we only need to determine one edge for each cycle. 951 952 Note that in **Step 3**, when responses to two queries are different, we can know whether $p_i$ is in $A$ or $x_i$ is in $A$. Note that we can change $m$ arbitrarily, so we can apply binary search on $m$ to get one of $p_i$ and $x_i$. That finishes the task in $\log n$ queries for each cycle. On average for each element, it is at most $\frac{1}{3}\log n$ queries. 953 954 After that, we know all $p_i$-s on cycles of length $\ge 3$, and we can calculate the response to any query $[q_1, q_2,\ldots,q_n]$ easily if we don't have $k$. Similar to **Step 2**, we can determine all $p_i$-s on cycles of length $2$ in $\frac{1}{2}n\log n$ queries. On average for each element, it is $\frac{1}{2}\log n$ queries. Thus, in the worst case where the whole permutation graph consists only of cycles of length $2$, the total number of queries is $1.5\lceil\log n\rceil\cdot n$. When $n=100$, it is $10.5\cdot n$, a little larger than the limit. We can apply a trivial optimization when doing **Step 2**: do binary serach on possible indices instead of all indices. This will use a total of at most $n\log n+\sum\limits_{i=0}^{\lfloor(n-1)/2\rfloor} \log(n-1-2\cdot i)$ queries. When $n=100$, it is $986$, which fits the constraints well. 955 956 **Code** 957 958 ``` 959 #include <bits/stdc++.h> 960 #define all(s) s.begin(), s.end() 961 using namespace std; 962 using ll = long long; 963 using ull = unsigned long long; 964 965 int T; 966 967 void solve() { 968 int n; cin >> n; 969 const int k = (n + 1) / 2; 970 const int M = __lg(n - 1) + 1; 971 cout << k + 1 << endl; 972 973 vector<int> p(n + 1); 974 975 auto query = [&](vector<int> &q) -> int { 976 cout << "? "; 977 for (int i = 1; i <= n; i++) cout << q[i] << " \n"[i == n]; 978 cout.flush(); 979 int res; cin >> res; 980 return res; 981 }; 982 983 vector<int> c(n + 1), d(1 << M); 984 auto binary_coding = [&]() { 985 for (int i = 0, cnt = 1; cnt <= n; i++, cnt++) { 986 c[cnt++] = i; 987 if (cnt <= n) c[cnt] = (1 << M) - 1 - i; 988 } 989 for (int i = 1; i <= n; i++) d[c[i]] = i; 990 return; 991 }; 992 993 vector<int> xors(n + 1); 994 vector<vector<int>> res1(M, vector<int>(n + 1)), res2(M, vector<int>(n + 1)); 995 vector<int> good, bad; 996 auto getXORs = [&]() { 997 for (int bit = 0; bit < M; bit++) { 998 vector<int> A, B; 999 for (int i = 1; i <= n; i++) { 1000 if (c[i] & (1 << bit)) B.emplace_back(i); 1001 else A.emplace_back(i); 1002 } 1003 int m = A.size(), l = B.size(); 1004 for (int i = 0; i < m; i++) { 1005 vector<int> q(n + 1); 1006 for (int j = 0; j < m; j++) q[j + 1] = A[(j + i) % m]; 1007 for (int j = 0; j < l; j++) q[j + m + 1] = B[j]; 1008 int res = query(q); 1009 res1[bit][q[1]] = res; 1010 res2[bit][q[m]] = res; 1011 } 1012 for (int i = 0; i < l; i++) { 1013 vector<int> q(n + 1); 1014 for (int j = 0; j < l; j++) q[j + 1] = B[(j + i) % l]; 1015 for (int j = 0; j < m; j++) q[j + l + 1] = A[j]; 1016 int res = query(q); 1017 res1[bit][q[1]] = res; 1018 res2[bit][q[l]] = res; 1019 } 1020 for (int i = 1; i <= n; i++) { 1021 if (res1[bit][i] != res2[bit][i]) xors[i] ^= (1 << bit); 1022 } 1023 } 1024 for (int i = 1; i <= n; i++) { 1025 if (xors[i] != 0) good.emplace_back(i); 1026 else bad.emplace_back(i); 1027 } 1028 return; 1029 }; 1030 auto solve3 = [&]() { 1031 for (auto pos : good) { 1032 if (p[pos]) continue; 1033 int x = xors[pos], bit = __lg(x & (-x)); 1034 vector<int> A, B; 1035 for (int i = 1; i <= n; i++) { 1036 if (c[i] & (1 << bit)) B.emplace_back(i); 1037 else A.emplace_back(i); 1038 } 1039 if (c[pos] & (1 << bit)) swap(A, B); 1040 int m = A.size(), l = B.size(); 1041 int id = 0; 1042 for (int i = 0; i < m; i++) if (A[i] == pos) id = i; 1043 int L = 2, R = m; 1044 vector<int> base(n + 1); 1045 for (int j = 0; j < m; j++) base[j + 1] = A[(j + id) % m]; 1046 for (int j = 0; j < l; j++) base[j + m + 1] = B[j]; 1047 while (L < R) { 1048 int mid = (L + R) >> 1; 1049 vector<int> q(n + 1); 1050 for (int i = 1; i < mid; i++) q[i] = base[i + 1]; 1051 q[mid] = base[1]; 1052 for (int i = mid + 1; i <= n; i++) q[i] = base[i]; 1053 int res = query(q); 1054 if (res != res1[bit][pos]) R = mid; 1055 else L = mid + 1; 1056 } 1057 int s = 0; 1058 if (res2[bit][pos] > res1[bit][pos]) p[base[L]] = pos, s = base[L]; 1059 else p[pos] = base[L], s = pos; 1060 while (!p[p[s]]) { 1061 int X = xors[p[s]]; 1062 p[p[s]] = d[X ^ c[s]]; 1063 s = p[s]; 1064 } 1065 } 1066 }; 1067 auto solve2 = [&]() { 1068 for (auto pos : bad) { 1069 if (p[pos]) continue; 1070 auto calc = [&](vector<int> &q) { 1071 int val = count(all(p), 0) / 2; 1072 vector<int> inv(n + 1); 1073 for (int i = 1; i <= n; i++) inv[q[i]] = i; 1074 for (int i = 1; i <= n; i++) val += (inv[i] < inv[p[i]]); 1075 return val; 1076 }; 1077 vector<int> cand, ok; 1078 for (int i = 1; i <= n; i++) { 1079 if (i != pos && !p[i]) cand.emplace_back(i); 1080 if (p[i]) ok.emplace_back(i); 1081 } 1082 while ((int)cand.size() != 1) { 1083 vector<int> q = { 0 }, L, R; 1084 int len = ((int)cand.size() + 1) / 2; 1085 for (int i = 0; i < len; i++) q.emplace_back(cand[i]), L.emplace_back(cand[i]); 1086 for (int i = len; i < k; i++) q.emplace_back(ok[i - len]); 1087 q.emplace_back(pos); 1088 for (int i = len; i < (int)cand.size(); i++) q.emplace_back(cand[i]), R.emplace_back(cand[i]); 1089 for (int i = k - len; i < (int)ok.size(); i++) q.emplace_back(ok[i]); 1090 int res = query(q); 1091 res -= calc(q); 1092 if (res != 0) swap(L, R); 1093 cand = L; 1094 for (auto x : R) ok.emplace_back(x); 1095 } 1096 p[pos] = cand[0]; 1097 p[cand[0]] = pos; 1098 } 1099 }; 1100 1101 binary_coding(); 1102 getXORs(); 1103 solve3(); 1104 solve2(); 1105 1106 cout << "! "; 1107 for (int i = 1; i <= n; i++) cout << p[i] << " \n"[i == n]; 1108 cout.flush(); 1109 return; 1110 } 1111 1112 int main() { 1113 ios::sync_with_stdio(false), cin.tie(0), cout.tie(0); 1114 cin >> T; 1115 while (T--) { 1116 solve(); 1117 } 1118 } 1119 ``` 1120 1121 --- 1122 1123 [2127H - 23 Rises Again](/contest/2127/problem/H) 1124 **Idea:** [sweetweasel](/profile/sweetweasel "International Master sweetweasel") and [eren__](/profile/eren__ "Grandmaster eren__") 1125 **Preparation:** [Hamed_Ghaffari](/profile/Hamed_Ghaffari "Grandmaster Hamed_Ghaffari") and [_R00T](/profile/_R00T "Master _R00T") 1126 1127 **Hints** 1128 1129 **Hint 0** 1130 1131 Each connected component of a *candy graph* is either a simple path or a simple cycle. 1132 1133 **Hint 1** 1134 1135 Try to break the problem down into smaller parts. 1136 1137 **Hint 2** 1138 1139 Take a DFS tree, at most $5$ back-edges pass through each vertex. 1140 1141 **Hint 3** 1142 1143 Choose a vertex $v$, brute force on the back-edges that pass through $v$ and appears in the subgraph with maximum number of edges, then remove $v$ and all back-edges that pass through $v$. 1144 1145 **Hint 4** 1146 1147 Now we have to solve the following sub-problem for each connected component: 1148 1149 You are given a simple connected graph that each vertex belongs to at most $5$ simple cycles, and an array $d_1,d_2,\ldots,d_n (0 \leq d_i \leq 2)$. What is the subgraph with maximum number of edges that degree of vertex $i$ is at most $d_i$. 1150 1151 **Hint 5** 1152 1153 The sub-problem can be solved in $\mathcal{O}(2^nnm)$ with dp bitmask. 1154 1155 **Hint 6** 1156 1157 Let $N$ be the size of the component with the maximum size after removing $v$ and back-edges that pass through $v$. 1158 1159 We can solve the problem in $\mathcal{O}(2^5 2^NNm)$. 1160 1161 **Hint 7** 1162 1163 Choose $v$ as the centroid of the DFS tree. 1164 1165 Since $N \leq n/2$ the complexity will be $\mathcal{O}(2^5 2^{n/2}nm)$. 1166 1167 **Hint 8** 1168 1169 Is the complexity really $\mathcal{O}(2^5 2^{n/2}nm)$? 1170 1171 **Solution** 1172 1173 Each connected component of a *candy graph* is either a simple path or a simple cycle. 1174 1175 Take a DFS tree, at most $5$ back-edges pass through each vertex, then choose a vertex $v$, brute force on the back-edges that pass through $v$ and appears in the subgraph with maximum number of edges, then remove $v$ and all back-edges that pass through $v$. 1176 1177 Let $d_i$ be the maximum degree that vertex $i$ can have. Initially $d_i=2$ for each vertex. Each back-edge $(x,y)$ that you select, reduces $d_x$ and $d_y$ by $1$. If after selecting back-edges that pass through $v$, there exists a vertex with negative $d$, skip this case. Otherwise you have to solve the sub-problem in **Hint 4** for every connected component. 1178 1179 We can solve the sub-problem with the following dp bitmask: 1180 1181 Let $ans_{mask}$ be the answer for $mask$, and let $dp_{mask,u,v,l1}$ be the answer for $mask$ where the last path we selected is from $u$ to $v$ and $l1 \in \text{{0, 1}}$ means that the length of the path is $1$ or not. 1182 1183 Transitions: 1184 1185 * Start a new path: $ans_{mask}+1 \to dp_{mask,u,v,1}$, if $(u,v)$ is an edge outside $mask$ with $d_u, d_v \geq 1$. 1186 * Add a vertex to the last path: $dp_{mask,u,v,l1}+1 \to dp_{mask+2^w,u,w,0}$, if $w$ is a vertex outside $mask$ and adjacent to $v$, and $d_v = 2, d_w \geq 1$. 1187 * Make the last path cycle: $dp_{mask,u,v,0}+1 \to ans_{mask}$, if there exists a $(u, v)$ edge, and $d_u = d_v = 2$. 1188 * Skip a vertex: $ans_{mask} \to ans_{mask+2^w}$, if $w$ is a vertex outside $mask$. 1189 1190 Also, you have to solve the sub-problem for each component twice, because you can choose a DFS tree edge connected to the vertex that you've deleted and it reduces $d$ of one vertex in that component. 1191 1192 It can be seen that if $N$ be the size of the component with the maximum size, the complexity will be $\mathcal{O}(2^NNm)$ for a fixed set of back-edges, and $\mathcal{O}(2^52^NNm)$ in total. 1193 1194 If we select $v$ as the centroid of the DFS tree $N$ will be less than or equal to $n/2$ so the complexity will be $\mathcal{O}(2^5 2^{n/2}nm)$. 1195 1196 It can be proven that $m \leq 3n$ in graphs that each vertex belongs to at most $5$ simple cycles. So the complexity will be $\mathcal{O}(2^52^{n/2}n^2)$. 1197 1198 **Proof** 1199 1200 We prove this by induction. suppose that $m \leq 3n$ for all graphs with $n \lt N$. 1201 1202 Take a DFS tree, we can prove that the degree of a leaf is at most $3$, because otherwise at least $3$ back-edges would exit that leaf and there would be at least $6$ cycles containing that leaf. 1203 1204 So there always exists a vertex with degree $\leq 3$, we can remove it, $m \leq 3(N-1) + 3 = 3N$. 1205 1206 **Code** 1207 1208 ``` 1209 #include <bits/stdc++.h> 1210 using namespace std; 1211 1212 #define SZ(x) int(x.size()) 1213 #define maxs(a, b) (a = max(a, b)) 1214 1215 const int MXN = 30, MXM = MXN*(MXN-1)/2; 1216 1217 int n, m, U[MXM], V[MXM]; 1218 vector<int> g[MXN]; 1219 bool tedge[MXM], have_edge[MXN][MXN]; 1220 int sz[MXN]; 1221 1222 void dfs1(int v) { 1223 sz[v] = 1; 1224 for(int i : g[v]) { 1225 int u = v^U[i]^V[i]; 1226 if(!sz[u]) { 1227 tedge[i] = 1; 1228 dfs1(u); 1229 sz[v] += sz[u]; 1230 } 1231 } 1232 } 1233 1234 int centroid(int v, int p=-1) { 1235 for(int i : g[v]) if(tedge[i]) { 1236 int u = v^U[i]^V[i]; 1237 if(u!=p && sz[u]+sz[u]>n) 1238 return centroid(u, v); 1239 } 1240 return v; 1241 } 1242 1243 int ID[MXN], id_counter; 1244 vector<int> vertices[MXN]; 1245 int dp[1<<(MXN>>1)][MXN>>1][MXN>>1][2], ans_tmp[1<<(MXN>>1)], ans[2]; 1246 1247 void dfs_id(int v, int p=-1) { 1248 vertices[ID[v] = id_counter].push_back(v); 1249 for(int i : g[v]) if(tedge[i]) { 1250 int u = v^U[i]^V[i]; 1251 if(u!=p) dfs_id(u, v); 1252 } 1253 } 1254 1255 int deg[MXN], pos[MXN]; 1256 1257 int solve_(int id) { 1258 int n = SZ(vertices[id]); 1259 for(int msk=0; msk<(1<<n); msk++) { 1260 ans_tmp[msk] = -1e9; 1261 for(int i=0; i<n; i++) 1262 for(int j=0; j<n; j++) 1263 for(int x : {0,1}) 1264 dp[msk][i][j][x] = -1e9; 1265 } 1266 ans_tmp[0] = 0; 1267 for(int msk=0; msk<(1<<n); msk++) { 1268 for(int i=0; i<n; i++) if(msk>>i&1) 1269 for(int j=0; j<n; j++) if(i!=j && (msk>>j&1)) { 1270 if(deg[vertices[id][j]]==2) { 1271 for(int eid : g[vertices[id][j]]) if(ID[U[eid]]==ID[V[eid]]) { 1272 int u = vertices[id][j]^U[eid]^V[eid]; 1273 if(!(msk>>pos[u]&1) && deg[u]>=1) 1274 maxs(dp[msk^(1<<pos[u])][i][pos[u]][0], 1275 max(dp[msk][i][j][0], dp[msk][i][j][1])+1); 1276 } 1277 if(deg[vertices[id][i]]==2 && have_edge[vertices[id][i]][vertices[id][j]]) 1278 maxs(ans_tmp[msk], dp[msk][i][j][0]+1); 1279 } 1280 maxs(ans_tmp[msk], max(dp[msk][i][j][0], dp[msk][i][j][1])); 1281 } 1282 for(int i=0; i<n; i++) if(!(msk>>i&1)) { 1283 maxs(ans_tmp[msk^(1<<i)], ans_tmp[msk]); 1284 if(deg[vertices[id][i]]>=1) 1285 for(int eid : g[vertices[id][i]]) if(ID[U[eid]]==ID[V[eid]]) { 1286 int u = vertices[id][i]^U[eid]^V[eid]; 1287 if(deg[u]>=1 && !(msk>>pos[u]&1)) 1288 maxs(dp[msk^(1<<i)^(1<<pos[u])][i][pos[u]][1], ans_tmp[msk]+1); 1289 } 1290 } 1291 } 1292 return ans_tmp[(1<<n)-1]; 1293 } 1294 1295 void solve(int id, int cent_neighbour) { 1296 ans[0] = solve_(id); 1297 if(deg[cent_neighbour]!=0) { 1298 deg[cent_neighbour]--; 1299 ans[1] = solve_(id); 1300 } 1301 else ans[1] = -1e9; 1302 } 1303 1304 void Main() { 1305 cin >> n >> m; 1306 for(int i=0; i<n; i++) { 1307 g[i].clear(); 1308 vertices[i].clear(); 1309 sz[i] = 0; 1310 for(int j=0; j<n; j++) 1311 have_edge[i][j] = 0; 1312 } 1313 for(int i=0; i<m; i++) { 1314 tedge[i] = 0; 1315 } 1316 for(int i=0,u,v; i<m; i++) { 1317 cin >> u >> v; 1318 u--, v--; 1319 have_edge[u][v] = have_edge[v][u] = 1; 1320 U[i] = u; 1321 V[i] = v; 1322 g[u].push_back(i); 1323 g[v].push_back(i); 1324 } 1325 dfs1(0); 1326 int cent = centroid(0); 1327 1328 ID[cent] = 0; 1329 id_counter = 0; 1330 for(int i : g[cent]) if(tedge[i]) { 1331 int u = cent^U[i]^V[i]; 1332 id_counter++; 1333 dfs_id(u, cent); 1334 for(int j=0; j<SZ(vertices[id_counter]); j++) 1335 pos[vertices[id_counter][j]] = j; 1336 } 1337 1338 vector<int> be; 1339 for(int i=0; i<m; i++) 1340 if(!tedge[i] && (ID[U[i]]^ID[V[i]])) be.push_back(i); 1341 1342 int besz = SZ(be), answer = -1e9; 1343 1344 for(int msk=0; msk<(1<<besz); msk++) { 1345 fill(deg, deg+n, 2); 1346 for(int i=0; i<besz; i++) if(msk>>i&1) 1347 deg[U[be[i]]]--, deg[V[be[i]]]--; 1348 bool deg3 = 0; 1349 for(int i=0; i<n; i++) 1350 if(deg[i]<0) { 1351 deg3 = 1; 1352 break; 1353 } 1354 if(deg3) continue; 1355 int cur[3]; 1356 cur[0] = cur[1] = cur[2] = -1e9; 1357 cur[deg[cent]] = __builtin_popcount(msk); 1358 for(int i : g[cent]) if(tedge[i]) { 1359 int u = cent^U[i]^V[i]; 1360 solve(ID[u], u); 1361 cur[0] = max(cur[0]+ans[0], cur[1]+ans[1]+1); 1362 cur[1] = max(cur[1]+ans[0], cur[2]+ans[1]+1); 1363 cur[2] = cur[2]+ans[0]; 1364 } 1365 answer = max({answer, cur[0], cur[1], cur[2]}); 1366 } 1367 cout << answer << '\n'; 1368 } 1369 1370 int32_t main() { 1371 cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0); 1372 int tc; 1373 cin >> tc; 1374 while(tc--) Main(); 1375 return 0; 1376 } 1377 ``` 1378 1379 **Apology** 1380 1381 It turns out there are some very simple randomized solutions we hadn’t anticipated, as well as approaches using matching and even unexpected ones like backtracking. Unfortunately, these are quite hard to detect and reject without knowing beforehand. 1382 1383 We sincerely apologize for this mistake. We hope you enjoyed the rest of the problems.