Circular Array Merging with Max-Cost

We are given a circular array of positive integers. In one step we can pick any two adjacent elements, remove them, and pay a cost equal to the larger of the two values. The goal is to reduce the array to a single element while minimiizng the total cost.

Key observation

Because every merge can only increase-increase the numbers involved, the optimal strategy is to eliminate the smallest elements first. Whenever the current minimum is removed, its two neighbors become adjacent, so the smaller of those two neighbors should be charged for the merge.

Algorithm

1. Store the array in a doubly-linked circular list so that each element knows its predecessor and successor.
2. Put all indices in a min-heap keyed by the element value.
3. Repeatedly extract the global minimum v at position p. Add min(left[p], right[p]) to the answer, splice p out of the list, and continue until one element remains.

Reference implementation

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

const int MAXN = 2e5 + 5;

int n;
int val[MAXN], prv[MAXN], nxt[MAXN];
using Node = pair<int,int>;
priority_queue<Node,vector<Node>,greater<Node>> pq;

long long solve() {
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> val[i];
        prv[i] = (i - 1 + n) % n;
        nxt[i] = (i + 1) % n;
        pq.emplace(val[i], i);
    }

    long long cost = 0;
    vector<bool> gone(n, false);

    while (pq.size() > 1) {
        auto [v, p] = pq.top(); pq.pop();
        if (gone[p]) continue;

        int l = prv[p], r = nxt[p];
        cost += min(val[l], val[r]);

        // unlink p
        nxt[l] = r;
        prv[r] = l;
        gone[p] = true;
    }
    return cost;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;  cin >> T;
    while (T--) cout << solve() << '\n';
    return 0;
}

Counting Distinct Mulitsets under Coverage

Given a multiset of integers, we can mark some occurrences as featured. A non-featured occurrence is covered if at least one occurrence of the same value is featured. We want to count how many different final multisets (after discarding covered elements) can be obtained.

Reduction

The numeric values themselves are irrelevant; only the frequency of each distinct number matters. Let c[i] be the count of the i-th distinct value. For each value we decide either

• mark none of its occurrences (all c[i] copies are removed), or
• mark all c[i] copies (they all survive).

Hence every value contributes either 0 or c[i] elements to the final multiset.

Dynamic programming

Let dp[k] be the number of ways to obtain a multiset of total size k. Initialize dp[0] = 1. For each value with frequency cnt, update the knapsack in reverse:

for k from n downto cnt:
    dp[k] = (dp[k] + cnt * dp[k - cnt]) % MOD

Final answer

smallest possible size of the final multiset is the largest single frequency maxC, because we must keep at least one group of identical elements. Sum dp[k] for k = maxC .. n.

Reference implementation

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

const int MAXN = 5005;
const int MOD  = 1e9 + 7;

int n, freq[MAXN];
long long dp[MAXN];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;  cin >> T;
    while (T--) {
        cin >> n;
        memset(freq, 0, sizeof(freq));
        int maxC = 0;
        for (int i = 0, x; i < n; ++i) {
            cin >> x;
            ++freq[x];
            maxC = max(maxC, freq[x]);
        }

        memset(dp, 0, sizeof(dp));
        dp[0] = 1;
        for (int v = 1; v < MAXN; ++v) {
            int cnt = freq[v];
            if (!cnt) continue;
            for (int k = n; k >= cnt; --k)
                dp[k] = (dp[k] + cnt * dp[k - cnt]) % MOD;
        }

        long long ans = 0;
        for (int k = maxC; k <= n; ++k)
            ans = (ans + dp[k]) % MOD;
        cout << ans << '\n';
    }
    return 0;
}