codeforces-scrape

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

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