Hope you enjoyed the round!
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$$$.
We will subtract from the maximum element. Then $$$\min(a)$$$ does not change except when $$$a_1 = a_2 = \ldots = a_n$$$. In that special case, you can check that the move is valid as $$$\max(a) - \min(a)$$$ becomes $$$1$$$.
In any other case, $$$\max(a)$$$ reduces by $$$0$$$ or $$$1$$$, so $$$\max(a) - min(a)$$$ only decreases, and thus $$$\max(a) - \min(a) \le k$$$ clearly holds.
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$$$.
Let $$$b =$$$ max prefix sum in the subarray $$$[a_{pos + 1}, a_{pos + 2}, \ldots, a_n]$$$. Let $$$c =$$$ max suffix sum in the subarray $$$[a_1, a_2, \ldots, a_{pos - 1}]$$$. Here we will allow the empty prefix and suffix too.
Suppose the value of $$$a_{pos} = x$$$. Then, the maximum subarray sum including $$$pos$$$ will be $$$x + b + c$$$.
And the maximum subarray not including $$$pos$$$ will be $$$\le k$$$, because thats equivalent to replacing $$$a_{pos}$$$ with $$$-\texttt{INF}$$$.
Thus, we can simply replace $$$x$$$ with $$$k - b - c$$$ and it will satisfy the conditions.
Let $$$f(x)$$$ be defined as the maximum subarray sum when we replace $$$a_{pos}$$$ with $$$x$$$.
Note the following properties of $$$f(x)$$$:
$$$f(-\texttt{INF}) \le k$$$: Because this is the assumption for the non-impossible case.
$$$f(k) \ge k$$$: Because the subarray $$$[a_{pos}]$$$ itself has a sum of $$$k$$$, so the maximum subarray sum must be greater.
$$$f(x + 1) \ge f(x)$$$ : Because increasing an element cannot reduce the maximum subarray sum.
$$$f(x + 1) \le f(x) + 1$$$: Because by increasing $$$a_{pos}$$$, each subarray increases by $$$0$$$ or $$$1$$$ depending on whether it includes $$$pos$$$. Thus, there is no way for the function calculating maximum subarray sum to increase by more than $$$1$$$.
With these observations, we can infact binary search on the first $$$x$$$ such that $$$f(x) = k$$$.
This is because, $$$f$$$ becomes continuous on the set of integers by the third and fourth property, and hence it will take all values in the range $$$[f(a), f(b)]$$$ for $$$a \le b$$$, and we have shown that $$$k \in [f(-\texttt{INF}), f(k)]$$$ by the first and second property.
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.
With some background theory about diameters, this becomes trivial as when diameter length (in terms of nodes) is odd, they share a common central node; and when even, they share an edge (which shares $$$2$$$ nodes). Nevertheless, we provide an elementary proof.
Let $$$a_1, a_2, \ldots a_d$$$ and $$$b_1, b_2, \ldots b_d$$$ be $$$2$$$ distinct diameters that do not share any node.
Consider the closest pair of $$$2$$$ points in these $$$2$$$ paths, say $$$a_i$$$ and $$$b_j$$$ are closest. Then, the path $$$(a_i, b_j)$$$ cannot contain any other $$$a_k$$$ or any other $$$b_k$$$ because otherwise it would be a contradiction to the fact that they are closest.
Now, the length of the path $$$(a_1, b_1)$$$ is $$$(i - 1) + \operatorname{dist}(a_i, b_j) + (j - 1)$$$, where $$$\operatorname{dist}(x, y)$$$ denotes the number of nodes on the path $$$(x, y)$$$.
Assume that $$$i, j \ge \frac{d + 1}{2}$$$, then $$$\operatorname{dist}(a_1, b_1)$$$ is strictly larger than $$$d$$$ (using $$$\operatorname{dist}(a_i, b_j) \ge 2$$$), contradicting that $$$d$$$ is the diameter. In the other cases of $$$i, j$$$ being smaller than $$$\frac{d + 1}{2}$$$, we can check the pairs $$$(a_1, b_d), (a_d, b_1)$$$ and $$$(a_d, b_d)$$$. It is easy to see at least one of them will be larger than $$$d$$$.
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).
This comes directly from the previous property. Since all diameters share at least one node, the new forest generated after removing path $$$(u, v)$$$ will have a strictly smaller diameter.
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})$$$.
This is a classical property.
Note that $$$a_i \ge i$$$ for all $$$1 \le i \le k$$$ by induction. And thus, $$$a_1 + a_2 + \ldots + a_k \ge 1 + 2 + \ldots + k = \dfrac{k \cdot (k + 1)}{2}$$$.
But, $$$a_1 + a_2 + \ldots + a_k \le n$$$ implies $$$\dfrac{k \cdot (k + 1)}{2} \le n$$$, and so $$$k \le 2 \cdot \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.
Every smaller tree is formed from a larger "parent" tree. The diameter of the smaller tree is smaller than the diameter of the larger tree using Property $$$2$$$.
Suppose that there is some tree that is formed at $$$k$$$-th step. Then, consider the sequence of parent trees of this tree, and their diameters. Their diameters form a strictly increasing sequence, but their sum must be bounded by $$$n$$$ since we remove that many nodes, and total removed nodes is $$$n$$$. Thus, using Property $$$3$$$, we get $$$k \le \sqrt{2 \cdot n}$$$.
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))$$$.
Let $$$f_i,g_i$$$ be the longest and second longest path from $$$i$$$ in $$$i$$$'s subtree, the diameter will be $$$\max \limits_{i=1}^n {f_i+g_i}$$$.
When we find a diameter $$$(u,v)$$$, let update $$$f_u,g_u$$$ for all $$$u$$$ on the path $$$(\operatorname{lca}(u,v),\text{root})$$$. Note that the path $$$(\operatorname{lca}(u,v),\text{root})$$$ will be always shorter than the diameter, so the total update times will be $$$\mathcal O(n)$$$.
Use a std::set to find $$$f_u,g_u$$$ for every node $$$u$$$ and a std::priority_queue to maintain the maximum $$$f_i + g_i$$$, the total complexity is $$$\mathcal O(n \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.
It can be proven that diameter decreases by $$$2$$$ each iteration and not just $$$1$$$, and it is possible to obtain this as we show later. So the best bound is $$$d$$$ where $$$1 + 3 + 5 + \ldots + (2 \cdot d - 1) \le n$$$, which comes out to be $$$\sqrt{n}$$$.
Let $$$L = \sqrt{n}$$$. Make $$$P_1, P_2, \ldots, P_L$$$ where $$$P_i$$$ is a line graph of size $$$2 \cdot i - 1$$$. Now, connect the central nodes of $$$P_i$$$ and $$$P_{i - 1}$$$ for all $$$i$$$. Refer to Wuhudsm comment for a picture.
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.
We prove by induction. For $$$n \le 5$$$, it can be verified through bruteforce for all cases.
For $$$n \ge 6$$$, if $$$k$$$ is $$$\le C(n - 1, 3)$$$, just set $$$n = n - 1$$$ and by induction it is solvable. If $$$C(n - 1, 3) \lt k \le C(n, 3)$$$, then we set $$$k = k - C(n - 1, 2)$$$ and use induction. It can be verified that $$$0 \le k \le C(n - 1, 3)$$$ after this modification and so it is valid.
#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;
}
2107F1 - Cycling (Easy Version)
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;
}
2107F2 - Cycling (Hard Version)
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$$$.
Suppose $$$q \ne p$$$, i.e. we use $$$a_p$$$ for overtaking $$$p + 1$$$, and we used $$$a_i$$$ for overtaking $$$q + 1$$$. Then, if $$$a_p + 2 \le a_i$$$, it is not less optimal to overtake $$$q + 1$$$ using $$$a_p$$$ as well, and if $$$a_i \le a_p + 1$$$, it is not less optimal to overtake $$$q$$$ using $$$a_i$$$.
Thus, $$$q$$$ is only ever the "edges" of the ranges , i.e. $$$p$$$ or $$$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.
Assume $$$min(a) = 1$$$. Let $$$L_i$$$ denote the number of overtakes using the value $$$i$$$, and we use values $$$1, 2 \ldots, k$$$. Then, it is easy to see the indices $$$1, 2, \ldots, L_1$$$ will be overtaken with $$$1$$$, after that $$$L_1 + 1, L_1 + 2, \ldots, L_2$$$ will be overtaken with $$$2$$$ and so on.
It should not be more optimal to take the value $$$i$$$ to cover the entire suffix, and so this gives us additional constraints of the form (by calculating the difference of costs in the current way, and the modified way) $$$2 \cdot (L_{i + 1} + L_{i + 2} + \ldots + L_k) \gt L_{i + 1} \cdot 1 + L_{i + 2} \cdot 2 + L_{i + 3} \cdot 3 + \ldots$$$. This simplies to $$$L_{i + 1} \ge L_{i + 3} + 2 \cdot L_{i + 4} + \ldots$$$.
Because of $$$L_{i + 1} \ge 2 \cdot L_{i + 4}$$$, we get a bound of $$$3 \cdot log_2(n)$$$, but the exact bound can be computed by a greedy approach.
#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;
}
