A. The Good Array

Tags: greedy, math

Problem: For any (i \in {1,2,\dots,n}), the array (a) must have at least (\lceil \frac{i}{k} \rceil) ones among its first (i) elements and also atleast (\lceil \frac{i}{k} \rceil) ones among its last (i) elements.

Solution:

1. Special case (k=1): The positions where we can place ones are contiguous, so the answer is (n).
2. General case: To satisfy the condition for the prefix, a greedy approach places ones at positions (1, k+1, 2k+1, \dots, xk+1, n). Now we need to check if any additional ones are required to satisfy the suffix condition. Let (d = n % k - 1).
   • If (d > 0), then (0 < d < k), and no extra ones are needed. The answer is (\lfloor \frac{n-1}{k} \rfloor + 2).
   • If (d = 0), the last placed one coincides with position (n), which already satisfies the suffix condition for the first step. The answer is (\lfloor \frac{n-1}{k} \rfloor + 1).
   • If (d = -1), meaning (xk+1 = n+1), we use the previous position ((x-1)k+1) as the last mandatory one, and the answer is again (\lfloor \frac{n-1}{k} \rfloor + 2).
3. Time complexity: (\mathcal{O}(t)).

Code:

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int t, n, k;
    scanf("%d", &t);
    while (t--) {
        scanf("%d %d", &n, &k);
        if (k == 1) printf("%d\n", n);
        else if (n % k - 1 != 0) printf("%d\n", (n - 1) / k + 2);
        else printf("%d\n", (n - 1) / k + 1);
    }
    return 0;
}

Key Insight: Apart from positions (1) and (n), the distance between consecutive ones is always (k). The condition for requiring an extra one depends on whether the last placed one covers both ends.

B. Lamps

Tags: greedy, sortings

Solution:

1. Consider a constant (a): Suppose all (a_i = c). Sort the (b) values in descending order. The maximum total brightness we can obtain is the sum of the largest (\min(n, c)) values.
2. General case: For each possible (k) (from 1 to (n)), let (c_k) be the count of lamps with (a_i = k). Sort the (b) values for each (k) in descending order. The optimal contribution for lamps with this (a) value is the sum of the first (\min(k, c_k)) values. We can always process lamps with smaller (a) values first to maximize the final answer, which is (\sum_{k=1}^{n} s_k), where (s_k = \sum_{i=1}^{\min(k, c_k)} b_{k_i}).
3. Time complexity: (\mathcal{O}(n \log n)).

Code:

#include <bits/stdc++.h>
using namespace std;
 
const int maxn = 2e5 + 100;
 
struct Lamp {
    int a, b;
} lamps[maxn];
 
bool cmp(Lamp x, Lamp y) {
    if (x.a == y.a) return x.b > y.b;
    return x.a < y.a;
}
 
int main() {
    int t, n;
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &n);
        vector<int> cnt(n + 1, 0);
        for (int i = 1; i <= n; i++) {
            scanf("%d %d", &lamps[i].a, &lamps[i].b);
            cnt[lamps[i].a]++;
            if (cnt[lamps[i].a] > lamps[i].a) cnt[lamps[i].a] = lamps[i].a;
        }
        sort(lamps + 1, lamps + n + 1, cmp);
        long long ans = 0;
        for (int i = 1; i <= n; i++) {
            if (lamps[i].a == lamps[i-1].a) continue;
            int limit = cnt[lamps[i].a];
            for (int j = i; j < i + limit; j++)
                ans += lamps[j].b;
        }
        printf("%lld\n", ans);
    }
    return 0;
}

Key Insights:

• Start from the simplest case where all (a) are the same.
• The ability to destroy lamps after they are lit is crucial; it reduces the number of lit lamps.

C. Insert Zero and Invert Prefix

Tags: constructive algorithms

Solution:

1. Special cases: If all (a_i = 0), we can set all (p_i = 0). If (a_n = 1), no construction exists because a (1) at the end cannot be produced (a (1) appears only if there is a (0) before the inserted (0)).
2. Construction: We process the array (a) from right to left, grouping consecutive identical values. Each group is of the form (1,1,\dots,1,0,0,\dots,0) (or pure zeros or pure ones). To each group, we add to the answer array (b) (in order) (|S|-1) zeros followed by the number of ones in that group. This is done in a first-in-first-out manner.
3. Time complexity: (\mathcal{O}(n)).

Code:

#include <bits/stdc++.h>
using namespace std;
 
const int maxn = 1e5 + 100;
 
int main() {
    int t, n, a[maxn], b[maxn];
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
        if (a[n] == 1) {
            printf("NO\n");
            continue;
        }
        printf("YES\n");
        int p = n, idx = 0;
        while (p >= 1) {
            int left = -1, endZero = -1;
            // find the last zero segment
            for (int i = p; i >= 1; i--)
                if (a[i] == 0) { left = i; break; }
            if (left == -1) { // all ones? actually impossible
                // fill with zeros
                while (p >= 1) b[++idx] = 0, p--;
                break;
            }
            // find the start of ones before this zero segment
            for (int i = left - 1; i >= 1; i--)
                if (a[i] == 1) { endZero = i + 1; break; }
            if (endZero == -1) { // only zeros left
                while (p >= 1) b[++idx] = 0, p--;
                b[++idx] = (p > 0 ? p : 0); // actually number of ones is 0
                break;
            }
            // number of elements in this group: from endZero to p
            int groupLen = p - endZero + 1;
            // We need to output (groupLen-1) zeros
            for (int i = 1; i < groupLen; i++) b[++idx] = 0;
            // Then output the count of ones in this group (which is left - endZero + 1? Actually ones are from endZero to left-1)
            int onesCount = (left - endZero);
            b[++idx] = onesCount;
            // move p to before this group
            p = endZero - 1;
        }
        for (int i = 1; i <= n; i++) printf("%d ", b[i]);
        printf("\n");
    }
    return 0;
}

D. Ball Sorting

Tags: data structures, dp, sortings

Solution:

1. Role of zeros (free positions): A zero allows us to move a ball adjacent to it to any position, at a cost equal to the distance. With greedy, after rearrangements, the selected balls can be placed in increasing order of (c).
2. DP definition: Let (dp(i,j)) be the minimum cost to make the first (i) balls (considering positions 1 to (i)) increasing, using (j) zeros, and with the (i)-th ball not selected. We add sentinel values: (c_0 = 0), (c_{n+1} = n+1). Initialize (dp(i,0)=0) for the longest increasing prefix starting from 1.
3. Transition: For each (i) and (j),
   • We can choose not to use the (j)-th zero: (dp(i,j) = \min(dp(i,j), dp(i,j-1))).
   • Or we use it: for any (k < i) with (c_k < c_i), if (k < i-1), cost is (dp(k, j-1) + (i-k-1)); if (k = i-1), cost is (dp(k, j)). Take the minimum over all (k).
4. Answer: (dp(n+1, k)) for each (k) from 1 to (n).
5. Time complexity: (\mathcal{O}(tn^3)).

Code:

#include <bits/stdc++.h>
using namespace std;
 
const int maxn = 510;
const int INF = 0x3f3f3f3f;
 
int main() {
    int t, n, c[maxn], dp[maxn][maxn];
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) scanf("%d", &c[i]);
        c[0] = 0, c[n+1] = n+1;
        memset(dp, INF, sizeof(dp));
        dp[0][0] = 0;
        // initialize dp[i][0] for increasing prefix
        for (int i = 1; i <= n+1; i++) {
            if (c[i-1] < c[i]) dp[i][0] = 0;
            else break;
        }
        for (int i = 1; i <= n+1; i++) {
            for (int j = 1; j <= i; j++) {
                dp[i][j] = min(dp[i][j], dp[i][j-1]);
                for (int k = 0; k < i; k++) {
                    if (c[k] < c[i]) {
                        if (k < i-1) dp[i][j] = min(dp[i][j], dp[k][j-1] + i - k - 1);
                        else dp[i][j] = min(dp[i][j], dp[k][j]);
                    }
                }
            }
        }
        for (int i = 1; i <= n; i++) printf("%d ", dp[n+1][i]);
        printf("\n");
    }
    return 0;
}