Let $$$y$$$ denote the final position of all of the slimes. Then it is optimal to choose $$$x = y$$$ for every operation.

Let $$$\mathrm{mn}$$$ denote the minimum value in $$$a$$$, and let $$$\mathrm{mx}$$$ denote the maximum value in $$$a$$$. Now, the number of operations that you need to apply is equal to $$$\max(y - \mathrm{mn}, \mathrm{mx} - y)$$$.

We want to choose the value of $$$y$$$ that minimizes $$$\max(y - \mathrm{mn}, \mathrm{mx} - y)$$$. Therefore, we will choose the value that is closest to the middle of $$$\mathrm{mn}$$$ and $$$\mathrm{mx}$$$. This yields a final answer of $$$\lceil \frac{\mathrm{mx} - \mathrm{mn}}{2} \rceil$$$.

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define debug(x) cout << #x << " = " << x << "\n";
#define vdebug(a) cout << #a << " = "; for(auto x: a) cout << x << " "; cout << "\n";
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int uid(int a, int b) { return uniform_int_distribution<int>(a, b)(rng); }
ll uld(ll a, ll b) { return uniform_int_distribution<ll>(a, b)(rng); }

void solve(){
    int n;
    cin >> n;

    vector<int> a(n);
    for (int &x : a) cin >> x;

    int mx = *max_element(a.begin(), a.end());
    int mn = *min_element(a.begin(), a.end());
    cout << (mx - mn + 1) / 2 << "\n";
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int t;
    cin >> t;
    while (t--) solve();
}

Consider each index separately. For one of the indices, you will gain value equal to $$$a_i + b_i$$$. For all of the other indices, you will gain value equal to $$$b_i$$$ only.

It is never bad to put the larger value in $$$b_i$$$.

We should swap any $$$a_i$$$ where $$$a_i \gt b_i$$$, because we would prefer for the larger value to be in $$$b_i$$$. In total, we gain value equal to the maximums of each pair, plus the largest of the minimums of each pair.

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define debug(x) cout << #x << " = " << x << "\n";
#define vdebug(a) cout << #a << " = "; for(auto x: a) cout << x << " "; cout << "\n";
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int uid(int a, int b) { return uniform_int_distribution<int>(a, b)(rng); }
ll uld(ll a, ll b) { return uniform_int_distribution<ll>(a, b)(rng); }

void solve(){
    int n;
    cin >> n;

    vector<int> a(n), b(n);
    for (int &x : a) cin >> x;
    for (int &x : b) cin >> x;

    ll sum = 0;
    for (int i = 0; i < n; i++)
        sum += max(a[i], b[i]);

    ll ans = 0;
    for (int i = 0; i < n; i++)
        ans = max(ans, sum + min(a[i], b[i]));
    
    cout << ans << "\n";
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int t;
    cin >> t;
    while (t--) solve();
}

Suppose you have a positive element. You can make this element negative without affecting any later elements by applying an operation onto it directly.

You can make all of the elements negative. To do so, consider each index starting from $$$n$$$ to $$$1$$$. If it is currently positive, you can apply an operation on this index, turning it negative.

Let $$$\mathrm{idx}$$$ be the largest index you ever operate on. Then since you can never flip its sign using an operation on a later index, $$$a_{\mathrm{idx}}$$$ must initially be positive, and it will be negative after performing the operation.

Read the hints. In fact, it is always possible to make all elements before $$$\mathrm{idx}$$$ positive. Thus, in the end you end up with either the original array (if you applied no operations), or an array of the form $$$[|a_1|, ..., |a_{\mathrm{idx}-1}|, -a_{\mathrm{idx}}, a_{\mathrm{idx}+1}, ..., a_n]$$$ for some $$$\mathrm{idx}$$$ where $$$a_{\mathrm{idx}}$$$ is initially positive. You can find the optimal choice of $$$\mathrm{idx}$$$ using prefix and suffix arrays.

To make all of the elements before $$$\mathrm{idx}$$$ positive, you can first make them all negative by applying the method in the easy version. Then at the end, you can perform an operation on $$$\mathrm{idx}$$$, yielding the optimal array.

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define debug(x) cout << #x << " = " << x << "\n";
#define vdebug(a) cout << #a << " = "; for(auto x: a) cout << x << " "; cout << "\n";
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int uid(int a, int b) { return uniform_int_distribution<int>(a, b)(rng); }
ll uld(ll a, ll b) { return uniform_int_distribution<ll>(a, b)(rng); }

void solve(){
    int n;
    cin >> n;

    vector<int> a(n);
    for (int &x : a) cin >> x;

    int par = 0;
    vector<int> ans;
    for (int i = n - 1; i >= 0; i--){
        if (par == 1)
            a[i] = -a[i];
        if (a[i] > 0){
            ans.push_back(i);
            par ^= 1;
        }
    }

    cout << ans.size() << "\n";
    for (int i = 0; i < ans.size(); i++)
        cout << ans[i] + 1 << " \n"[i == ans.size() - 1];
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int t;
    cin >> t;
    while (t--) solve();
}

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define debug(x) cout << #x << " = " << x << "\n";
#define vdebug(a) cout << #a << " = "; for(auto x: a) cout << x << " "; cout << "\n";
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int uid(int a, int b) { return uniform_int_distribution<int>(a, b)(rng); }
ll uld(ll a, ll b) { return uniform_int_distribution<ll>(a, b)(rng); }

void solve(){
    int n;
    cin >> n;

    vector<int> a(n);
    for (int &x : a) cin >> x;

    vector<ll> pre(n), suf(n + 1);
    pre[0] = abs(a[0]);
    for (int i = 1; i < n; i++)
        pre[i] = pre[i - 1] + abs(a[i]);
    
    suf[n - 1] = a[n - 1];
    for (int i = n - 2; i >= 0; i--)
        suf[i] = suf[i + 1] + a[i];

    ll best = suf[0];
    int idx = -1;
    for (int i = 1; i < n; i++){
        if (a[i] > 0){
            ll score = pre[i - 1] + suf[i + 1] - a[i];
            if (score > best){
                best = score;
                idx = i;
            }
        }
    }

    if (idx == -1){
        cout << "0\n";
        return;
    }

    vector<int> ans;
    for (int i = idx - 1; i >= 0; i--){
        if (ans.size() & 1)
            a[i] = -a[i];
        if (a[i] > 0)
            ans.push_back(i);
    }
    ans.push_back(idx);

    cout << ans.size() << "\n";
    for (int i = 0; i < ans.size(); i++)
        cout << ans[i] + 1 << " \n"[i == ans.size() - 1];
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int t;
    cin >> t;
    while (t--) solve();
}

Try solving the problem on a binary array; that is, all values of $$$a$$$ and $$$b$$$ are either $$$0$$$ or $$$1$$$.

Suppose you want to check if it is possible to achieve a final value of at least $$$m$$$. Then you can replace all smaller values with $$$0$$$, and all values at least $$$m$$$ with $$$1$$$. Now, solve the problem on the resulting binary array and check if it is possible to achieve a final value of $$$1$$$.

This allows you to binary search for the final answer.

Read the hints. It now suffices to solve the problem on a binary array. Let $$$\mathrm{diff} = \mathrm{cnt}_1 - \mathrm{cnt}_0$$$. Whenever you apply an operation, you lose the minimum and maximum of $$$S$$$. Therefore, the only way to change the value of $$$\mathrm{diff}$$$ is to apply an operation where the minimum and maximum of $$$S$$$ are the same; that is, all four values in $$$S$$$ are the same. If they are $$$0$$$, then $$$\mathrm{diff}$$$ increases by $$$2$$$; if they are $$$1$$$, then $$$\mathrm{diff}$$$ decreases by $$$2$$$. We want to increase $$$\mathrm{diff}$$$ as much as possible; if we can make it positive in the end, then that implies the final two values are both $$$1$$$.

Consider a subarray of indices such that there are no occurrences of $$${a_i, b_i} = {1, 1}$$$; that is, we only have either $$${a_i, b_i} = {0, 0}$$$ or $$${a_i, b_i} = {0, 1}$$$. Then we want to repeatedly perform operations within this subarray, because this will maximize the number of times we can increase $$$\mathrm{diff}$$$. Note that an operation using $$${0, 0}$$$ and $$${0, 1}$$$ will produce a $$${0, 0}$$$, so we will never lose an opportunity to increase $$$\mathrm{diff}$$$; we can apply operations within this subarray arbitrarily. Once we have applied as many operations as possible in this subarray, we are left with one pair, which is $$${0, 0}$$$ if the subarray started with a $$${0, 0}$$$, or $$${0, 1}$$$ otherwise.

Now, it is impossible to increase $$$\mathrm{diff}$$$ any further. This is because any two pairs of $$${0, 0}$$$ have a $$${1, 1}$$$ in between. Clearly, if $$$\mathrm{diff}$$$ is nonpositive, then we have already lost. If $$$\mathrm{diff}$$$ is positive, we claim we win. Indeed, if there exists any $$${0, 0}$$$ or $$${0, 1}$$$, we can perform any operation with it, thus avoiding decreasing $$$\mathrm{diff}$$$. Otherwise, if all pairs are equal to $$${1, 1}$$$, then we win trivially. This concludes the solution.

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define debug(x) cout << #x << " = " << x << "\n";
#define vdebug(a) cout << #a << " = "; for(auto x: a) cout << x << " "; cout << "\n";
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int uid(int a, int b) { return uniform_int_distribution<int>(a, b)(rng); }
ll uld(ll a, ll b) { return uniform_int_distribution<ll>(a, b)(rng); }

void solve(){
    int n;
    cin >> n;

    vector<int> a(n), b(n);
    for (int &x : a) cin >> x;
    for (int &x : b) cin >> x;

    int l = 0, r = 1e9 + 5;
    while (l < r){
        int mid = (l + r) / 2;

        int one = 0, zero = 0;
        int prev = -1;
        for (int i = 0; i < n; i++){
            int type = 0;
            if (a[i] >= mid)
                type++;
            if (b[i] >= mid)
                type++;

            if (type == 1)
                continue;

            if (type == 2){
                one++;
                prev = 1;
            }

            if (type == 0){
                if (prev != 0)
                    zero++;
                prev = 0;
            }
        }

        if (one > zero)
            l = mid + 1;
        else
            r = mid;
    }

    cout << l - 1 << "\n";
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int t;
    cin >> t;
    while (t--) solve();
}

$$$n$$$ will never be removed, and will always be added to $$$S$$$.

Try rooting at $$$n$$$.

Read the hints, through this editorial I will consider $$$n$$$ to be the root of the tree.

Lets try to determine the following for each node. When we add $$$x$$$ to $$$S$$$ for the first time, what can the largest element of $$$S$$$ be before this point. Lets try to find some necessary conditions for this.

• $$$\max(S) \lt x$$$, this is true because the maximum leaf is non-decreasing.
• $$$\max(S)$$$ is greater than the largest element in the subtree of $$$x$$$ (excluding $$$x$$$ itself). Since $$$n$$$ can never be removed, in order for $$$x$$$ to become a leaf, we must first remove everything in its subtree. For this to happen there must be some leaf outside the subtree of $$$x$$$ which is bigger than each element of the subtree. During this process a greater element will be added to $$$S$$$.

$$$\text{subtree}(x)$$$ will be used to denote the subtree of $$$x$$$ excluding $$$x$$$ itself. Remember that we rooted the tree at $$$n$$$.

It turns out that these conditions are also sufficient. i.e. if $$$\max(\text{subtree}(x)) \lt \max(S) \lt x$$$, then we are able to add $$$x$$$ into $$$S$$$ without needing to include any additional elements ($$$S := S \cup \lbrace x \rbrace$$$). We can prove that this is true because if the current largest leaf is larger than $$$\max(\text{subtree}(x))$$$, then we are able to remove the entire subtree of $$$x$$$ without changing the maximum. $$$x$$$ now becomes a leaf and because $$$\max(S) \lt x$$$, $$$x$$$ will be the new maximum and added on the next turn.

Thus we can solve this problem with dynamic programming where $$$dp_i$$$ is the number of ways to reach a state where $$$\max(S) = i$$$. The initial state has only the max leaf set to $$$1$$$.

$$$dp_i$$$ can transition to $$$dp_j$$$ if and only if $$$\max(\text{subtree}(j)) \lt i \lt j$$$. These transitions conveniently form ranges, so we can simulate all the transitions using prefix sums in $$$O(n)$$$.

It should be note that transitions to $$$n$$$ are a special case, a node $$$x$$$ can transition to $$$n$$$ if and only if we can delete all children of $$$n$$$ excluding the one with $$$x$$$ in its subtree. In other words all nodes outside the subtree that contains $$$x$$$ are smaller than it.

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define debug(x) cout << #x << " = " << x << "\n";
#define vdebug(a) cout << #a << " = "; for(auto x: a) cout << x << " "; cout << "\n";
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int uid(int a, int b) { return uniform_int_distribution<int>(a, b)(rng); }
ll uld(ll a, ll b) { return uniform_int_distribution<ll>(a, b)(rng); }

const int MOD = 998244353;

template<ll mod> // template was not stolen from https://codeforces.me/profile/SharpEdged
struct modnum {
    static constexpr bool is_big_mod = mod > numeric_limits<int>::max();

    using S = conditional_t<is_big_mod, ll, int>;
    using L = conditional_t<is_big_mod, __int128, ll>;

    S x;

    modnum() : x(0) {}
    modnum(ll _x) {
        _x %= static_cast<ll>(mod);
        if (_x < 0) { _x += mod; }
        x = _x;
    }

    modnum pow(ll n) const {
        modnum res = 1;
        modnum cur = *this;
        while (n > 0) {
            if (n & 1) res *= cur;
            cur *= cur;
            n /= 2;
        }
        return res;
    }
    modnum inv() const { return (*this).pow(mod-2); }
    
    modnum& operator+=(const modnum& a){
        x += a.x;
        if (x >= mod) x -= mod;
        return *this;
    }
    modnum& operator-=(const modnum& a){
        if (x < a.x) x += mod;
        x -= a.x;
        return *this;
    }
    modnum& operator*=(const modnum& a){
        x = static_cast<L>(x) * a.x % mod;
        return *this;
    }
    modnum& operator/=(const modnum& a){ return *this *= a.inv(); }
    
    friend modnum operator+(const modnum& a, const modnum& b){ return modnum(a) += b; }
    friend modnum operator-(const modnum& a, const modnum& b){ return modnum(a) -= b; }
    friend modnum operator*(const modnum& a, const modnum& b){ return modnum(a) *= b; }
    friend modnum operator/(const modnum& a, const modnum& b){ return modnum(a) /= b; }
    
    friend bool operator==(const modnum& a, const modnum& b){ return a.x == b.x; }
    friend bool operator!=(const modnum& a, const modnum& b){ return a.x != b.x; }
    friend bool operator<(const modnum& a, const modnum& b){ return a.x < b.x; }

    friend ostream& operator<<(ostream& os, const modnum& a){ os << a.x; return os; }
    friend istream& operator>>(istream& is, modnum& a) { ll x; is >> x; a = modnum(x); return is; }
};

using mint = modnum<MOD>;

void solve(){
    int n;
    cin >> n;

    vector<vector<int>> g(n);
    for (int i = 0; i < n - 1; i++){
        int u, v;
        cin >> u >> v;
        u--;
        v--;

        g[u].push_back(v);
        g[v].push_back(u);
    }

    if (g[n - 1].size() == 1){
        cout << "1\n";
        return;
    }

    vector<int> mx(n);
    auto dfs = [&](auto self, int c, int p) -> void{
        for (int x : g[c]){
            if (x == p)
                continue;

            self(self, x, c);
            mx[c] = max({mx[c], x, mx[x]});
        }
    };
    dfs(dfs, n - 1, -1);

    set<int, greater<int>> s;
    for (int i = 0; i < n - 1; i++)
        s.insert(i);

    vector<int> cur;
    auto dfs2 = [&](auto self, int c, int p) -> void{
        s.erase(c);
        cur.push_back(c);

        for (int x : g[c]){
            if (x == p)
                continue;

            self(self, x, c);
        }
    };
    
    vector<bool> ok(n); // can transition to n
    for (int x : g[n - 1]){
        dfs2(dfs2, x, n - 1);

        for (int u : cur){
            if (u > (*s.begin()))
                ok[u] = true;
        }

        for (int u : cur)
            s.insert(u);
        cur.clear();
    }
    ok[n - 1] = true;

    int idx = -1;
    for (int i = 0; i < n; i++){
        if (g[i].size() == 1)
            idx = i;
    }

    vector<mint> dp(n), pre(n);
    dp[idx] = 1;
    pre[idx] = 1;
    for (int i = idx + 1; i < n - 1; i++){
        int l = mx[i] + 1;

        if (l < i){
            dp[i] = pre[i - 1];
            if (l > 0)
                dp[i] -= pre[l - 1];
        }

        pre[i] = dp[i] + pre[i - 1];
    }

    mint ans = 0;
    for (int i = 0; i < n; i++){
        if (ok[i])
            ans += dp[i];
    }

    cout << ans << "\n";
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int t;
    cin >> t;
    while (t--) solve();
}

Which element of $$$a$$$ is it optimal to use last?

Suppose you know which element you're placing last. Now what does the problem reduce to?

Binary search is your friend.

We will prove that it's optimal to place the maximum value of $$$a$$$ last in the array. After we've done that, the problem now becomes maximising the minimum value of $$$b$$$ after rearranging the rest of the values in $$$a$$$.

To maximise the minimum value of $$$b$$$, we can binary search it. To check whether it's $$$\le v$$$, we can do a bitmask DP which finds the maximum number of disjoint subsets of $$$a$$$ whose sum is $$$\ge v$$$, and check whether we have at least $$$k$$$ of them. There exists a simple greedy algorithm, once we have these subsets, to construct an ordering which gets us the value of v: we assign each subset to a position in array $$$b$$$, and simulate the process; whenever an index is chosen to be added to, we choose the highest remaining number from the corresponding subset.

We can make the bitmask dp in the form dp[mask] = maximum {number of groups, leftover}. There are $$$O(n)$$$ transitions from each mask (adding each possible extra element to the mask), so it runs in $$$O(2^n \cdot n)$$$. Since the difference between min and max in $$$b$$$ is at most $$$max(a)$$$, we can find an upper and lower bound for the binary search which are A apart, so time complexity ends up being $$$O(n \cdot 2^n \cdot log(A))$$$.

We can use this greedy algorithm to prove that $$$max(a)$$$ can always be placed last (let's call it $$$x$$$). Suppose we have an optimal rearrangement with $$$x$$$ not being last, and let's consider the set of values which go in each position in array $$$b$$$. Consider the last item added to the maximum pile (let's call it $$$y$$$) and the pile where $$$x$$$ was added. If we remove $$$y$$$ from its pile, its pile is now $$$min(b)$$$. If we remove $$$x$$$ from its pile and add $$$y$$$ to it, there are two cases: 1. $$$y$$$'s original pile is still the min. Greedily construct this min and add $$$x$$$ last, and $$$pile = ans - y + x \ge ans$$$ so it's a maximal construction. 2. $$$x$$$'s original pile is now the min. Greedily construct this min and add $$$x$$$ last, and $$$pile \ge ans - y - x + y + x = ans$$$ so it's a maximal construction.

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

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


void solve() {
    int n, k; cin >> n >> k;
    vecin(aa, n); sort(all(aa));
    n --;
    ll extra = aa.back(); aa.pop_back();

    ll L = 0, R = extra * (ll)n;
    while (L != R) {
        ll mid = (L + R + 1) / 2;
        vector<pair<int, ll>> dp(1 << n, {0, 0});
        for (int i = 1; i < (1 << n); i ++) {
            for (int j = 0; (1 << j) <= i; j ++) {
                if (!(i & (1 << j))) continue;
                int res = i ^ (1 << j);
                pair<int, ll> cur = dp[res];
                cur.second += aa[j];
                if (cur.second >= mid)
                    cur = {cur.first + 1, 0};
                dp[i] = max(dp[i], cur);
            }
        }
        if (dp[(1 << n) - 1].first >= k)
            L = mid;
        else
            R = mid - 1;
    }
    cout << L + extra << endl;
}

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

    cin >> tt;

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

When is it optimal to stay at a house for more than $$$1$$$ day?

Suppose you are staying at a house for more than $$$1$$$ day. When should you arrive at that house?

Suppose you are staying at a house for more than $$$1$$$ day. Which houses could you previously have come from?

First, observe that any house you stay at for longer than $$$1$$$ day should be a prefix maximum on the path from house $$$x$$$, otherwise it's at least as good to stay on the previous house with greater $$$h_i$$$ on the path from house $$$x$$$.

Also, if you are going to stay at a house for longer than $$$1$$$ day, it is optimal to reach it as early as possible. Assume you stay at it for longer than 1 day but also don't reach it as early as possible: if the previous house you stayed at for longer than $$$1$$$ day had greater or equal hospitality you could have stayed there instead for an extra day and it would not be worse, and if it had lower hospitality you should have reached the new house earlier.

Finally, if you are going to switch directions in an optimal solution, you should go all the way past house $$$x$$$ before switching directions again. This is because if you switch directions at a house that is not a prefix maximum, it would have been better to just stay at the last prefix maximum for longer; and if you switch directions at a prefix maximum, but don't immediately go all the way past $$$x$$$, you should have stayed at that prefix maximum for longer.

We can maintain for each house the maximum possible satisfaction we can achieve if we reach it as early as possible. We know that for each house, the optimal answer if we finish on that house at time $$$y$$$ depends only on the house with the next largest $$$h_i$$$ on the path to $$$x$$$, and the maximum answer for having previously stayed on the other side of $$$x$$$ then gone straight to that house.

For the former case, we can maintain which house is the prefix maximum on both sides, and for the latter case, we can use convex hull trick or LCT to keep track of the best satisfaction if we arrive on house $$$x$$$ at exactly time $$$y$$$ from either side. We use two pointers for the leftmost and rightmost currently reachable houses and update whenever a new prefix maximum becomes reachable. We also need prefix sums to track the increase in satisfaction of any houses we pass on the path to the next prefix maximum. You also need to be careful to not immediately insert a new house into the CHT/LCT, but only as soon as the next prefix maximum on the other side can actually reach it. The implementation is a bit horrible and the time complexity is $$$O(n log n)$$$, although it can also be implemented in $$$O(n)$$$.

Suppose you are staying at a house for more than $$$1$$$ day. Which houses could you go to next?

The boring solution uses a "pull DP". What if instead we used a "push DP"? In fact, we can show that whenever you reach a prefix maximum, the next house you will move to is either the next higher prefix maximum on that side of $$$x$$$, or the next highest prefix maximum on the other side of $$$x$$$. So we can precalculate both those things using a monotonic stack, and perform the transitions to both those houses (if they exist), assuming we reach them as early as possible. This is easy to implement in $$$O(n)$$$.

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

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


struct Line {
	mutable ll k, m, p;
	bool operator<(const Line& o) const { return k < o.k; }
	bool operator<(ll x) const { return p < x; }
    ll eval(ll x) { return k * x + m; }
};

struct LineContainer : multiset<Line, less<>> {
	static const ll inf = LLONG_MAX;
	ll div(ll a, ll b) {
		return a / b - ((a ^ b) < 0 && a % b); }
	bool isect(iterator x, iterator y) {
		if (y == end()) return x->p = inf, 0;
		if (x->k == y->k) x->p = x->m > y->m ? inf : -inf;
		else x->p = div(y->m - x->m, x->k - y->k);
		return x->p >= y->p;
	}
	void add(ll k, ll m) {
		auto z = insert({k, m, 0}), y = z++, x = y;
		while (isect(y, z)) z = erase(z);
		if (x != begin() && isect(--x, y)) isect(x, y = erase(y));
		while ((y = x) != begin() && (--x)->p >= y->p)
			isect(x, erase(y));
	}
	ll query(ll x) {
		assert(!empty());
		auto l = *lower_bound(x);
		return l.eval(x);
	}
};

vector<ll> h;
vector<ll> pref;

ll range_sum(int L, int R) {
    return pref[R + 1] - pref[L];
}

void solve() {
    int n, t, x; cin >> n >> t >> x;
    x --;
    h.resize(n); pref.resize(n + 1);
    pref[0] = 0;
    for (int i = 0; i < n; i ++) {
        cin >> h[i];
        pref[i + 1] = pref[i] + h[i];
    }
    vecin(d, n - 1);
    for (int i = x - 2; i >= 0; i --) {
        d[i] = max(d[i], d[i + 1] + 1);
    }
    for (int i = x; i < n - 2; i ++) {
        d[i + 1] = max(d[i + 1], d[i] + 1);
    }

    ll ans = h[x] * t;
    int L = x, R = x;
    Line curleft = {h[x], 0, 0}, curright = {h[x], 0, 0};
    int left_best = x, right_best = x;
    LineContainer left, right;
    left.add(h[x], 0); right.add(h[x], 0);
    queue<pair<int, pair<ll, ll>>> add_left, add_right;
    while (L > 0 || R < n - 1) {
        int left_time = (L == 0) ? 2e9 : d[L - 1];
        int right_time = (R == n - 1) ? 2e9 : d[R];
        if (min(left_time, right_time) > t) break;
        if (left_time <= right_time) {
            L --;
            if (h[L] > curleft.k) {
                // best = max sum on day left_time-1 on house L+1
                int pref_dist = left_best - L;
                int start_dist = x - L;
                while (add_right.size() && add_right.front().first <= left_time - start_dist) {
                    right.add(add_right.front().second.first, add_right.front().second.second);
                    add_right.pop();
                }
                ll best = max(
                    curleft.eval(left_time - pref_dist) + range_sum(L + 1, left_best - 1),
                    right.query(left_time - start_dist) + range_sum(L + 1, x - 1)
                );
                // cout << L << " " << h[L] << " " << best << endl;
                ans = max(ans, best + (t - left_time + 1) * h[L]);
                left_best = L;
                curleft = {h[L], best - (left_time - 1) * h[L], 0};
                add_left.push({left_time + start_dist, {h[L], best - (left_time - 1 + start_dist) * h[L] + range_sum(L + 1, x)}});
            }
        } else {
            R ++;
            if (h[R] > curright.k) {
                // best = max sum on day right_time-1 on house R-1
                int pref_dist = R - right_best;
                int start_dist = R - x;
                while (add_left.size() && add_left.front().first <= right_time - start_dist) {
                    left.add(add_left.front().second.first, add_left.front().second.second);
                    add_left.pop();
                }
                ll best = max(
                    curright.eval(right_time - pref_dist) + range_sum(right_best + 1, R - 1),
                    left.query(right_time - start_dist) + range_sum(x + 1, R - 1)
                );
                // cout << R << " " << h[R] << " " << best << endl;
                ans = max(ans, best + (t - right_time + 1) * h[R]);
                right_best = R;
                curright = {h[R], best - (right_time - 1) * h[R], 0};
                add_right.push({right_time + start_dist, {h[R], best - (right_time - 1 + start_dist) * h[R] + range_sum(x, R - 1)}});
            }
        }
    }
    cout << ans << endl;
}

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

    cin >> tt;

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

#include <bits/stdc++.h>
 
using namespace std;
 
using ll = long long;
using vi = vector<int>;
using vl = vector<ll>;
using pl = pair<ll, ll>;
template <class T>
using vc = vector<T>;
 
template <class T>
constexpr T infty = 0;
template <>
constexpr ll infty<ll> = 2'020'000'000'000'000'000;
 
#define FOR2(i, a) for (int i = 0; i < int(a); ++i)
#define FOR3(i, a, b) for (int i = int(a); i < int(b); ++i)
#define FOR2_R(i, a) for (int i = int(a) - 1; i >= 0; --i)
#define overload4(a, b, c, d, e, ...) e
#define overload3(a, b, c, d, ...) d
#define FOR(...) overload4(__VA_ARGS__, _4, FOR3, FOR2, _1)(__VA_ARGS__)
#define FOR_R(...) overload3(__VA_ARGS__, _3, FOR2_R, _1)(__VA_ARGS__)
 
#define all(x) (x).begin(), (x).end()
#define trav(a, x) for (auto& a : x)
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
 
template <class T, class S>
inline bool chmax(T &a, const S &b) {
    T c = max<T>(a, b);
    bool changed = (c != a);
    a = c;
    return changed;
}
 
template <class T>
void rd(T &x) { cin >> x; }
 
template <class T>
void rd(vc<T> &x) { for (auto &d : x) rd(d); }
 
void read() {}
template <class H, class... T>
void read(H &h, T &...t) { rd(h), read(t...); }
 
void print() { cout << '\n'; }
template <class Head, class... Tail>
void print(Head &&head, Tail &&...tail) {
    cout << head;
    if (sizeof...(Tail)) cout << ' ';
    print(forward<Tail>(tail)...);
}
 
#define INT(...)   int __VA_ARGS__; read(__VA_ARGS__)
#define LL(...)    ll __VA_ARGS__; read(__VA_ARGS__)
#define VEC(type, name, size) vector<type> name(size); read(name)
 




void solve() {
    INT(N); LL(tot); INT(X);
    X--;
    VEC(ll, A, N);
    VEC(ll, D, N-1);
    vl T(N);
    T[X] = 1;
    FOR(i, X, N-1) {
        T[i+1] = max(T[i]+1, D[i]);
        if (i == X && D[i] == 1) T[i+1] = 1;
    }
    FOR_R(i, X) {
        T[i] = max(T[i+1]+1, D[i]);
        if (i == X-1 && D[i] == 1) T[i] = 1;
    }
    vi nh(N), lh(N);
    vc<pl> stk;
    stk.eb(mp(N, 2e9));
    FOR_R(i, N) {
        while (stk.back().se <= A[i]) stk.pop_back();
        nh[i] = stk.back().fi;
        stk.eb(mp(i, A[i]));
    }
    stk.clear();
    stk.eb(mp(-1, 2e9));
    FOR(i, N) {
        while (stk.back().se <= A[i]) stk.pop_back();
        lh[i] = stk.back().fi;
        stk.eb(mp(i, A[i]));
    }
 
    ll dp[N];
    FOR(i, N) {
        dp[i] = -infty<ll>;
    }
    FOR(i, N) dp[i] = 0;
    vc<pl> vals; FOR(i, N) vals.eb(mp(T[i], i));
    sort(all(vals));
    ll ans = 0;
    vl ps; ps.eb(0);
    FOR(i, N) ps.eb(ps.back()+A[i]);
    trav(xx, vals) {
        int i = xx.se;
        if (dp[i] < 0) continue;
        chmax(ans, (tot - T[i] + 1) * A[i] + dp[i]);
        vi ops = {nh[i], lh[i]};
        trav(j, ops) {
            if (j < 0 || j >= N) continue;
            if (abs(j-i) > T[j] - T[i]) {
                continue;
            }
            chmax(dp[j], dp[i] + (T[j] - T[i] - abs(j-i) + 1) * A[i] + ps[max(i, j)] - ps[min(i, j) + 1]);
        }
    }
 
    print(ans);
}
 
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    INT(T);
    FOR(t, T) {
        solve();
    }
    return 0;
}

Imagine the string has no $$$\mathtt{?}$$$ characters, try to find a greedy which can check if a string $$$t$$$ can be generated from $$$s$$$ by applying the operation.

Try to generalise this greedy for when there are $$$\mathtt{?}$$$ characters.

Read the hints. A correct greedy for the no $$$\mathtt{?}$$$ character version is perhaps the simplest one you can try, which is as follows:

We would like to find a subsequence of $$$s$$$ which is equal to $$$t$$$, where each substring between consecutive characters contains an even number of $$$\mathtt{1}$$$. We can find this by iterating through the characters of $$$t$$$. For each character find the first character in $$$s$$$ where $$$s_j = t_i$$$ and the substring between $$$s_j$$$ and the previously chosen character contains an even number of $$$\mathtt{1}$$$.

We can prove correctness by contradiction. Say we have a matching where at some point we didn't chose the earliest match, say between $$$t_i$$$ and $$$t_{i + 1}$$$ (we matched with a later position for $$$t_{i + 1}$$$). We can adjust our matching to instead take the earliest position for $$$t_{i + 1}$$$, call this earliest position $$$x$$$. Since we know the substring from $$$t_i$$$ to $$$x$$$ is removable and the substring from $$$t_i$$$ to $$$t_{i + 1}$$$ is removable, we can deduce that the substring from $$$x$$$ to $$$t_{i + 1}$$$ is removable. Because $$$t_{i + 1}$$$ to $$$t_{i + 2}$$$ is removeable and $$$x$$$ to $$$t_{i + 1}$$$ is removable, we can deduce that $$$x$$$ to $$$t_{i + 2}$$$ will also be removable. Thus matching the earliest option is always optimal.

Now lets try to generalise this when there are $$$\mathtt{?}$$$ characters. Naïvely using the same greedy does not work, consider a case like $$$s = \mathtt{?10000000}$$$, $$$t = \mathtt{10000000}$$$. If we match the first $$$\mathtt{1}$$$ with the $$$\mathtt{?}$$$ we get stuck, instead we should set the $$$\mathtt{?}$$$ to $$$\mathtt{0}$$$ and match with the $$$\mathtt{1}$$$.

Let's analyse why we fail this counter case. It fails because we incorrectly assign the value of a $$$\mathtt{?}$$$, and in general this will always be why the greedy fails, since we already know this approach would be correct after replacing all $$$\mathtt{?}$$$. When we encounter a $$$\mathtt{?}$$$ during the greedy, our choice of replacement determines the parity of the count of $$$\mathtt{1}$$$ in the current suffix. If chose incorrectly we get "locked" on the incorrect parity and are forced to consume suboptimally.

To fix this problem, we can adjust our greedy to consider both parities at the same time. Instead of considering only the earliest match, we consider the earliest match for each parity. For each character $$$t_i$$$, we will compute the pair $$$(\text{best}_0, \text{best}_1)$$$, where $$$\text{best}_0$$$ is the earliest match with an even count of $$$1$$$ in the suffix and $$$\text{best}_1$$$ is the earliest match with an odd count of $$$1$$$ in the suffix (note that each $$$\mathtt{?}$$$ does not contribute to the suffix parity). When we transition we only need to consider the $$$4$$$ combinations of new parity and old parity. Now the entire string will be generatable if and only if the substring $$$s_{best_i + 1},s_{best_i + 2},\ldots,s_n$$$ is removable for at least one element of the final pair.

The proof for this greedy is similar to the naïve greedy in the no $$$\mathtt{?}$$$ version. However this time we prove that for any step, if we fix the parity of the new suffix, then taking the earliest choice is always optimal. And now since we always consider both suffix parities, we will always find a matching if one exists.

Now for counting, we can run dynamic programming on this greedy. Where $$$dp_{i, j}$$$ is the number of strings with ending greedy pair $$$(i, j)$$$, for transitions we only need to try appending $$$\mathtt{0}$$$ and $$$\mathtt{1}$$$ to the string. To fit the time limit of the problem, we need to be able to find transitions in $$$O(1)$$$. Because the problem allows $$$O(n^2)$$$ anyway, we can pre-calculate the earliest even and odd match for each position. This allows us to calculate the transitions for pairs in $$$O(1)$$$.

Thus, the final time complexity is $$$O(n^2)$$$.

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define debug(x) cout << #x << " = " << x << "\n";
#define vdebug(a) cout << #a << " = "; for(auto x: a) cout << x << " "; cout << "\n";
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int uid(int a, int b) { return uniform_int_distribution<int>(a, b)(rng); }
ll uld(ll a, ll b) { return uniform_int_distribution<ll>(a, b)(rng); }

const int MOD = 998244353;

template<ll mod> // template was not stolen from https://codeforces.me/profile/SharpEdged
struct modnum {
    static constexpr bool is_big_mod = mod > numeric_limits<int>::max();

    using S = conditional_t<is_big_mod, ll, int>;
    using L = conditional_t<is_big_mod, __int128, ll>;

    S x;

    modnum() : x(0) {}
    modnum(ll _x) {
        _x %= static_cast<ll>(mod);
        if (_x < 0) { _x += mod; }
        x = _x;
    }

    modnum pow(ll n) const {
        modnum res = 1;
        modnum cur = *this;
        while (n > 0) {
            if (n & 1) res *= cur;
            cur *= cur;
            n /= 2;
        }
        return res;
    }
    modnum inv() const { return (*this).pow(mod-2); }
    
    modnum& operator+=(const modnum& a){
        x += a.x;
        if (x >= mod) x -= mod;
        return *this;
    }
    modnum& operator-=(const modnum& a){
        if (x < a.x) x += mod;
        x -= a.x;
        return *this;
    }
    modnum& operator*=(const modnum& a){
        x = static_cast<L>(x) * a.x % mod;
        return *this;
    }
    modnum& operator/=(const modnum& a){ return *this *= a.inv(); }
    
    friend modnum operator+(const modnum& a, const modnum& b){ return modnum(a) += b; }
    friend modnum operator-(const modnum& a, const modnum& b){ return modnum(a) -= b; }
    friend modnum operator*(const modnum& a, const modnum& b){ return modnum(a) *= b; }
    friend modnum operator/(const modnum& a, const modnum& b){ return modnum(a) /= b; }
    
    friend bool operator==(const modnum& a, const modnum& b){ return a.x == b.x; }
    friend bool operator!=(const modnum& a, const modnum& b){ return a.x != b.x; }
    friend bool operator<(const modnum& a, const modnum& b){ return a.x < b.x; }

    friend ostream& operator<<(ostream& os, const modnum& a){ os << a.x; return os; }
    friend istream& operator>>(istream& is, modnum& a) { ll x; is >> x; a = modnum(x); return is; }
};

using mint = modnum<MOD>;

void solve(){
    int n;
    cin >> n;

    string s;
    cin >> s;

    s = '0' + s;
    n++;

    vector<int> pre(n);
    pre[0] = s[0] == '1';
    for (int i = 1; i < n; i++){
        pre[i] = pre[i - 1] + (s[i] == '1');
    }

    vector<array<array<int, 2>, 2>> to(n + 1);
    for (int i = 0; i <= n; i++){
        to[i][0][0] = n;
        to[i][0][1] = n;
        to[i][1][0] = n;
        to[i][1][1] = n;

        int cnt = 0;
        bool wowee = false;
        for (int j = i + 1; j < n; j++){
            if ((cnt & 1) && !wowee){
                if (s[j] == '1')
                    cnt++;
                if (s[j] == '?')
                    wowee = true;
                continue;
            }
            
            if (s[j] == '1')
                cnt++;
            if (s[j] == '?')
                wowee = true;

            int par = pre[j] & 1;
            if (s[j] == '?'){
                to[i][0][par] = min(to[i][0][par], j);
                to[i][1][par] = min(to[i][1][par], j);
                continue;
            }

            int omg = s[j] - '0';
            to[i][omg][par] = min(to[i][omg][par], j);
        }
    }

    vector<bool> good(n + 1);
    int cnt = 0;
    int wowee = false;
    for (int i = n - 1; i >= 0; i--){
        good[i] = (cnt % 2 == 0) || wowee;
        if (s[i] == '1')
            cnt++;
        if (s[i] == '?')
            wowee = true;
    }

    mint ans = 0;
    vector<vector<mint>> dp(n + 1, vector<mint>(n + 1));
    dp[0][n] = 1;

    vector<array<int, 2>> ord;
    for (int i = 0; i <= n; i++){
        for (int j = i; j <= n; j++){
            ord.push_back({i, j});
            if (j != i)
                ord.push_back({j, i});
        }
    }

    for (auto [i, j] : ord){
        for (int nxt = 0; nxt < 2; nxt++){
            int even = min(to[i][nxt][0], to[j][nxt][0]);
            int odd = min(to[i][nxt][1], to[j][nxt][1]);
            dp[even][odd] += dp[i][j];
        }

        if (good[i] || good[j])
            ans += dp[i][j];
    }

    cout << ans << "\n";
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int t;
    cin >> t;
    while (t--) solve();
}

It's not convex, monotone, monge, FFT, centroid, or any other fancy trick like that. The solution is simpler than you might expect.

Reformulate the formula for score so that it's in terms of nodes in the subtree from root, not the path to the root.

Suppose you wanted to solve for a single root in $$$O(n^2)$$$. How would you do it?

Why is naive rerooting $$$O(n^3)$$$ on a tree like this?

How many DP values do you compute for the node labelled X? How many do you actually care about?

In general, how many DP values do you actually care about for a node?

Let:

• $$$dp_1[i][j]$$$ be the maximum score of a subset of nodes \textbf{in} the subtree of node $$$i$$$, assuming the selected root is $$$i$$$ or an ancestor of $$$i$$$, which uses exactly $$$j$$$ nodes.
• $$$dp_2[i][j]$$$ be the maximum score of a subset of nodes \textbf{in} the subtree of node $$$i$$$ assuming the selected root is $$$i$$$ or an ancestor of $$$i$$$, which uses exactly $$$j$$$ nodes, and does not have node $$$i$$$ selected.
• $$$dp_3[i][j]$$$ be the maximum score of a subset of nodes \textbf{outside} the subtree of node $$$i$$$, assuming the selected root is $$$i$$$ or in its subtree, which uses exactly $$$j$$$ nodes.

We can compute $$$dp_1$$$ and $$$dp_2$$$ using Trick 7 in $$$O(n^2)$$$. The tricky part is $$$dp_3$$$. The critical observation is that for each node $$$i$$$ with a subtree size of $$$sz(i)$$$, we only care about the $$$sz(i)$$$ largest values of $$$dp_3[i]$$$, that is: $$$dp_3[i][k - sz(i)], dp_3[i][k - sz(i) + 1], \ldots, dp3_[i][k - 1]$$$. This is because if we select fewer than $$$k - sz(i)$$$ nodes outside of the subtree of $$$i$$$, then we have selected fewer than $$$k$$$ nodes overall and the solution is not optimal. There are now two ways to continue.

Let us compute $$$dp_3$$$ in a way similar to Trick 7. Initially we have $$$dp_3[0][j] = 0$$$ for all $$$j$$$ (since the root has no parents).

Suppose we are at a node $$$u$$$ with children $$$c_1, c_2, \ldots, c_m$$$ and we have already computed $$$dp_3[u]$$$. Let $$$pref[i][j]$$$ be the max score we can achieve by selecting $$$j$$$ nodes out of the subtrees of $$$c_1, \ldots, c_i$$$. And let $$$suf[i][j]$$$ be the max score we can achieve by selecting $$$j$$$ nodes out of the subtrees of $$$c_i, \ldots, c_m$$$ and nodes outside of the subtree of $$$u$$$. Then for each child we obtain the largest $$$sz(c_i0$$$ values of $$$dp_3[c_i]$$$ by merging $$$pref[i - 1]$$$ and $$$suf[i + 1]$$$.

Observe that we only need to compute $$$\Sigma_{j\le i}sz(c_i)$$$ values of $$$pref[i]$$$, and $$$\Sigma_{j\ge i}sz(c_i)$$$ values of $$$suf[i]$$$. So by the same argument as Trick 7 running in $$$O(n^2)$$$, this DP also runs in $$$O(n^2)$$$.

All that remains is to add the contribution of node $$$u$$$ to each of its child values with $$$dp_3[c_i][j] = max(dp_3[c_i][j], dp_3[c_i][j - 1] + j \cdot w_u)$$$. Then the answer for each root is $$$max(dp_2[x][j] + dp_3[x][k - 1 - j] + k \cdot w[i])$$$.

Suppose the tree is a binary tree. Then, for a node $$$u$$$ with children $$$c_1, c_2$$$, we can just naively merge $$$dp_1[c_2]$$$ and $$$dp_3[u]$$$ to get $$$dp_3[c_1]$$$, and merge $$$dp_1[c_1]$$$ and $$$dp_3[u]$$$ to get $$$dp_3[c_2]$$$ (then add the contribution of $$$u$$$ with $$$dp_3[c_i][j] = max(dp_3[c_i][j], dp_3[c_i][j - 1] + j \cdot w_u)$$$). And this magically runs in $$$O(n^2)$$$, because both the convolutions run in $$$sz(c_1) \cdot sz(c_2)$$$, and the sum across all nodes of $$$sz(c_1) \cdot sz(c_2)$$$ exactly corresponds to each pair of nodes once.

What if the tree is not a binary tree? We can make it one! If a node $$$u$$$ has $$$m$$$ children, add $$$m-3$$$ dummy nodes $$$d_1, d_2, \ldots, d_{m-3}$$$ in a chain and connect the children to them like this:

The only thing to watch out for is that the contribution of the original node $$$u$$$ must be done for each original child, not for the dummy nodes. The number of nodes is still $$$O(n)$$$ so it runs in $$$O(n^2)$$$.

#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 = 4005;

ll dp_down[MAXN][MAXN], dp_down_take[MAXN][MAXN], dp_up[MAXN][MAXN];
ll pref_merge[MAXN][MAXN], suff_merge[MAXN][MAXN];
vector<int> adj[MAXN];
vector<int> children[MAXN];
ll weight[MAXN];
int sz[MAXN];
int n, k;

void dfs1(int node, int parent) {
    sz[node] = 1;
    for (auto a : adj[node])
        if (a != parent) {
            children[node].push_back(a);
            dfs1(a, node);
            for (int i = min(sz[node] - 1, k); i >= 0; i --)
                for (int j = 1; j <= sz[a] && i + j <= k; j ++)
                    dp_down[node][i + j] = max(dp_down[node][i + j], dp_down[node][i] + dp_down_take[a][j]);
            sz[node] += sz[a];
        }
    for (int i = min(k, sz[node]); i > 0; i --)
        dp_down_take[node][i] = max(dp_down[node][i], dp_down[node][i - 1] + (ll)i * weight[node]);
}

void dfs2(int node) {
    int deg = children[node].size();
    if (deg == 1) {
        for (int i = 0; i <= k; i ++)
            dp_up[children[node][0]][i] = dp_up[node][i];
    } else if (deg >= 2) {
        int p = sz[children[node][0]];
        for (int i = 0; i <= k; i ++)
            pref_merge[0][i] = dp_down_take[children[node][0]][i],
            suff_merge[deg][i] = dp_up[node][i];
        for (int c = 1; c < deg; c ++) {
            for (int i = 0; i <= k; i ++)
                pref_merge[c][i] = 0;
            int child = children[node][c];
            p += sz[child];
            for (int i = min(k, p); i >= 0; i --)
                for (int j = min(i, sz[child]); j >= 0 && i - j <= p - sz[child]; j --)
                    pref_merge[c][i] = max(pref_merge[c][i], pref_merge[c - 1][i - j] + dp_down_take[child][j]);
        }
        for (int c = deg - 1; c >= 0; c --) {
            for (int i = 0; i <= k; i ++)
                suff_merge[c][i] = 0;
            int child = children[node][c];
            p -= sz[child];
            for (int i = k; i >= max(0, k - p - 1); i --)
                for (int j = min(i, sz[child]); j >= 0; j --)
                    suff_merge[c][i] = max(suff_merge[c][i], suff_merge[c + 1][i - j] + dp_down_take[child][j]);
            for (int i = k; i >= max(0, k - sz[child] - 1); i --)
                for (int j = min(i, p); j >= 0; j --)
                    dp_up[child][i] = max(dp_up[child][i], suff_merge[c + 1][i - j] + (c > 0 ? pref_merge[c - 1][j] : 0));
        }
    }
    for (auto a : children[node]) {
        for (int i = min(k, n - sz[a]); i >= 1; i --)
            dp_up[a][i] = max(dp_up[a][i], dp_up[a][i - 1] + (ll)i * weight[node]);
        dfs2(a);
    }
}

void solve() {
    cin >> n >> k;
    for (int i = 0; i < n; i ++) {
        for (int j = 0; j <= k; j ++)
            dp_down[i][j] = dp_down_take[i][j] = dp_up[i][j] = 0;
        adj[i].clear(); children[i].clear();
        cin >> weight[i];
    }
    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);
    }
    dfs1(0, -1);
    dfs2(0);
    for (int i = 0; i < n; i ++) {
        ll best = 0;
        for (int j = 0; j < min(k, sz[i]); j ++)
            best = max(best, dp_down[i][j] + dp_up[i][k - 1 - j] + (ll)k * weight[i]);
        cout << best << " ";
    }
    cout << endl;
}

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

    cin >> tt;

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

#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 = 4005;
int n, k;
int spare;
vector<int> adj[MAXN], children[2 * MAXN];
ll beauty[2 * MAXN];
int sz[2 * MAXN];
ll dp_down[2 * MAXN][MAXN], dp_down_take[2 * MAXN][MAXN];
ll dp_up[2 * MAXN][MAXN];
 
void merge(ll *target, ll *aa, ll *bb, int tsize, int asize, int bsize, int topmost) {
    for (int i = tsize; i > max(0, tsize - topmost); i --)
        for (int j = 0; j <= min(min(asize, bsize), i); j ++)
            target[i] = max(target[i], asize >= bsize ? aa[i - j] + bb[j] : bb[i - j] + aa[j]);
}
void finalise(ll *target, ll *source, ll b, int tsize) {
    for (int i = tsize; i > 0; i --)
        target[i] = max(source[i], source[i - 1] + (ll)i * b);
}
 
void dfs1(int node, int parent) {
    vector<int> cc;
    for (auto a : adj[node])
        if (a != parent) {
            dfs1(a, node);
            cc.push_back(a);
        }
    int cur = node;
    while (cc.size() > 2) {
        children[cur] = {cc.back(), spare};
        cc.pop_back();
        beauty[spare] = beauty[node];
        cur = spare ++;
    }
    children[cur] = cc;
}
 
void dfs2(int node) {
    sz[node] = (node < n);
    for (auto a : children[node]) {
        dfs2(a);
        sz[node] += sz[a];
    }
    if (children[node].size() == 1) {
        for (int i = 0; i <= k; i ++)
            dp_down[node][i] = dp_down_take[children[node][0]][i];
    } else if (children[node].size() == 2) {
        merge(dp_down[node], dp_down_take[children[node][0]], dp_down_take[children[node][1]], min(k, sz[node] - (node < n)), sz[children[node][0]], sz[children[node][1]], sz[node] - (node < n));
    }
    finalise(dp_down_take[node], dp_down[node], node < n ? beauty[node] : 0, min(k, sz[node]));
}
 
void dfs3(int node) {
    if (children[node].size() == 1) {
        finalise(dp_up[children[node][0]], dp_up[node], beauty[node], min(k, n - sz[children[node][0]]));
    } else if (children[node].size() == 2) {
        int aa = children[node][0], bb = children[node][1];
        merge(dp_up[aa], dp_up[node], dp_down_take[bb], min(n - sz[aa], k), min(n - sz[node], k), min(sz[bb], k), min(sz[aa] + 2, k));
        merge(dp_up[bb], dp_up[node], dp_down_take[aa], min(n - sz[bb], k), min(n - sz[node], k), min(sz[aa], k), min(sz[bb] + 2, k));
        if (aa < n)
            finalise(dp_up[aa], dp_up[aa], beauty[node], min(n - sz[aa], k));
        if (bb < n)
            finalise(dp_up[bb], dp_up[bb], beauty[node], min(n - sz[bb], k));
    }
    for (auto a : children[node])
        dfs3(a);
}
 
void solve() {
    cin >> n >> k;
    for (int i = 0; i < n; i ++)
        adj[i].clear(), children[i].clear();
    for (int i = n; i < 2 * n; i ++)
        children[i].clear();
    spare = n;
    for (int i = 0; i < n; i ++)
        cin >> beauty[i];
    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);
    }
    dfs1(0, -1);
    for (int i = 0; i < spare; i ++)
        for (int j = 0; j <= k; j ++)
            dp_down[i][j] = dp_up[i][j] = dp_down_take[i][j] = 0;
    dfs2(0);
    dfs3(0);
    for (int i = 0; i < n; i ++) {
        ll best = 0;
        for (int j = 0; j < min(k, sz[i]); j ++)
            best = max(best, dp_down[i][j] + dp_up[i][k - 1 - j] + (ll)k * beauty[i]);
        cout << best << " ";
    }
    cout << endl;
}
 
int main() {
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int tt = 1;
 
    cin >> tt;
 
    while (tt--) solve();
    return 0;
}

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;
}