2133.md (25847B)
1 Source: https://codeforces.com/blog/entry/145785 2 3 Thank you for participating in my round! I hope you all enjoyed it. 4 5 **Rate the contest!** 6 7 **Quality** 8 9 * Excellent contest 10 * Good contest 11 * Average contest 12 * Bad contest 13 * Horrible contest 14 15 **Difficulty** 16 17 * Trivial contest 18 * Easy contest 19 * Average contest 20 * Hard contest 21 * Impossible contest 22 23 [2133A - Redstone?](/contest/2133/problem/A "Codeforces Round 1044 (Div. 2)") 24 25 **Hint 1** 26 27 What does the speed of each gear depend on? 28 29 **Solution** 30 31 Suppose we have some arrangement of gears where gear $i$ from the left has $b_i$ teeth. Then the speed of gear $n$ is $1 \cdot \frac{b_1}{b_2} \cdot \frac{b_2}{b_3} \cdot \ldots \cdot \frac{b_{n-1}}{b_n}$. Notice that most of the fractions cancel, leaving only $\frac{b_1}{b_n}$. So in fact, the speed of gear $n$ depends only on $b_n$ and $b_1$. 32 33 Therefore if we want the rightmost gear to have the same speed as the leftmost gear, we need to arrange them in such a way that $\frac{b_1}{b_n} = 1$, so $b_1 = b_n$. This is possible if and only if there are two gears with the same number of teeth. So we just need to find if there are any duplicated values in the given array. This can be checked in $\mathcal{O}(n\,\text{log}\,n)$ using a set, although the constraints are low enough to allow checking all pairs in $\mathcal{O}(n^2)$ as well. 34 35 **Code (C++)** 36 37 ``` 38 #include <bits/stdc++.h> 39 using namespace std; 40 41 typedef long long ll; 42 #define all(x) x.begin(), x.end() 43 #define vecin(name, len) vector<int> name(len); for (auto &_ : name) cin >> _; 44 #define vecout(v) for (auto _ : v) cout << _ << " "; cout << endl; 45 46 void solve() { 47 int n; cin >> n; 48 vecin(gears, n); 49 set<int> seen; 50 for (auto gear : gears) { 51 if (seen.count(gear)) { 52 cout << "YES" << endl; return; 53 } 54 seen.insert(gear); 55 } 56 cout << "NO" << endl; 57 } 58 59 int main() { 60 ios_base::sync_with_stdio(false); 61 cin.tie(NULL); 62 int tt = 1; 63 64 cin >> tt; 65 66 while (tt--) solve(); 67 return 0; 68 } 69 ``` 70 71 **Code (Python)** 72 73 ``` 74 tt = int(input()) 75 for t in range(tt): 76 n = int(input()) 77 gears = list(map(int, input().split())) 78 valid = False 79 for i in range(n): 80 for j in range(i + 1, n): 81 if gears[i] == gears[j]: 82 valid = True 83 if valid: 84 print("YES") 85 else: 86 print("NO") 87 ``` 88 89 **Rate the problem!** 90 91 **Quality** 92 93 * Excellent problem 94 * Good problem 95 * Average problem 96 * Bad problem 97 * Horrible problem 98 99 **Difficulty** 100 101 * Trivial problem 102 * Easy problem 103 * Average problem 104 * Hard problem 105 * Impossible problem 106 107 [2133B - Villagers](/contest/2133/problem/B "Codeforces Round 1044 (Div. 2)") 108 109 **Hint 1** 110 111 Who should you pair with the grumpiest villager? 112 113 **Solution** 114 115 Notice that each operation sets at least one of the involved villagers' grumpiness to $0$. So after one operation has been done involving each villager, each villager either has grumpiness $0$ or is friends with another villager with grumpiness $0$. Then all the villagers can be made friends with each other for free, by joining the villagers with grumpiness $0$. 116 117 So an upper bound on the answer is the cost to do at least one operation involving each villager. This is also a lower bound, since if there is a villager who was not involved in any operation, they are not friends with any other villager. Therefore we just need to find this cost. 118 119 Let's sort the array $g$ so that the grumpiest villager is villager $n$. An optimal set of operations is then to pair villagers $n$ and $n-1$, $n-2$ and $n-3$, $n-4$ and $n-5$ and so on. If villager $1$ is left over, pair it with villager $2$ as well. This costs $g_n + g_{n - 2} + g_{n - 4} + \ldots$ in total. 120 121 We can prove that this is a lower bound on the answer as follows. Consider instead the operation of paying $\text{max}(g_i, g_j)$ emeralds but setting both $g_i$ and $g_j$ to $0$; any optimal sequence with this operation has a cost of at most that of using the original operation. Now consider which villager is paired with villager $n$ for the first operation performed on them. If it is not villager $n - 1$, then some villager $x$ was paired with villager $n - 1$ on their first operation, and some other villager $y$ is paired with villager $n$ on their first operation. Replace those operations with pairing villagers $n$ and $n - 1$, and villagers $x$ and $y$. The cost does not increase because $\text{max}(x, y) \le g_{n-1}$. So there is also an optimal sequence where villagers $n$ and $n-1$ are paired with each other first for a cost of $g_n$. This leaves $n-2$ villagers with nonzero $g_i$, and clearly it is no better than an optimal sequence to pair any of them with villagers $n$ or $n - 1$ when they could be paired with other villagers among each other, so the argument can be repeated inductively on those $n-2$ villagers. 122 123 **Code (C++)** 124 125 ``` 126 #include <bits/stdc++.h> 127 using namespace std; 128 129 typedef long long ll; 130 #define all(x) x.begin(), x.end() 131 #define vecin(name, len) vector<int> name(len); for (auto &_ : name) cin >> _; 132 #define vecout(v) for (auto _ : v) cout << _ << " "; cout << endl; 133 134 void solve() { 135 int n; cin >> n; 136 vecin(g, n); 137 ll ans = 0; 138 sort(all(g)); 139 for (int i = n - 1; i >= 0; i -= 2) 140 ans += g[i]; 141 cout << ans << endl; 142 } 143 144 int main() { 145 ios_base::sync_with_stdio(false); 146 cin.tie(NULL); 147 int tt = 1; 148 149 cin >> tt; 150 151 while (tt--) solve(); 152 return 0; 153 } 154 ``` 155 156 **Code (Python)** 157 158 ``` 159 tt = int(input()) 160 for t in range(tt): 161 n = int(input()) 162 grumpiness = list(map(int, input().split())) 163 grumpiness.sort() 164 tot = 0 165 for i in range(n - 1, -1, -2): 166 tot += grumpiness[i] 167 print(tot) 168 ``` 169 170 **Rate the problem!** 171 172 **Quality** 173 174 * Excellent problem 175 * Good problem 176 * Average problem 177 * Bad problem 178 * Horrible problem 179 180 **Difficulty** 181 182 * Trivial problem 183 * Easy problem 184 * Average problem 185 * Hard problem 186 * Impossible problem 187 188 [2133C - The Nether](/contest/2133/problem/C "Codeforces Round 1044 (Div. 2)") 189 190 **Hint 1** 191 192 How can you find where the path should start? 193 194 **Hint 2** 195 196 How else can you use the information you gained from that? 197 198 **Solution** 199 200 Let's first find a suitable starting location for the longest path. We can find the length of the longest path starting from each location in $n$ queries, by querying `? i n 1 2 ... n` for each $1 \le i \le n$, and can pick any location whose query returned the maximum value. 201 202 How can we also use this information to help find the rest of the path? Suppose we have some location $x$ in any longest path, whose query returned $k$. Then we know the next location is one whose query returned $k-1$. This is because if it returned a value $\ge k$, then there is a path of length at least $k + 1$ from $x$, but the query returned $k$; and if it returned a value $\le k - 2$, then if it is the next location in the path, the path starting from $x$ has length at most $k - 1$, but we know there is a path of length $k$ starting from it so it is not a longest path. 203 204 So if our path ends at a location $x$ whose query returned $k$, we can find the next location by querying `? x 2 x y` for all locations $y$ whose query returned $k-1$, and choosing any location which returns $2$. We repeat this until we have the whole path. Since the second step queries each location at most once, other than the starting location, we use no more than $2 \cdot n - 1$ queries in total. 205 206 **Code (Python)** 207 208 ``` 209 import sys 210 for test in range(int(input())): 211 layers = {} 212 n = int(input()) 213 big = -1 214 path = [] 215 for i in range(n): 216 print(f"? {i + 1} {n} {' '.join(list(map(str, list(range(1, n + 1)))))}") 217 sys.stdout.flush() 218 ans = int(input()) 219 if ans in layers: 220 layers[ans].append(i + 1) 221 else: 222 layers[ans] = [i + 1] 223 if ans > big: 224 big = ans 225 path = [i + 1] 226 for depth in range(big - 1, 0, -1): 227 for candidate in layers[depth]: 228 print(f"? {path[-1]} 2 {path[-1]} {candidate}") 229 sys.stdout.flush() 230 ans = int(input()) 231 if ans == 2: 232 path.append(candidate) 233 break 234 print(f"! {len(path)} {' '.join(list(map(str, path)))}") 235 sys.stdout.flush() 236 ``` 237 238 **Rate the problem!** 239 240 **Quality** 241 242 * Excellent problem 243 * Good problem 244 * Average problem 245 * Bad problem 246 * Horrible problem 247 248 **Difficulty** 249 250 * Trivial problem 251 * Easy problem 252 * Average problem 253 * Hard problem 254 * Impossible problem 255 256 **Bonus** 257 258 Solve in $\frac{5}{3} \cdot n$ queries. 259 260 [2133D - Chicken Jockey](/contest/2133/problem/D "Codeforces Round 1044 (Div. 2)") 261 262 **Hint 1** 263 264 How many times can a mob take fall damage? 265 266 **Hint 2** 267 268 If a mob takes more than $1$ fall damage, what about the mob below it? 269 270 **Hint 3** 271 272 Use DP. 273 274 **Solution** 275 276 Let's make a few observations. First of all, if a mob takes fall damage, it ends up at the bottom of a stack. This means a mob never takes fall damage more than once, because after taking fall damage there are no more mobs below it that it can fall off of. 277 278 Secondly, if a mob takes more than $1$ fall damage, the mob below must have been killed without taking fall damage, otherwise it would have been at the bottom of the stack and hence the mob above would only have $1$ mob below it and take $1$ fall damage. Therefore the mob below must take $h_i$ attacks to kill, regardless of whether it is in the original stack or if other mobs below it had fallen off and taken damage. This means that if a mob should take more than $1$ fall damage, it is best to do so in the original stack, as that will maximise the fall damage without incurring any additional attacks. 279 280 This seems like a very local choice: for each mob $i$ we either kill it directly, let it take $i - 1$ fall damage by killing the mob below it directly, or let it take $1$ fall damage by falling down when the mob below it dies. So we could let $dp[i]$ be the minimum attacks needed to kill all the mobs up to mob $i$. Clearly $dp[0] = 0$ and $dp[1] = h_1$. For $i \ge 2$, we either let it take $1$ fall damage which costs $dp[i - 1] + h_i - 1$ attacks, or let it take maximum fall damage which costs $dp[i - 2] + h_{i - 1} + \text{max}(0, h_i - (i - 1))$ attacks; we set $dp[i]$ to the smaller of those two values. The answer is then $dp[n]$. 281 282 **Code (Python)** 283 284 ``` 285 t = int(input()) 286 for test in range(t): 287 n = int(input()) 288 h = list(map(int, input().split())) 289 dp = [0] * (n + 1) 290 dp[1] = h[0] 291 for i in range(1, n): 292 dp[i + 1] = min(dp[i] + h[i] - 1, dp[i - 1] + h[i - 1] + max(0, h[i] - i)) 293 print(dp[n]) 294 ``` 295 296 **Rate the problem!** 297 298 **Quality** 299 300 * Excellent problem 301 * Good problem 302 * Average problem 303 * Bad problem 304 * Horrible problem 305 306 **Difficulty** 307 308 * Trivial problem 309 * Easy problem 310 * Average problem 311 * Hard problem 312 * Impossible problem 313 314 [2133E - I Yearned For The Mines](/contest/2133/problem/E "Codeforces Round 1044 (Div. 2)") 315 316 **Hint 1** 317 318 Suppose the tree is a chain. Can you catch Herobrine using only operation $1$? 319 320 **Hint 2** 321 322 You can do it in only $n$ queries. 323 324 **Hint 3** 325 326 You can use all instances of operation $2$ before operation $1$. 327 328 **Hint 4** 329 330 Try tree DP/colouring. 331 332 **Solution** 333 334 Observe that if we have some connected component of $k$ nodes that is a path (i.e. each node has degree at most $2$), we can check it for the presence of Herobrine in $k$ operations by "sweeping" from one end of the path to the other with operation $1$. This can be proven by induction on the number of operations: after the $i^{th}$ operation, he cannot be in any of the first $i$ nodes in the path. 335 336 Also, it is always fine to do all instances of operation $2$ before any of operation $1$, as if we have any instance of operation $2$ after doing operation $1$, we could instead move that operation to the beginning of the sequence, and we would only be restricting Herobrine's movement. 337 338 So we need to find a way to split the tree into paths with at most $\left\lfloor\frac{n}{4}\right\rfloor$ of operation $2$, then check all the paths for Herobrine. There are a few different ways of doing this; the model solution does this by colouring the tree. Root the tree at node $1$. Let a green node be an endpoint of a path in its subtree, a yellow node be an intermediate node of a path in its subtree, and a black node be one on which we perform operation $2$. Then for each node: 339 340 * If it has three or more green children, or any yellow children, colour it black. 341 * Otherwise, if it has exactly two green children (and any other children are black), colour it yellow. 342 * Otherwise, colour it green. 343 344 We can prove this results in at most $\left\lfloor\frac{n}{4}\right\rfloor$ black nodes. For each black node, if it was coloured black because it had three (or more) green children, group it with those; if it was coloured black because it had a yellow child, group it with that node and its two green children. We have grouped each black node with at least $3$ other nodes that aren't grouped with any other black node, so if there are $x$ black nodes, we know $n \ge 4 \cdot x$. 345 346 **Code (C++)** 347 348 ``` 349 #include <bits/stdc++.h> 350 using namespace std; 351 352 typedef long long ll; 353 #define all(x) x.begin(), x.end() 354 #define vecin(name, len) vector<int> name(len); for (auto &_ : name) cin >> _; 355 #define vecout(v) for (auto _ : v) cout << _ << " "; cout << endl; 356 357 const int MAXN = 200005; 358 vector<int> adj[MAXN]; 359 int colour[MAXN]; 360 vector<pair<int, int>> ans; 361 vector<int> leaves; 362 bool vis[MAXN]; 363 364 void dfs(int node, int parent) { 365 vector<int> children; 366 for (auto a : adj[node]) 367 if (a != parent) { 368 dfs(a, node); 369 children.push_back(a); 370 } 371 int num_1_children = 0; 372 bool any_2_children = false; 373 for (auto child : children) { 374 if (colour[child] == 1) 375 num_1_children ++; 376 else if (colour[child] == 2) 377 any_2_children = true; 378 } 379 if (any_2_children || num_1_children >= 3) { 380 colour[node] = 0; 381 ans.push_back({2, node + 1}); 382 ans.push_back({1, node + 1}); 383 } else if (num_1_children == 2) { 384 colour[node] = 2; 385 } else { 386 colour[node] = 1; 387 if (num_1_children == 0) 388 leaves.push_back(node); 389 } 390 } 391 392 void dfs2(int node) { 393 vis[node] = true; 394 ans.push_back({1, node + 1}); 395 for (auto a : adj[node]) 396 if (colour[a] != 0 && !vis[a]) 397 dfs2(a); 398 } 399 400 void solve() { 401 int n; cin >> n; 402 for (int i = 0; i < n; i ++) 403 adj[i].clear(), vis[i] = false; 404 for (int i = 0; i < n - 1; i ++) { 405 int a, b; cin >> a >> b; 406 a --; b --; 407 adj[a].push_back(b); 408 adj[b].push_back(a); 409 } 410 ans.clear(); 411 leaves.clear(); 412 dfs(0, -1); 413 for (auto a : leaves) 414 if (!vis[a]) 415 dfs2(a); 416 cout << ans.size() << endl; 417 for (auto a : ans) 418 cout << a.first << " " << a.second << endl; 419 } 420 421 int main() { 422 ios_base::sync_with_stdio(false); 423 cin.tie(NULL); 424 int tt = 1; 425 426 cin >> tt; 427 428 while (tt--) solve(); 429 return 0; 430 } 431 ``` 432 433 **Rate the problem!** 434 435 **Quality** 436 437 * Excellent problem 438 * Good problem 439 * Average problem 440 * Bad problem 441 * Horrible problem 442 443 **Difficulty** 444 445 * Trivial problem 446 * Easy problem 447 * Average problem 448 * Hard problem 449 * Impossible problem 450 451 **Bonus (easy)** 452 453 Prove that $\left\lfloor \frac{5}{4} \cdot n \right\rfloor$ operations are necessary in the worst case. 454 455 **Bonus (hard)** 456 457 Implement the checker. 458 459 **Solution** 460 461 ``` 462 #include <bits/stdc++.h> 463 #include "testlib.h" 464 465 using namespace std; 466 467 bool verify(int n, vector<set<int>> adj, vector<pair<int, int>> ops) { 468 vector<bool> inpath(n, false); 469 vector<bool> irrelevant(n, false); 470 vector<set<int>> children(n); 471 vector<int> parent(n, -1); 472 473 int last_op1_node = -1; 474 vector<int> active_heads; 475 476 function<void(int)> check_for_parent = [&](int node) { 477 if (irrelevant[node] || !inpath[node]) return; 478 if (parent[node] == -1 && (int)adj[node].size() == (int)children[node].size() + 1) 479 for (auto a : adj[node]) 480 if (!children[node].count(a)) { 481 parent[node] = a; 482 children[a].insert(node); 483 } 484 }; 485 function<void(int)> destroy = [&](int node) { 486 queue<int> q; 487 q.push(node); 488 while (q.size()) { 489 int cur = q.front(); q.pop(); 490 if (parent[cur] != -1) 491 children[parent[cur]].erase(cur), parent[cur] = -1; 492 inpath[cur] = false; 493 irrelevant[cur] = true; 494 for (auto a : children[cur]) 495 q.push(a); 496 } 497 }; 498 499 for (int op = 0; op < ops.size(); op ++) { 500 int node = ops[op].second; 501 if (ops[op].first == 1 && !irrelevant[node]) { 502 if (!inpath[node]) { 503 if (children[node].size() > 0 || adj[node].size() <= 1) { 504 active_heads.push_back(node); 505 inpath[node] = true; 506 } 507 } 508 check_for_parent(node); 509 } else { 510 if (inpath[node] || node == last_op1_node) { 511 destroy(node); 512 } 513 for (auto a : adj[node]) { 514 adj[a].erase(node); 515 if (inpath[a] && parent[a] == node) 516 destroy(a); 517 if (inpath[a] && parent[a] == -1) 518 check_for_parent(a); 519 } 520 adj[node].clear(); 521 } 522 vector<int> new_heads; 523 for (auto head : active_heads) { 524 if (irrelevant[head] || !inpath[head]) continue; 525 if (adj[head].size() == children[head].size()) { 526 destroy(head); continue; 527 } 528 if (ops[op].first == 1 && (head == node || parent[head] == node)) { 529 if (head == node) 530 new_heads.push_back(head); 531 continue; 532 } 533 if (op < ops.size() - 1 && ops[op + 1].first == 1 && ops[op + 1].second == head) { 534 new_heads.push_back(head); continue; 535 } 536 if (parent[head] != -1) 537 children[parent[head]].erase(head); 538 parent[head] = -1; 539 inpath[head] = false; 540 for (auto a : children[head]) 541 new_heads.push_back(a); 542 } 543 active_heads = new_heads; 544 last_op1_node = (ops[op].first == 1) ? node : -1; 545 } 546 for (int i = 0; i < n; i ++) 547 if (!irrelevant[i]) 548 return false; 549 return true; 550 } 551 552 const int MAXN = 200005; 553 int n, t; 554 vector<int> adj_orig[MAXN]; 555 int max_ops() { 556 // floor(1.25n) 557 return (5 * n) / 4; 558 } 559 560 void readAns(InStream &in) { 561 vector<set<int>> adj(n); 562 for (int i = 0; i < n; i ++) { 563 for (auto a : adj_orig[i]) 564 adj[i].insert(a); 565 } 566 int opcnt = in.readInt(1, max_ops(), "number of operations"); 567 vector<pair<int, int>> ops; 568 for (int op = 0; op < opcnt; op ++) { 569 int tt = in.readInt(1, 2, "operation type"); 570 int node = in.readInt(1, n, "operation node"); 571 ops.push_back({tt, node - 1}); 572 } 573 if (!verify(n, adj, ops)) 574 in.quitf(_wa, "sequence of valid moves exists for Herobrine to not be caught"); 575 } 576 577 int main(int argc, char *argv[]) { 578 registerTestlibCmd(argc, argv); 579 580 t = inf.readInt(); 581 for (int i = 0; i < t; i ++) { 582 setTestCase(i + 1); 583 n = inf.readInt(); 584 for (int i = 0; i < n; i ++) 585 adj_orig[i].clear(); 586 for (int i = 0; i < n - 1; i ++) { 587 int u = inf.readInt(); 588 int v = inf.readInt(); 589 u --; v --; 590 adj_orig[u].push_back(v); 591 adj_orig[v].push_back(u); 592 } 593 594 readAns(ans); 595 readAns(ouf); 596 } 597 ans.quitif(!ans.seekEof(), _pe, "expected EOF after %d answers", t); 598 ouf.quitif(!ouf.seekEof(), _pe, "expected EOF after %d answers", t); 599 600 quitf(_ok, "very good"); 601 } 602 ``` 603 604 [2133F - Flint and Steel](/contest/2133/problem/F "Codeforces Round 1044 (Div. 2)") 605 606 **Hint 1** 607 608 Try solving it in $\mathcal{O}(n^2)$ first. 609 610 **Hint 2** 611 612 Use DP. 613 614 **Hint 3** 615 616 Use segment tree. 617 618 **Solution** 619 620 Let's first find how many detonations are required. This seems very similar to the standard problem of finding the minimum number of ranges that covers the entire array (with each creeper being the range $[i - e_i + 1, i + e_i - 1]$), but there is one key difference: two ranges cannot have intersecting midpoints. If that were the case, then whichever creeper we detonate first would kill the other, so they can't both be detonated. 621 622 A natural idea is letting $dp[i][j]$ be the minimum detonations required to kill exactly the first $i$ creepers with the rightmost creeper we use being creeper $j$. In fact, we can observe that only the states where $i = j + e_j - 1$ matter, so we can remove a dimension and instead let $dp[i]$ be the minimum detonations required to kill all the creepers up to $i + e_i - 1$ with the rightmost creeper we use being creeper $i$. 623 624 There are two cases where we can transition from some creeper $j \lt i$: either $i$ is to the right of creeper $j$'s range of detonation, so $i - e_i + 1 \le j + e_j$ and $j + e_j - 1 \lt i$, or $j$ is to the left of creeper $i$'s range of detonation, so $j \lt i - e_i + 1$ and $i - e_i + 1 \le j + e_j$. We can directly implement this to get an $\mathcal{O}(n^2)$ solution, but this is too slow. 625 626 We can optimise this further using segment tree. Let's process the creepers from $1$ to $n$ and maintain a segment tree where position $i$ stores the minimum detonations required to kill all the creepers up to $i$, using only the creepers processed so far (or $\infty$ if it's impossible). And let $dp[i]$ be the minimum detonations required to kill all the creepers up to $i + e_i - 1$, with creeper $i$ the rightmost one we use. When we reach creeper $i$, we do a point minimum update: $\text{segtree}[i + e_i - 1] = \text{min}(\text{segtree}[i + e_i - 1], \,dp[i])$. 627 628 But how do we calculate $dp[i]$? Notice that in fact we only need to perform two range minimum queries, corresponding to the two cases from earlier. For the first case, after processing the first $i - 1$ creepers, we query the range $[i - e_i, i - 1]$. And for the second case, after processing the first $i - e_i$ creepers, we query the range $[i - e_i, i + e_i - 1]$. Then $dp[i]$ is set to the smaller of those two values. We can precompute which queries need to be performed after processing each creeper to do this in $\mathcal{O}(n \,\text{log}\, n)$. The minimum detonations will then be $\text{min}_{i + e_i - 1 \ge n}(dp[i])$. 629 630 To reconstruct the set of detonated creepers, we can also have a predecessor array storing which creeper is the rightmost one to the left of creeper $i$ that should be detonated if we detonate creeper $i$, and also store that information in the segment tree. There is one more piece of the puzzle: in which order do we detonate them? If they are detonated in ascending order of explosive power, we can never get an earlier creeper in the sequence killing a later one. 631 632 **Code (C++)** 633 634 ``` 635 #include <bits/stdc++.h> 636 using namespace std; 637 638 typedef long long ll; 639 #define all(x) x.begin(), x.end() 640 #define vecin(name, len) vector<int> name(len); for (auto &_ : name) cin >> _; 641 #define vecout(v) for (auto _ : v) cout << _ << " "; cout << endl; 642 643 const int INF = 1e9; 644 645 struct segtree { 646 int n; 647 vector<pair<int, int>> tree; 648 segtree (int _n) { 649 n = 1; 650 while (n < _n) 651 n *= 2; 652 tree = vector<pair<int, int>>(2 * n, {INF, -1}); 653 } 654 void upd(int i, pair<int, int> x) { 655 i += n; 656 tree[i] = min(tree[i], x); 657 while (i > 1) { 658 i /= 2; 659 tree[i] = min(tree[2 * i], tree[2 * i + 1]); 660 } 661 } 662 pair<int, int> query(int left, int right, int index, int maxl, int maxr) { 663 if (left == maxl && right == maxr) { 664 return tree[index]; 665 } 666 int mid = (maxl + maxr) / 2; 667 pair<int, int> ans = {INF, -1}; 668 if (left <= mid) 669 ans = min(ans, query(left, min(mid, right), 2 * index, maxl, mid)); 670 if (right > mid) 671 ans = min(ans, query(max(left, mid + 1), right, 2 * index + 1, mid + 1, maxr)); 672 return ans; 673 } 674 pair<int, int> query(int left, int right) {return query(left, right, 1, 0, n - 1);} 675 }; 676 677 struct update { 678 int l; int r; int i; 679 }; 680 681 void solve() { 682 int n; cin >> n; 683 vecin(aa, n); 684 vector<vector<update>> upd(n + 1); 685 for (int i = 0; i < n; i ++) { 686 if (aa[i] == 0) 687 continue; 688 int left = max(0, i + 1 - aa[i]), right = min(n, i + aa[i] - 1); 689 upd[i].push_back((update){left, i, i + 1}); 690 upd[left].push_back((update){left, right, i + 1}); 691 } 692 vector<pair<int, int>> dp(n + 1, {INF, -1}); 693 dp[0] = {0, -1}; 694 segtree seg(n + 1); 695 seg.upd(0, {1, -1}); 696 for (int i = 0; i <= n; i ++) { 697 if (i > 0) 698 seg.upd(min(n, i + aa[i - 1] - 1), {dp[i].first + 1, i}); 699 for (auto xx : upd[i]) 700 dp[xx.i] = min(dp[xx.i], seg.query(xx.l, xx.r)); 701 } 702 if (seg.query(n, n).first == INF) { 703 cout << -1 << endl; return; 704 } 705 vector<pair<int, int>> ans; 706 int cur = seg.query(n, n).second; 707 while (cur != -1) { 708 ans.push_back({aa[cur - 1], cur}); 709 cur = dp[cur].second; 710 } 711 sort(all(ans)); 712 cout << ans.size() << endl; 713 for (auto a : ans) 714 cout << a.second << " "; 715 cout << endl; 716 } 717 718 int main() { 719 ios_base::sync_with_stdio(false); 720 cin.tie(NULL); 721 int tt = 1; 722 723 cin >> tt; 724 725 while (tt--) solve(); 726 return 0; 727 } 728 ``` 729 730 **Rate the problem!** 731 732 **Quality** 733 734 * Excellent problem 735 * Good problem 736 * Average problem 737 * Bad problem 738 * Horrible problem 739 740 **Difficulty** 741 742 * Trivial problem 743 * Easy problem 744 * Average problem 745 * Hard problem 746 * Impossible problem