The boss's shield permanently activates and blocks all subsequent damage only when two cards of the exact same value are played back-to-back. Importantly, the card that actually triggers the shield still deals its normal damage.

This means we want to play as many cards as possible before being forced to place two identical cards adjacent to each other. We should only do this on the very last card we play.

Let the most frequent card in our hand have a damage value of $$$X$$$, and let its frequency be $$$F$$$. Let the number of all other cards be $$$O = n - F$$$.

To maximize the number of $$$X$$$ cards we can play, we must use the $$$O$$$ "other" cards as separators. By placing an "other" card between every $$$X$$$ card, we can form an alternating sequence like this:

This allows us to safely play $$$O + 1$$$ copies of $$$X$$$ without triggering the shield.

Finally, to squeeze out the maximum possible damage, we can play exactly one more $$$X$$$ card at the very end of this sequence:

This final $$$X$$$ triggers the shield, but it still deals its normal damage. All remaining cards in our hand will deal $$$0$$$, but that doesn't matter because we have already used all of our "other" cards.

Thus, the maximum number of $$$X$$$ cards we can successfully play is $$$(O + 1) + 1 = O + 2$$$. Of course, if $$$F \lt O + 2$$$, we simply play all $$$F$$$ of our $$$X$$$ cards without any issues.

The maximum number of majority cards we can play is $$$\min(F, O + 2)$$$. Since we always play every single "other" card, the maximum total damage is:

Time complexity: $$$\mathcal{O}(n)$$$.

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
 
using namespace std;
 
void solve() {
    int n;
    cin >> n;
    long long total_sum = 0;
    map<int, int> freq;
    
    int max_f = 0;
    int maj_val = 0;
    
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        total_sum += x;
        freq[x]++;
        if (freq[x] > max_f) {
            max_f = freq[x];
            maj_val = x;
        }
    }
    
    int others = n - max_f;
    
    int max_majority_played = min(max_f, others + 2);
    
    long long ans = (total_sum - 1LL * max_f * maj_val) + 1LL * max_majority_played * maj_val;
    cout << ans << "\n";
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t; cin >> t;
    while(t--) {
        solve();
    }
    return 0;
}

Let $$$n_0$$$ and $$$n_1$$$ be the number of 0s and 1s in the initial string. Let $$$k_0$$$ and $$$k_1$$$ be the number of 0s and 1s in the final alternating string. Let $$$c_0$$$ and $$$c_1$$$ be the number of 0s and 1s we deleted.

Because our deletions must strictly alternate, the difference between the number of deleted 0s and 1s can be at most $$$1$$$. Thus, $$$|c_0 - c_1| \le 1$$$. We know that $$$c_0 = n_0 - k_0$$$ and $$$c_1 = n_1 - k_1$$$.

Let $$$\Delta n = n_0 - n_1$$$ and $$$\Delta k = k_0 - k_1$$$. Substituting our equations, the condition $$$|c_0 - c_1| \le 1$$$ translates to:

Since the final string is strictly alternating, $$$\Delta k$$$ can only be $$$-1$$$, $$$0$$$, or $$$1$$$. This means that if $$$|\Delta n| \gt 2$$$, it is mathematically impossible to satisfy the inequality, and we should output $$$-1$$$.

If it is possible ($$$|\Delta n| \le 2$$$), we want to maximize the length of our final string (which minimizes deletions). We can first greedily "compress" the initial string by removing all adjacent duplicate characters (e.g., 00011001 becomes 0101). Let the length of this compressed alternating string be $$$L$$$, and let $$$\Delta L$$$ be the difference between the number of 0s and 1s in it.

To ensure our sequence of deletions is valid, we must satisfy the condition $$$|\Delta n - \Delta k| \le 1$$$, meaning our final $$$\Delta k$$$ must be in the range $$$[\Delta n - 1, \Delta n + 1]$$$. We can safely remove any number of characters from the beginning or the end of our compressed alternating string, and it will remain alternating. Each character we remove shifts $$$\Delta L$$$ by exactly $$$+1$$$ or $$$-1$$$.

Thus, to fix the parity and enter the valid range, the minimum number of characters we must drop from the ends of our compressed string is exactly the mathematical distance from $$$\Delta L$$$ to the range $$$[\Delta n - 1, \Delta n + 1]$$$. This distance is exactly $$$\max(0, |\Delta n - \Delta L| - 1)$$$.

The total number of deleted characters is the number of characters removed during compression $$$(n - L)$$$, plus the characters removed from the ends to fix the parity. Final answer: $$$(n - L) + \max(0, |\Delta n - \Delta L| - 1)$$$.

Time complexity: $$$\mathcal{O}(n)$$$.

#include <iostream>
#include <string>
#include <cmath>
#include <algorithm>
 
using namespace std;
 
void solve() {
    int n; cin >> n;
    string s; cin >> s;
 
    int n0 = 0, n1 = 0;
    for (char c : s) {
        if (c == '0') n0++;
        else n1++;
    }
 
    int delta_n = n0 - n1;
    if (abs(delta_n) > 2) {
        cout << -1 << "\n";
        return;
    }
 
    int L = 1;
    int L0 = (s[0] == '0' ? 1 : 0);
    int L1 = (s[0] == '1' ? 1 : 0);
 
    for (int i = 1; i < n; i++) {
        if (s[i] != s[i - 1]) {
            L++;
            if (s[i] == '0') L0++;
            else L1++;
        }
    }
 
    int delta_L = L0 - L1;
    int ans = (n - L) + max(0, abs(delta_n - delta_L) - 1);
    cout << ans << "\n";
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int t; cin >> t;
    while(t--) {
        solve();
    }
    
    return 0;
}

The tower collapses if all $$$m$$$ pieces of any single level are removed. This guarantees that the answer is at most $$$m$$$.

Let's write the condition to collapse a specific row $$$k$$$ via damage. The sum of destabilization factors of the removed pieces from rows $$$i \ge k$$$ must satisfy:

To satisfy this inequality using the minimum number of pieces, we must greedily select pieces with the largest $$$a_{i,j}$$$ from rows at and below $$$k$$$.

Since the answer will never exceed $$$m$$$, we only need to keep track of at most $$$m$$$ pieces at any time. We can process the grid from the bottom row ($$$n$$$) to the top row ($$$1$$$), maintaining a priority queue or sorted list of the largest $$$m$$$ destabilization factors $$$a_{i,j}$$$ seen so far.

At each row $$$k$$$, we insert its $$$m$$$ pieces into our active pool, discard all but the largest $$$m$$$ elements overall, and find the minimum number of largest elements that sum to at least $$$v_k$$$. The minimum number of pieces required across all rows $$$k$$$, bounded by $$$m$$$, is our answer.

Time complexity: $$$\mathcal{O}(n \cdot m \log m)$$$

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
void solve() {
    int n, m;
    cin >> n >> m;
    vector<long long> v(n + 1);
    for(int i = 1; i <= n; i++) cin >> v[i];
    
    vector<vector<long long>> a(n + 1, vector<long long>(m));
    for(int i = 1; i <= n; i++) {
        for(int j = 0; j < m; j++) {
            cin >> a[i][j];
        }
    }
    
    int min_ans = m; 
    vector<long long> best;
    
    for(int k = n; k >= 1; k--) {
        for(int j = 0; j < m; j++) {
            best.push_back(a[k][j]);
        }
        
        sort(best.rbegin(), best.rend());
        
        if ((int)best.size() > m) {
            best.resize(m);
        }
        
        long long current_sum = 0;
        int pieces = 0;
        
        for(long long val : best) {
            current_sum += val;
            pieces++;
            if (current_sum >= v[k]) {
                min_ans = min(min_ans, pieces);
                break;
            }
        }
    }
    
    cout << min_ans << "\n";
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t; cin >> t;
    while(t--) {
        solve();
    }
    return 0;
}

Let's consider the difference array $$$d$$$, where $$$d_i = a_{i+1} - a_i$$$ for all $$$1 \le i \lt n$$$.

Consider what happens to the array $$$a$$$ when we perform an operation on index $$$i$$$. The triplet $$$(a_{i-1}, a_i, a_{i+1})$$$ becomes $$$(a_{i-1}, a_{i-1} - a_i + a_{i+1}, a_{i+1})$$$. Let's see how this affects our difference array $$$d$$$:

• The new $$$d_{i-1}$$$ becomes $$$(a_{i-1} - a_i + a_{i+1}) - a_{i-1} = a_{i+1} - a_i$$$, which is exactly the old $$$d_i$$$.
• The new $$$d_i$$$ becomes $$$a_{i+1} - (a_{i-1} - a_i + a_{i+1}) = a_i - a_{i-1}$$$, which is exactly the old $$$d_{i-1}$$$.

Thus, performing the operation on index $$$i$$$ is exactly equivalent to swapping $$$d_{i-1}$$$ and $$$d_i$$$!

However, we can only perform this operation if $$$a_{i-1}$$$ and $$$a_{i+1}$$$ have the same parity. Notice that $$$a_{i+1} - a_{i-1} = (a_{i+1} - a_i) + (a_i - a_{i-1}) = d_i + d_{i-1}$$$. For $$$a_{i-1}$$$ and $$$a_{i+1}$$$ to have the same parity, their difference $$$d_i + d_{i-1}$$$ must be an even number. The sum of two integers is even if and only if they have the same parity.

Therefore, the condition that $$$a_{i-1}$$$ and $$$a_{i+1}$$$ have the same parity is equivalent to saying $$$d_{i-1}$$$ and $$$d_i$$$ have the same parity.

This means we can swap any two adjacent elements in the difference array $$$d$$$ as long as they share the same parity. This allows us to independently sort any contiguous subsegment of $$$d$$$ that consists entirely of even numbers, or entirely of odd numbers.

To construct the lexicographically smallest array $$$a$$$, we simply group contiguous elements of $$$d$$$ that share the same parity, sort each group in non-decreasing order, and then reconstruct the array $$$a$$$ starting from $$$a_1$$$.

Time complexity: $$$\mathcal{O}(n \log n)$$$.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
 
using namespace std;
 
void solve() {
    int n;
    cin >> n;
    vector<long long> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    
    vector<long long> d(n - 1);
    for (int i = 0; i < n - 1; i++) {
        d[i] = a[i + 1] - a[i];
    }
    
    for (int i = 0; i < n - 1; ) {
        int j = i;
        while (j < n - 1 && (d[j] & 1) == (d[i] & 1)) {
            j++;
        }
        sort(d.begin() + i, d.begin() + j);
        i = j;
    }
    
    cout << a[0] << " ";
    long long cur = a[0];
    for (int i = 0; i < n - 1; i++) {
        cur += d[i];
        cout << cur << " ";
    }
    cout << "\n";
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t; cin >> t;
    while(t--) {
        solve();
    }
    return 0;
}

From the arithmetic progression condition,

From the XOR condition,

Substituting the second equation into the first gives

Let $$$x$$$ be the bitwise AND of $$$a$$$ and $$$c$$$, i.e. x = a&c. Recall the standard bitwise addition identity

Therefore,

Equivalently, in bitwise notation, a^c = 2(a&c).

Thus, it is enough to count pairs $$$(a,c)$$$ such that $$$a \lt c \le n$$$ and a^c = 2(a&c).

For every such pair, $$$b$$$ is uniquely determined as $$$a \oplus c$$$. Also, $$$a \lt b \lt c$$$ follows from the two original conditions. We only need to enforce $$$a \lt c$$$: if $$$a=c$$$, then the equation becomes $$$0=2a$$$, which is impossible because $$$a \ge 1$$$.

We solve this with digit DP, processing bits from $$$60$$$ down to $$$0$$$. Let the state be

• bit: the bit currently being processed.
• cLess: whether the already processed prefix of $$$c$$$ is strictly smaller than the corresponding prefix of $$$n$$$.
• aLess: whether the already processed prefix of $$$a$$$ is strictly smaller than the corresponding prefix of $$$c$$$.
• need: the value required for the current bit of a&c, determined by the XOR value at the previous, more significant bit.

At each state, try all four choices for the current bits of $$$a$$$ and $$$c$$$. A transition is valid when:

1. The chosen prefix of $$$c$$$ does not exceed the prefix of $$$n$$$.
2. The chosen prefix of $$$a$$$ does not exceed the prefix of $$$c$$$.
3. The current bit of a&c equals need.

For the next lower bit, the new value of need is the XOR of the current bits of $$$a$$$ and $$$c$$$. This represents the one-bit left shift in a^c = 2(a&c).

After processing all bits, the state contributes $$$1$$$ exactly when need is $$$0$$$ and aLess is true, which guarantees $$$a \lt c$$$.

Time complexity: $$$\mathcal{O}(\log n)$$$ per test case.

#include <iostream>
#include <vector>
#include <cstring>
 
using namespace std;
 
long long dp[65][2][2][2];
long long n;
 
const int MOD = 1000000007;
 
long long solve_dp(int bit, int c_less, int a_less, int need) {
    if (bit < 0) {
        if (need == 0 && a_less == 1) return 1;
        return 0;
    }
    
    if (dp[bit][c_less][a_less][need] != -1) {
        return dp[bit][c_less][a_less][need];
    }
    
    long long ans = 0;
    int n_bit = (n >> bit) & 1;
    
    for (int a_bit = 0; a_bit <= 1; a_bit++) {
        for (int c_bit = 0; c_bit <= 1; c_bit++) {
            // Check constraint against n
            if (c_less && c_bit > n_bit) continue;
            
            // Check constraint a <= c (since we need a < c eventually)
            if (!a_less && a_bit > c_bit) continue;
            
            // Check the "need" condition for (a & c)
            if (need == 1 && (a_bit & c_bit) == 0) continue;
            if (need == 0 && (a_bit & c_bit) == 1) continue;
            
            int next_c_less = c_less && (c_bit == n_bit);
            int next_a_less = a_less || (a_bit < c_bit);
            int next_need = a_bit ^ c_bit; // The next bit's & must match this bit's ^
            
            ans = (ans + solve_dp(bit - 1, next_c_less, next_a_less, next_need)) % MOD;
        }
    }
    
    return dp[bit][c_less][a_less][need] = ans;
}
 
void solve() {
    cin >> n;
    memset(dp, -1, sizeof(dp));
    // Start at bit 60, c is constrained by n, a is not yet less than c, need = 0
    cout << solve_dp(60, 1, 0, 0) << "\n";
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t; cin >> t;
    while(t--) {
        solve();
    }
    return 0;
}

Let's solve the problem independently for a single color $$$c$$$ with $$$M$$$ vertices.

First, consider the case where $$$k = 1$$$. The optimal component is a single vertex, which mathematically corresponds to the centroid of the $$$M$$$ vertices. For any edge $$$e$$$ in the tree, let $$$m_{\mathrm{in}}[e]$$$ and $$$m_{\mathrm{out}}[e]$$$ be the number of color $$$c$$$ vertices on either side of the edge. The number of paths from color $$$c$$$ vertices that must cross edge $$$e$$$ to reach the centroid is exactly $$$w[e] = \min(m_{\mathrm{in}}[e], m_{\mathrm{out}}[e])$$$. Thus, the total distance to the centroid is:

where the sum is over all edges $$$e$$$ in the tree.

When $$$k \gt 1$$$, we must choose a connected component $$$S$$$ of $$$k$$$ vertices (which contains exactly $$$k - 1$$$ edges). Notice that if an edge $$$e$$$ is entirely inside $$$S$$$, no path from any colored vertex to $$$S$$$ needs to cross it (the distance is absorbed into the component). If an edge is outside $$$S$$$, exactly $$$w[e]$$$ paths still cross it. Thus, the cost of any valid component $$$S$$$ containing the centroid is:

To minimize $$$\mathrm{Cost}(S)$$$, we must maximize the sum of $$$w[e]$$$ for the $$$k - 1$$$ edges we pick. A crucial property of tree centroids is that $$$w[e]$$$ is monotonically decreasing as you move away from the centroid. Because of this monotonicity, if we simply greedily pick the $$$k - 1$$$ edges with the globally maximum $$$w[e]$$$ values in the entire tree, they are mathematically guaranteed to form a connected component containing the centroid!

However, calculating this naively for all colors takes $$$\mathcal{O}(N^2)$$$. To achieve the required time complexity, we process all colors using Virtual Trees (also known as Auxiliary Trees):

1. For each color $$$c$$$, build a Virtual Tree of its $$$M$$$ vertices in $$$\mathcal{O}(M \log M)$$$ time using LCA.
2. Run a bottom-up DP on the Virtual Tree to find $$$m_{\mathrm{in}}$$$ for each virtual subtree.
3. A virtual edge $$$(u, v)$$$ represents a compressed path of $$$L = \operatorname{depth}[v] - \operatorname{depth}[u]$$$ real edges. Because there are no other vertices of color $$$c$$$ branching off this path, every single real edge on this path shares the exact same weight: $$$w' = \min(m_{\mathrm{in}}, m_c - m_{\mathrm{in}})$$$.
4. For color $$$c$$$, collect the pairs (weight = $$$w'$$$, count = $$$L$$$) for all virtual edges.
5. Sort these pairs by weight descending, and greedily pick up to $$$K - 1$$$ edges to subtract from the total sum of all $$$w[e]$$$.

Since the sum of sizes of all Virtual Trees over all colors is $$$\mathcal{O}(n)$$$, the overall time complexity is $$$\mathcal{O}(n \log n)$$$.

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
const int LOG = 19;
int n;
vector<int> C, K;
vector<vector<int>> adj;
vector<int> tin, tout, depth;
vector<vector<int>> up;
int timer = 0;
 
void dfs(int v, int p, int d) {
    tin[v] = ++timer;
    depth[v] = d;
    up[v][0] = p;
    for (int i = 1; i < LOG; i++) {
        up[v][i] = up[up[v][i - 1]][i - 1];
    }
    for (int u : adj[v]) {
        if (u != p) dfs(u, v, d + 1);
    }
    tout[v] = ++timer;
}
 
bool is_ancestor(int u, int v) {
    return tin[u] <= tin[v] && tout[u] >= tout[v];
}
 
int get_lca(int u, int v) {
    if (is_ancestor(u, v)) return u;
    if (is_ancestor(v, u)) return v;
    for (int i = LOG - 1; i >= 0; i--) {
        if (!is_ancestor(up[u][i], v)) u = up[u][i];
    }
    return up[u][0];
}
 
void solve() {
    cin >> n;
    C.assign(n + 1, 0);
    K.assign(n + 1, 0);
    adj.assign(n + 1, vector<int>());
    tin.assign(n + 1, 0);
    tout.assign(n + 1, 0);
    depth.assign(n + 1, 0);
    up.assign(n + 1, vector<int>(LOG, 1));
    timer = 0;
 
    vector<vector<int>> colors(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> C[i];
        colors[C[i]].push_back(i);
    }
    for (int i = 1; i <= n; i++) cin >> K[i];
    
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
 
    dfs(1, 1, 0);
    
    vector<long long> ans(n + 1, -1);
    vector<int> cnt(n + 1, 0);
 
    for (int c = 1; c <= n; c++) {
        if (colors[c].empty()) continue;
        
        int M_c = colors[c].size();
        int K_c = K[c];
 
        vector<int> nodes = colors[c];
        sort(nodes.begin(), nodes.end(), [](int a, int b) { return tin[a] < tin[b]; });
 
        int sz = nodes.size();
        for (int i = 0; i < sz - 1; i++) {
            nodes.push_back(get_lca(nodes[i], nodes[i+1]));
        }
        
        sort(nodes.begin(), nodes.end(), [](int a, int b) { return tin[a] < tin[b]; });
        nodes.erase(unique(nodes.begin(), nodes.end()), nodes.end());
 
        for (int u : colors[c]) cnt[u] = 1;
 
        vector<int> st;
        vector<pair<int, int>> vt_edges;
        for (int u : nodes) {
            while (!st.empty() && !is_ancestor(st.back(), u)) st.pop_back();
            if (!st.empty()) vt_edges.push_back({st.back(), u});
            st.push_back(u);
        }
 
        long long total_dist = 0;
        vector<pair<long long, long long>> edge_weights; // {weight, count}
        
        for (int i = (int)vt_edges.size() - 1; i >= 0; i--) {
            int p = vt_edges[i].first;
            int u = vt_edges[i].second;
            cnt[p] += cnt[u];
            
            long long w = min((long long)cnt[u], (long long)M_c - cnt[u]);
            long long L = depth[u] - depth[p];
            total_dist += w * L;
            edge_weights.push_back({w, L});
        }
        
        sort(edge_weights.rbegin(), edge_weights.rend());
        
        long long saved = 0;
        long long needed = K_c - 1;
        for (auto& ew : edge_weights) {
            long long take = min(needed, ew.second);
            saved += take * ew.first;
            needed -= take;
            if (needed == 0) break;
        }
        
        ans[c] = total_dist - saved;
        for (int u : nodes) cnt[u] = 0;
    }
 
    for (int i = 1; i <= n; i++) {
        cout << ans[i] << (i == n ? "" : " ");
    }
    cout << "\n";
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t; cin >> t;
    while(t--) {
        solve();
    }
    return 0;
}