When all the elements of the array are equal, the solution is trivially impossible since the $$$\gcd$$$ of any subset will always be equal to $$$a_1$$$.

That is infact the only $$$\texttt{No}$$$ case. We show a construction otherwise.

Let $$$\operatorname{mx} = \max(a)$$$. Put all the elements equal to $$$\operatorname{mx}$$$ in one set, and all the other elements in the other set. Then, the $$$\gcd$$$ of the first set is $$$\operatorname{mx}$$$ while the other set will have a strictly smaller $$$\gcd$$$ (because $$$\gcd(a, b) \le \min(a, b)$$$)

Time complexity is $$$O(n)$$$.

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

int main(){
    int t; cin >> t;
    
    while (t--){
        int n; cin >> n;
        vector <int> a(n);
        for (int i = 0; i < n; i++){
            cin >> a[i];
        }
        int mn = *min_element(a.begin(), a.end());
        int mx = *max_element(a.begin(), a.end());
        if (mn == mx){
            cout << "No\n";
            continue;
        }
        cout << "Yes\n";
        for (int i = 0; i < n; i++){
            cout << (1 + (a[i] == mx)) << " \n"[i + 1 == n];
        }
    }
    return 0;
}

Suppose $$$\max(a) - \min(a) \le k$$$ holds, and there is at least one $$$a_i \ge 1$$$. Then, infact it is possible to take one apple while still keeping the condition of $$$\max(a) - \min(a) \le k$$$.

Thus, for an array with $$$\max(a) - \min(a) \le k$$$, the only way for a player to lose is when all $$$a_i = 0$$$. But this happens exactly after the $$$\sum(a_i)$$$-th turn because each turn reduces $$$\sum(a_i)$$$ by $$$1$$$.

It may be possible that a first move itself is not possible. For example, in the case that $$$a = [4, 1], k = 1$$$. We should check that after subtracting the maximum element, the array has the property that $$$\max(a) - \min(a) \le k$$$ and immediately print $$$\texttt{Jerry}$$$ otherwise.

In the other case, we can simply print $$$\texttt{Tom}$$$ when $$$\sum(a_i)$$$ is odd, and $$$\texttt{Jerry}$$$ when $$$\sum(a_i)$$$ is even. This is because when $$$\sum (a_i)$$$ is odd, Tom will be the last person to make a move since he went first and the total number of turns is odd, and vice versa.

Time complexity is $$$O(n)$$$.

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

int main(){
    int t; cin >> t;
    
    while (t--){
        int n, k; cin >> n >> k;
        
        vector <int> a(n);
        for (auto &x : a) cin >> x;
        
        long long sum = accumulate(a.begin(), a.end(), 0LL);
        
        sort(a.begin(), a.end());
        a[n - 1]--;
        sort(a.begin(), a.end());
        
        if (a[n - 1] - a[0] > k || sum % 2 == 0){
            cout << "Jerry\n";
            continue;
        }
        cout << "Tom\n";
    }
    return 0;
}

We assume that there is at least one $$$s_i = 0$$$ (unfilled position). In the other case that all $$$s_i = 1$$$, we can easily check if the maximum subarray sum is $$$k$$$ or not.

Let us first figure out when the answer is impossible. Replace all $$$a_i = -\texttt{INF}$$$ such that $$$s_i = 0$$$. If the maximum subarray sum is still $$$ \gt k$$$, then the answer is clearly impossible.

In every other case, the answer is infact possible! All positions with $$$s_i = 0$$$ will be kept $$$-\texttt{INF}$$$ except for $$$1$$$. Choose that position arbitrarily, let's call it $$$pos$$$.

In both solutions, be careful to avoid overflow. One simple way is to have $$$\texttt{INF} = 10^{13}$$$, as that is sufficient for our purposes (prevents overflow, but still larger than $$$k + \sum{a_i}$$$).

Time complexity: $$$O(n)$$$ or $$$O(n \cdot \log(A))$$$.

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

int main(){
    int t; cin >> t;
    while (t--){
        int n; 
        long long k; 
        cin >> n >> k;
        string s; cin >> s;
        vector <long long> a(n);
        for (auto &x : a) cin >> x;
        
        int pos = -1;
        for (int i = 0; i < n; i++){
            if (s[i] == '0'){
                pos = i;
                a[i] = -1e13;
            }
        }
        
        long long mx = 0;
        long long curr = 0;
        for (int i = 0; i < n; i++){
            curr = max(curr + a[i], a[i]);
            mx = max(mx, curr);
        }
        if (mx > k || (mx != k && pos == -1)){
            cout << "No\n";
            continue;
        }
        if (pos != -1){
            mx = 0, curr = 0;
            long long L, R;
            
            for (int i = pos + 1; i < n; i++){
                curr += a[i];
                mx = max(mx, curr);
            }
            L = mx;
            mx = 0;
            curr = 0;
            for (int i = pos - 1; i >= 0; i--){
                curr += a[i];
                mx = max(mx, curr);
            }
            R = mx;
            
            a[pos] = k - L - R;
        }
        
        cout << "Yes\n";
        for (int i = 0; i < n; i++){
            cout << a[i] << " \n"[i + 1 == n];
        }
    }
    return 0;
}

Note that the problem has a simple $$$O(n^2)$$$ solution by greedily finding the largest diameter in the current forest (set of disjoint trees) at every step, tiebreaking by the lexicographic order of the endpoints, then removing the diameter and continuing this process while at least $$$1$$$ node remains.

Property $$$1$$$: $$$2$$$ diameters always share at least one node.

Property $$$2$$$ : Let $$$(u, v)$$$ denote a diameter path, and $$$T$$$ denote the tree. Then $$$\operatorname{diam}(T \setminus (u, v)) \lt \operatorname{diam}(T)$$$ (strictly smaller).

Property $$$3$$$ : In any sequence of positive numbers such that $$$a_1 + a_2 + \ldots + a_k \le n$$$ such that $$$a_i \lt a_j$$$ for all $$$1 \le i \lt j \le k$$$, $$$k$$$ is at most $$$O(\sqrt{n})$$$.

With these $$$3$$$ properties, we can now solve the problem. We describe the algorithm below:

• Maintain a collection of subtrees (of nodes which have apples). Initially, the whole tree is there as one component.

• For every subtree, find it's lexicographically largest triplet of $$$(d, u, v)$$$ using a BFS/DFS.

• Remove the nodes on the diameter path for each subtree. This divides the component into several smaller subtrees. Add them to our collection.

• Repeat steps $$$2$$$ and $$$3$$$ while our collection is non-empty.

• Finally, sort (in descending order) the list of $$$(d, u, v)$$$ collected throughout all the steps, and output.

It is not hard to see that the above approach produces the correct answer. And it runs in $$$O(n \cdot \sqrt{n})$$$ time because steps $$$2$$$ and $$$3$$$ are repeated only $$$O(\sqrt{n})$$$ times.

There are several correct ways to implement Step $$$2$$$. One of the neatest way is as follows: Find the furthest node from $$$1$$$, tie breaking lexicographically, say we got $$$x$$$. Find the furthest node from $$$x$$$, again tie breaking lexicopgraphically, say we got $$$y$$$. Then $$$(\max(x, y), \min(x, y))$$$ is the required diameter. To prove that these $$$2$$$ traversals are enough, you can use the fact mentioned in proof of property $$$1$$$, i.e. diameters share a central node or an edge (depending on parity). To find the furthest node, we can use BFS or DFS both fairly easily.

For step $$$3$$$, we can keep recursing to the parent of $$$y$$$ till we reach $$$x$$$, assuming we have calculated the parents of all vertices with a dfs from $$$x$$$. You may refer to the code.

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

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

int main()
{
    int t; cin >> t;
    while (t--){
        int n; cin >> n;
        
        vector<vector<int>> adj(n + 1);
        for (int i = 1; i < n; i++){
            int u, v; cin >> u >> v;
            
            adj[u].push_back(v);
            adj[v].push_back(u);
        }
        
        vector <bool> used(n + 1, false), seen(n + 1, false);
        vector <array<int, 3>> ans;
        vector <int> p(n + 1, -1);
        
        while (true){
            if (count(used.begin() + 1, used.end(), false) == 0){
                break;
            }
            seen.assign(n + 1, false);
            
            auto dfs = [&](auto self, int u, int par) -> pair<int, int>{
                pair <int, int> ans = {1, u};
                p[u] = par;
                seen[u] = true;
                
                for (int v : adj[u]){
                    if (v != par && !used[v]){
                        auto pi = self(self, v, u);
                        pi.first += 1;
                        ans = max(ans, pi);
                    }
                }
                
                return ans;
            };
            
            for (int i = 1; i <= n; i++) if (!used[i] && !seen[i]){
                auto [d1, j] = dfs(dfs, i, -1);
                auto [d2, k] = dfs(dfs, j, -1);
                ans.push_back({d2, max(j, k), min(j, k)});
                
                while (k != -1){
                    used[k] = true;
                    k = p[k];
                }
            }
        }
        
        sort(ans.begin(), ans.end(), greater<array<int, 3>>());
        for (auto [x, y, z] : ans){
            cout << x << " " << y << " " << z << " ";
        }
        cout << '\n';
    }
    return 0;
}

Solve the problem in $$$O(n \cdot \log(n))$$$.

#include<bits/stdc++.h>
#ifdef DEBUG_LOCAL
#include <mydebug/debug.h>
#endif
using ll = long long;
const int N = 5e5+5;
using namespace std;
using pi = pair<int,int>;
using ti = tuple<int,int,int,int>;
int T,n,u,v,del[N],fa[N],ct;  vector<int> g[N]; set<pi> t[N];
void dfs(int u,int f){
    t[u].emplace(0,u),fa[u] = f;
    for(int v : g[u]) if(v != f){
        dfs(v,u); auto [x,y] = *--t[v].end();
        t[u].emplace(x+1,y);
    }
}ti gt(int u){
    assert(t[u].size() >= 1);
    if(t[u].size() == 1) return {0,u,u,u};
    auto [x,y] = *--t[u].end();
    auto [p,q] = *--(--t[u].end());
    return {x + p,max(y,q),min(y,q),u};
}void los(){
    cin >> n;
    for(int i = 1;i <= n;i ++) g[i].clear(),del[i] = 0,t[i].clear();
    for(int i = 1;i < n;i ++) cin >> u >> v,g[u].push_back(v),g[v].push_back(u);
    ct = 0,dfs(1,0); priority_queue<ti> q;
    for(int i = 1;i <= n;i ++) q.emplace(gt(i));
    while(q.size()){
        auto [di,u,v,d] = q.top(); q.pop();
        if(del[d] || ti{di,u,v,d} != gt(d)) continue;
        cout << di + 1 << " " << u << " " << v << " ";
        while(u != d) del[u] = 1,u = fa[u];
        while(v != d) del[v] = 1,v = fa[v];
        del[d] = 1; 
        auto [x,y] = *--t[d].end();
        while(fa[d] && !del[fa[d]]){
            d = fa[d];
            if(t[d].count({++x,y})) t[d].erase({x,y});
            q.emplace(gt(d));
            if(fa[d]){
                auto [a,b] = *--t[d].end();
                t[fa[d]].emplace(a+1,b);
            }
        }
    }cout << "\n";
}int main(){
    ios::sync_with_stdio(0),cin.tie(0);
    for(cin >> T;T --;) los();
}

Compute provably the exact worst case, and construct a tree that obtains it.

Let $$$C(n, k)$$$ denote $$$\frac{n!}{k! \cdot (n - k)!}$$$.

We first start from the maximum possible value of $$$k$$$, and the tree that achieves it, i.e. a straight line path rooted at $$$1$$$. It is not too hard to see that this tree has the largest weight, and the weight of this tree is $$$C(n, 3)$$$. Thus, for $$$k \gt C(n, 3) + 1$$$, we answer $$$\texttt{No}$$$. We can prove the largest weight point by proving each node should have exactly $$$1$$$ child. Suppose instead some node $$$u$$$ has $$$\ge 2$$$ children, $$$c_1$$$ and $$$c_2$$$, but then if we attached $$$c_1$$$ to $$$c_2$$$ and broke the $$$c_1$$$ and $$$u$$$ edge, it increases the weight.

Now, infact the answer is possible for all $$$0 \le k \le C(n, 3) + 1$$$. We try to modify the line graph to give a valid construction. First of all, replace $$$k$$$ with $$$C(n, 3) - k$$$ and view the problem as reducing the weight of the line graph instead.

Suppose we broke the edge $$$(n - 1) - n$$$ and added the edge $$$x - n$$$, then the weight decreases by $$$C(n - x, 2)$$$. This is because the depth of LCA with nodes $$$n - 1$$$, $$$n - 2, \ldots, x$$$ change and they decrease by $$$n - x - 1, n - x - 2, \ldots 1$$$ respectively. Suppose, after this step, we further broke the edge $$$(n - 2) - (n - 1)$$$, and added the edge $$$y - (n - 1)$$$. It is tempting to say that the weight again decreases by $$$C(n - 1 - y, 2)$$$ but this is only true when $$$y \ge x$$$.

If we generalize the above, and break the edges $$$(i - 1) - i$$$ and add the edge $$$a_i - i$$$ ($$$a_i \lt i$$$), then the weight will decrease by $$$C(i - a_i, 2)$$$ as long as the sequence $$$a$$$ is decreasing (or $$$a_i = i - 1$$$, i.e. we do not change the parent). Because $$$a$$$ must be decreasing, that means that $$$i - a_i$$$ can only contain distinct elements (or $$$i - a_i = 1$$$).

This reduces the problem to Find sum of distinct elements of $$$C(i, 2)$$$ ($$$0 \le i \le n - 1$$$)at most $$$1$$$ from k.

Infact the greedy algorithm solves this problem, i.e. take the largest (untaken) value of $$$C(i, 2) \le k$$$ at each step.

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

int main(){
    int t; cin >> t;
    while (t--){
        int n; cin >> n;
        long long k; cin >> k;
        
        long long mx = 1LL * n * (n - 1) * (n - 2) / 6;
        if (k > mx + 1){
            cout << "No\n";
            continue;
        }
        cout << "Yes\n";
        k = mx - min(k, mx);
        
        int p = n - 1;
        for (int i = n; i >= 2; i--){
            while (1LL * p * (p - 1) / 2 > k){
                p--;
            }
            k -= 1LL * p * (p - 1) / 2;
            
            cout << (i - p) << " " << i << "\n";
            if (p != 1) p--;
        }
    }
    return 0;
}

Let us try to figure out the optimal strategy. We want to use small values for the "overtake" operation, and we will use "swap" operations to make the overtakes less costly.

Suppose $$$p = $$$ first position of minima element. We should over take cyclists $$$1, 2, \ldots, p$$$ for the cost of $$$a_p$$$, swapping $$$p$$$ till first. This is because all $$$a_i (1 \le i \lt p)$$$ is $$$\ge a_p + 1$$$, and so the swap + overtake can't be worse. And obviously, if we are using $$$a_q (q \gt p)$$$, it is less costly in terms of swaps to use $$$p$$$ since the overtake cost cannot be worse.

Now, we might use the value $$$a_p$$$ for overtakes in the suffix as well, i.e. there exists some $$$q \ge p$$$ such that we overtake cyclists $$$1, 2, \ldots, q$$$ using $$$a_p$$$. This reduces the problem to the subproblem $$$a[q + 1, n]$$$, and thus we can use Dynamic Programming! But why are the problems independent in $$$a[q + 1, n]$$$ and the rest of the array? Suppose that we took some $$$a_i (i \le q)$$$ to be used for swaps in the suffix $$$a[q + 1, n]$$$, but we could then instead set up the swaps such that first $$$p$$$ reaches $$$q$$$, and then $$$p$$$ is taken for these suffix swaps. This won't add any additional swaps, and may only reduce the cost.

Let $$$dp_i$$$ be the answer for the suffix $$$a[i, n]$$$. Then, we compute $$$p = $$$ position of minima in $$$a[i, n]$$$, iterate on partition index $$$j$$$ such that we will take $$$p$$$ to $$$j$$$ using it for swaps $$$1, 2 \ldots, j$$$, value computed as $$$dp_{j + 1} + a_p \cdot (j - i) + S$$$, where $$$S$$$ denotes the total swaps made ($$$S = 2 \cdot (j - p) + (p - i - 1)$$$).

This solves the problem in $$$O(n^2)$$$.

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

int main(){
    int t; cin >> t;
    while (t--){
        int n; cin >> n;
        
        vector <int> a(n + 1);
        for (int i = 1; i <= n; i++){
            cin >> a[i];
        }
        
        vector <long long> dp(n + 1, 1e18);
        dp[n] = 0;
        
        for (int i = n - 1; i >= 0; i--){
            int p = i + 1;
            for (int j = i + 1; j <= n; j++) if (a[j] < a[p]){
                p = j;
            }
            
            for (int j = p; j <= n; j++){
                dp[i] = min(dp[i], dp[j] + 2 * (j - p) + 1LL * (j - i) * a[p] + (p - i - 1));
            }
        }
        
        cout << dp[0] << "\n";
    }
    return 0;
}

Read the editorial for F1 first. We considered the positions that we would take $$$p$$$ to, which we assumed was $$$q$$$ and iterated $$$q = p, p + 1, \ldots, n$$$, finding the cost for each.

Property : Optimal $$$q$$$ is only $$$q = p$$$ or $$$q = n$$$.

Now, let $$$p_1$$$ be the first minima in $$$a[1, n]$$$, then $$$p_2$$$ be the first minima in $$$a[p_1 + 1, n]$$$, $$$p_3$$$ be the first minima in $$$a[p_2 + 1, n]$$$, and so on. Let $$$q_i = $$$ where $$$p_i$$$ is taken to for each $$$i$$$. Due to the above property, we can see that the optimal strategy is : for some $$$x$$$, $$$q_x = n$$$ and $$$q_i = p_i$$$ for $$$i \lt x$$$, i.e. choose to take some index $$$p_x$$$ to $$$n$$$, and the previous indices do not move.

We get a $$$O(n)$$$ solution for a single array by trying all values of $$$x$$$. But, we need to answer prefix queries.

Note that each option of $$$x$$$ gives a linear equation in the length of the array. And appending an element to the end of the array adds at most $$$1$$$ extra option for $$$x$$$. We can maintain all the linear equations in a CHT/Lichao tree and find the minimum each time.

It can be proven that only $$$min(a) \le a_i \le min(a) + 20$$$ need to be considered, and we will never overtake using a larger value. This property gives us simpler solutions in $$$O(n \cdot 20)$$$ with $$$0$$$ data structures.

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF (int)1e18

#define inf 1e18
#define ld long double

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

 
struct chtDynamicMin {  
	struct line {
		int m, b; ld x; 
		int om, ob;
		int val; bool isQuery; 
		line(int _m = 0, int _b = 0, int _om = 0, int _ob = 0) {
			m = _m;
			b = _b;
			om = _om;
			ob = _ob;
			val = 0;
			x = -inf;
			isQuery = false;
		}
			
		
		int eval(int x) const { return m * x + b;	}
		bool parallel(const line &l) const { return m == l.m; }
		ld intersect(const line &l) const {
			return parallel(l) ? inf : 1.0 * (l.b - b) / (m - l.m);
		}
		bool operator < (const line &l) const {
			if(l.isQuery) return x < l.val;
			else return m < l.m; 
		}
	};
 
	set<line> hull; 
	typedef set<line> :: iterator iter; 
 
	bool cPrev(iter it) { return it != hull.begin(); }
	bool cNext(iter it) { return it != hull.end() && next(it) != hull.end(); }
 
	bool bad(const line &l1, const line &l2, const line &l3) {
		return l1.intersect(l3) <= l1.intersect(l2); 
	}
	bool bad(iter it) {
		return cPrev(it) && cNext(it) && bad(*prev(it), *it, *next(it));
	}
 
	iter update(iter it) {
		if(!cPrev(it)) return it; 
		ld x = it -> intersect(*prev(it));
		line tmp(*it); tmp.x = x;
		it = hull.erase(it); 
		return hull.insert(it, tmp);
	}
    
	void addLine(int m, int b) { 
		int om = m, ob = b;
		m *= -1;
		b *= -1;
		line l(m, b, om, ob); 
		iter it = hull.lower_bound(l); 
		if(it != hull.end() && l.parallel(*it)) {
			if(it -> b < b) it = hull.erase(it); 
			else return;
		}
 
		it = hull.insert(it, l); 
		if(bad(it)) return (void) hull.erase(it);
 
		while(cPrev(it) && bad(prev(it))) hull.erase(prev(it));
		while(cNext(it) && bad(next(it))) hull.erase(next(it));
 
		it = update(it);
		if(cPrev(it)) update(prev(it));
		if(cNext(it)) update(next(it));
	}
 
	int query(int x) const { 
		if(hull.empty()) return inf;
		line q; q.val = x, q.isQuery = 1;
		iter it = --hull.lower_bound(q);
		return - it -> eval(x);
	}
};

void Solve() 
{
    int n; cin >> n;
    
    // insert lines and calculate CHT 
    chtDynamicMin cht;
    
    vector <int> a(n + 1);
    for (int i = 1; i <= n; i++){
        cin >> a[i];
    }
    
    vector <int> pv(n + 1, 0);
    // previous smaller 
    stack <pair<int, int>> st;
    for (int i = n; i >= 1; i--){
        while (!st.empty() && st.top().first >= a[i]){
            pv[st.top().second] = i;
            st.pop();
        }
        
        st.push({a[i], i});
    }
    
    vector <int> dp(n + 1, 0);
    
    for (int i = 1; i <= n; i++){
        dp[i] = dp[pv[i]] + a[i] * (i - pv[i]) + (i - pv[i] - 1);
        // slope is +2 + a[i] 
        // constant - slope * i  
        int m = 2 + a[i];
        int c = dp[i] - m * i;
        cht.addLine(m, c);
        
        int ans = cht.query(i);
        cout << ans << " \n"[i == n];
    }
}

int32_t main() 
{
    auto begin = std::chrono::high_resolution_clock::now();
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
    // freopen("in",  "r", stdin);
    // freopen("out", "w", stdout);
    
    cin >> t;
    for(int i = 1; i <= t; i++) 
    {
        //cout << "Case #" << i << ": ";
        Solve();
    }
    auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
    return 0;
}