What does the speed of each gear depend on?

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$$$.

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.

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define all(x) x.begin(), x.end()
#define vecin(name, len) vector<int> name(len); for (auto &_ : name) cin >> _;
#define vecout(v) for (auto _ : v) cout << _ << " "; cout << endl;


void solve() {
    int n; cin >> n;
    vecin(gears, n);
    set<int> seen;
    for (auto gear : gears) {
        if (seen.count(gear)) {
            cout << "YES" << endl; return;
        }
        seen.insert(gear);
    }
    cout << "NO" << endl;
}

int main() {
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int tt = 1;

    cin >> tt;

    while (tt--) solve();
    return 0;
}

tt = int(input())
for t in range(tt):
    n = int(input())
    gears = list(map(int, input().split()))
    valid = False
    for i in range(n):
        for j in range(i + 1, n):
            if gears[i] == gears[j]:
                valid = True
    if valid:
        print("YES")
    else:
        print("NO")

Who should you pair with the grumpiest villager?

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$$$.

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.

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.

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.

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define all(x) x.begin(), x.end()
#define vecin(name, len) vector<int> name(len); for (auto &_ : name) cin >> _;
#define vecout(v) for (auto _ : v) cout << _ << " "; cout << endl;


void solve() {
    int n; cin >> n;
    vecin(g, n);
    ll ans = 0;
    sort(all(g));
    for (int i = n - 1; i >= 0; i -= 2)
        ans += g[i];
    cout << ans << endl;
}

int main() {
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int tt = 1;

    cin >> tt;

    while (tt--) solve();
    return 0;
}

tt = int(input())
for t in range(tt):
    n = int(input())
    grumpiness = list(map(int, input().split()))
    grumpiness.sort()
    tot = 0
    for i in range(n - 1, -1, -2):
        tot += grumpiness[i]
    print(tot)

How can you find where the path should start?

How else can you use the information you gained from that?

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.

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.

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.

import sys
for test in range(int(input())):
    layers = {}
    n = int(input())
    big = -1
    path = []
    for i in range(n):
        print(f"? {i + 1} {n} {' '.join(list(map(str, list(range(1, n + 1)))))}")
        sys.stdout.flush()
        ans = int(input())
        if ans in layers:
            layers[ans].append(i + 1)
        else:
            layers[ans] = [i + 1]
        if ans > big:
            big = ans
            path = [i + 1]
    for depth in range(big - 1, 0, -1):
        for candidate in layers[depth]:
            print(f"? {path[-1]} 2 {path[-1]} {candidate}")
            sys.stdout.flush()
            ans = int(input())
            if ans == 2:
                path.append(candidate)
                break
    print(f"! {len(path)} {' '.join(list(map(str, path)))}")
    sys.stdout.flush()

Solve in $$$\frac{5}{3} \cdot n$$$ queries.

How many times can a mob take fall damage?

If a mob takes more than $$$1$$$ fall damage, what about the mob below it?

Use DP.

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.

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.

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]$$$.

t = int(input())
for test in range(t):
    n = int(input())
    h = list(map(int, input().split()))
    dp = [0] * (n + 1)
    dp[1] = h[0]
    for i in range(1, n):
        dp[i + 1] = min(dp[i] + h[i] - 1, dp[i - 1] + h[i - 1] + max(0, h[i] - i))
    print(dp[n])

Suppose the tree is a chain. Can you catch Herobrine using only operation $$$1$$$?

You can do it in only $$$n$$$ queries.

You can use all instances of operation $$$2$$$ before operation $$$1$$$.

Try tree DP/colouring.

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.

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.

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:

• If it has three or more green children, or any yellow children, colour it black.
• Otherwise, if it has exactly two green children (and any other children are black), colour it yellow.
• Otherwise, colour it green.

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$$$.

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define all(x) x.begin(), x.end()
#define vecin(name, len) vector<int> name(len); for (auto &_ : name) cin >> _;
#define vecout(v) for (auto _ : v) cout << _ << " "; cout << endl;

const int MAXN = 200005;
vector<int> adj[MAXN];
int colour[MAXN];
vector<pair<int, int>> ans;
vector<int> leaves;
bool vis[MAXN];

void dfs(int node, int parent) {
    vector<int> children;
    for (auto a : adj[node])
        if (a != parent) {
            dfs(a, node);
            children.push_back(a);
        }
    int num_1_children = 0;
    bool any_2_children = false;
    for (auto child : children) {
        if (colour[child] == 1)
            num_1_children ++;
        else if (colour[child] == 2)
            any_2_children = true;
    }
    if (any_2_children || num_1_children >= 3) {
        colour[node] = 0;
        ans.push_back({2, node + 1});
        ans.push_back({1, node + 1});
    } else if (num_1_children == 2) {
        colour[node] = 2;
    } else {
        colour[node] = 1;
        if (num_1_children == 0)
            leaves.push_back(node);
    }
}

void dfs2(int node) {
    vis[node] = true;
    ans.push_back({1, node + 1});
    for (auto a : adj[node])
        if (colour[a] != 0 && !vis[a])
            dfs2(a);
}

void solve() {
    int n; cin >> n;
    for (int i = 0; i < n; i ++)
        adj[i].clear(), vis[i] = false;
    for (int i = 0; i < n - 1; i ++) {
        int a, b; cin >> a >> b;
        a --; b --;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    ans.clear();
    leaves.clear();
    dfs(0, -1);
    for (auto a : leaves)
        if (!vis[a])
            dfs2(a);
    cout << ans.size() << endl;
    for (auto a : ans)
        cout << a.first << " " << a.second << endl;
}

int main() {
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int tt = 1;

    cin >> tt;

    while (tt--) solve();
    return 0;
}

Prove that $$$\left\lfloor \frac{5}{4} \cdot n \right\rfloor$$$ operations are necessary in the worst case.

Implement the checker.

#include <bits/stdc++.h>
#include "testlib.h"
 
using namespace std;


bool verify(int n, vector<set<int>> adj, vector<pair<int, int>> ops) {
    vector<bool> inpath(n, false);
    vector<bool> irrelevant(n, false);
    vector<set<int>> children(n);
    vector<int> parent(n, -1);

    int last_op1_node = -1;
    vector<int> active_heads;
    
    function<void(int)> check_for_parent = [&](int node) {
        if (irrelevant[node] || !inpath[node]) return;
        if (parent[node] == -1 && (int)adj[node].size() == (int)children[node].size() + 1)
            for (auto a : adj[node])
                if (!children[node].count(a)) {
                    parent[node] = a;
                    children[a].insert(node);
                }
    };
    function<void(int)> destroy = [&](int node) {
        queue<int> q;
        q.push(node);
        while (q.size()) {
            int cur = q.front(); q.pop();
            if (parent[cur] != -1)
                children[parent[cur]].erase(cur), parent[cur] = -1;
            inpath[cur] = false;
            irrelevant[cur] = true;
            for (auto a : children[cur])
                q.push(a);
        }
    };

    for (int op = 0; op < ops.size(); op ++) {
        int node = ops[op].second;
        if (ops[op].first == 1 && !irrelevant[node]) {
            if (!inpath[node]) {
                if (children[node].size() > 0 || adj[node].size() <= 1) {
                    active_heads.push_back(node);
                    inpath[node] = true;
                }
            }
            check_for_parent(node);
        } else {
            if (inpath[node] || node == last_op1_node) {
                destroy(node);
            }
            for (auto a : adj[node]) {
                adj[a].erase(node);
                if (inpath[a] && parent[a] == node)
                    destroy(a);
                if (inpath[a] && parent[a] == -1)
                    check_for_parent(a);
            }
            adj[node].clear();
        }
        vector<int> new_heads;
        for (auto head : active_heads) {
            if (irrelevant[head] || !inpath[head]) continue;
            if (adj[head].size() == children[head].size()) {
                destroy(head); continue;
            }
            if (ops[op].first == 1 && (head == node || parent[head] == node)) {
                if (head == node)
                    new_heads.push_back(head);
                continue;
            }
            if (op < ops.size() - 1 && ops[op + 1].first == 1 && ops[op + 1].second == head) {
                new_heads.push_back(head); continue;
            }
            if (parent[head] != -1)
                children[parent[head]].erase(head);
            parent[head] = -1;
            inpath[head] = false;
            for (auto a : children[head])
                new_heads.push_back(a);
        }
        active_heads = new_heads;
        last_op1_node = (ops[op].first == 1) ? node : -1;
    }
    for (int i = 0; i < n; i ++)
        if (!irrelevant[i])
            return false;
    return true;
}


const int MAXN = 200005;
int n, t;
vector<int> adj_orig[MAXN];
int max_ops() {
    // floor(1.25n)
    return (5 * n) / 4;
}

void readAns(InStream &in) {
    vector<set<int>> adj(n);
    for (int i = 0; i < n; i ++) {
        for (auto a : adj_orig[i])
            adj[i].insert(a);
    }
    int opcnt = in.readInt(1, max_ops(), "number of operations");
    vector<pair<int, int>> ops;
    for (int op = 0; op < opcnt; op ++) {
        int tt = in.readInt(1, 2, "operation type");
        int node = in.readInt(1, n, "operation node");
        ops.push_back({tt, node - 1});
    }
    if (!verify(n, adj, ops))
        in.quitf(_wa, "sequence of valid moves exists for Herobrine to not be caught");
}

int main(int argc, char *argv[]) {
    registerTestlibCmd(argc, argv);
 
    t = inf.readInt();
    for (int i = 0; i < t; i ++) {
        setTestCase(i + 1);
        n = inf.readInt();
        for (int i = 0; i < n; i ++)
            adj_orig[i].clear();
        for (int i = 0; i < n - 1; i ++) {
            int u = inf.readInt();
            int v = inf.readInt();
            u --; v --;
            adj_orig[u].push_back(v);
            adj_orig[v].push_back(u);
        }

        readAns(ans);
        readAns(ouf);
    }
    ans.quitif(!ans.seekEof(), _pe, "expected EOF after %d answers", t);
    ouf.quitif(!ouf.seekEof(), _pe, "expected EOF after %d answers", t);
 
    quitf(_ok, "very good");
}

Try solving it in $$$\mathcal{O}(n^2)$$$ first.

Use DP.

Use segment tree.

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.

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$$$.

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.

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])$$$.

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])$$$.

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.

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define all(x) x.begin(), x.end()
#define vecin(name, len) vector<int> name(len); for (auto &_ : name) cin >> _;
#define vecout(v) for (auto _ : v) cout << _ << " "; cout << endl;

const int INF = 1e9;

struct segtree {
    int n;
    vector<pair<int, int>> tree;
    segtree (int _n) {
        n = 1;
        while (n < _n)
            n *= 2;
        tree = vector<pair<int, int>>(2 * n, {INF, -1});
    }
    void upd(int i, pair<int, int> x) {
        i += n;
        tree[i] = min(tree[i], x);
        while (i > 1) {
            i /= 2;
            tree[i] = min(tree[2 * i], tree[2 * i + 1]);
        }
    }
    pair<int, int> query(int left, int right, int index, int maxl, int maxr) {
        if (left == maxl && right == maxr) {
            return tree[index];
        }
        int mid = (maxl + maxr) / 2;
        pair<int, int> ans = {INF, -1};
        if (left <= mid)
            ans = min(ans, query(left, min(mid, right), 2 * index, maxl, mid));
        if (right > mid)
            ans = min(ans, query(max(left, mid + 1), right, 2 * index + 1, mid + 1, maxr));
        return ans;
    }
    pair<int, int> query(int left, int right) {return query(left, right, 1, 0, n - 1);}
};

struct update {
    int l; int r; int i;
};

void solve() {
    int n; cin >> n;
    vecin(aa, n);
    vector<vector<update>> upd(n + 1);
    for (int i = 0; i < n; i ++) {
        if (aa[i] == 0)
            continue;
        int left = max(0, i + 1 - aa[i]), right = min(n, i + aa[i] - 1);
        upd[i].push_back((update){left, i, i + 1});
        upd[left].push_back((update){left, right, i + 1});
    }
    vector<pair<int, int>> dp(n + 1, {INF, -1});
    dp[0] = {0, -1};
    segtree seg(n + 1);
    seg.upd(0, {1, -1});
    for (int i = 0; i <= n; i ++) {
        if (i > 0)
            seg.upd(min(n, i + aa[i - 1] - 1), {dp[i].first + 1, i});
        for (auto xx : upd[i])
            dp[xx.i] = min(dp[xx.i], seg.query(xx.l, xx.r));
    }
    if (seg.query(n, n).first == INF) {
        cout << -1 << endl; return;
    }
    vector<pair<int, int>> ans;
    int cur = seg.query(n, n).second;
    while (cur != -1) {
        ans.push_back({aa[cur - 1], cur});
        cur = dp[cur].second;
    }
    sort(all(ans));
    cout << ans.size() << endl;
    for (auto a : ans)
        cout << a.second << " ";
    cout << endl;
}

int main() {
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int tt = 1;

    cin >> tt;

    while (tt--) solve();
    return 0;
}