A. Moving Chips

A greedy approach is applicable. Chips can only move left to the nearest empty cell. Therefore, only the longest contiguous segment of 1s matters (denoted as s). The chips within this segment need to be consolidated. The minimal number of moves equals the number of 0s inside this segment.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int test_cases;
    cin >> test_cases;
    while (test_cases--) {
        int length;
        cin >> length;
        vector<int> arr(length);
        int first_one = -1, last_one = -1, one_count = 0;
        for (int i = 0; i < length; ++i) {
            cin >> arr[i];
            if (arr[i] == 1) {
                if (first_one == -1) first_one = i;
                last_one = i;
                ++one_count;
            }
        }
        if (first_one == -1) {
            cout << "0\n";
            continue;
        }
        int segment_len = last_one - first_one + 1;
        cout << segment_len - one_count << '\n';
    }
    return 0;
}

B. Monster Attack

Monsters must be defeated in order of increasing absolute distance from the player. A prefix sum of health is maintained. If at any point the cumulative health exceeds the product of attack power k and the current monster's distance, the answer is "NO".

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

struct Creature {
    int64 health;
    int64 position;
};

bool compareByDist(const Creature &x, const Creature &y) {
    return abs(x.position) < abs(y.position);
}

void process_case() {
    int64 n, attack_power;
    cin >> n >> attack_power;
    vector<Creature> monsters(n);
    for (auto &m : monsters) cin >> m.health;
    for (auto &m : monsters) cin >> m.position;
    sort(monsters.begin(), monsters.end(), compareByDist);
    int64 total_damage_needed = 0;
    for (const auto &m : monsters) {
        total_damage_needed += m.health;
        if (total_damage_needed > attack_power * abs(m.position)) {
            cout << "NO\n";
            return;
        }
    }
    cout << "YES\n";
}

int main() {
    int tests;
    cin >> tests;
    while (tests--) process_case();
    return 0;
}

C. Find a Good Subsequence

Given a subarray, we must determine if a "good" array can exist where elements are positive, the total sum matches, but at least one element differs. The key is to check if the sum of decrements possible from elements greater than 1 can cover the number of 1s present, as 1s can only be incremented.

#include <iostream>
#include <vector>
using namespace std;
using int64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int test_cases;
    cin >> test_cases;
    while (test_cases--) {
        int n, queries;
        cin >> n >> queries;
        vector<int64> prefix_sum(n + 1), one_prefix(n + 1);
        for (int i = 1; i <= n; ++i) {
            int64 val;
            cin >> val;
            --val; // max possible decrement for this element
            prefix_sum[i] = prefix_sum[i - 1] + val;
            one_prefix[i] = one_prefix[i - 1] + (val == 0); // count of ones
        }
        while (queries--) {
            int left, right;
            cin >> left >> right;
            if (left == right) {
                cout << "NO\n";
                continue;
            }
            int64 ones = one_prefix[right] - one_prefix[left - 1];
            int64 available = prefix_sum[right] - prefix_sum[left - 1];
            cout << (available >= ones ? "YES\n" : "NO\n");
        }
    }
    return 0;
}

D. Slime Eating

For each slime, compute the minimum operations to be eaten by a larger slime from the left or right. Use binary search on the left side to find the farthest starting index of a contiguous segment to the left whose sum exceeds the current slime's size and contains at least two distinct values. The operation count is the distance. Repeat the process on the reversed array for the right side.

#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
const int64 INF = 1e18;
const int MAX = 2000005;

vector<int64> arr(MAX), prefix(MAX), last_diff(MAX), result(MAX), reversed_arr(MAX);

bool can_eat_from_left(int start, int idx) {
    if (start > last_diff[idx - 1]) return false;
    return (prefix[idx - 1] - prefix[start - 1]) > arr[idx];
}

void compute_direction() {
    int n;
    cin >> n;
    fill(result.begin(), result.begin() + n + 2, INF);
    for (int i = 1; i <= n; ++i) {
        cin >> arr[i];
        reversed_arr[n - i + 1] = arr[i];
        prefix[i] = prefix[i - 1] + arr[i];
        if (arr[i] == arr[i - 1]) last_diff[i] = last_diff[i - 1];
        else last_diff[i] = i - 1;
    }
    for (int i = 1; i <= n; ++i) {
        if (arr[i] < arr[i - 1]) {
            result[i] = 1;
            continue;
        }
        int low = 1, high = i - 1, ans_pos = -1;
        while (low <= high) {
            int mid = (low + high) / 2;
            if (can_eat_from_left(mid, i)) {
                ans_pos = mid;
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        if (ans_pos != -1) result[i] = min(result[i], (int64)(i - ans_pos));
    }
    // Process reversed array for right side
    for (int i = 1; i <= n; ++i) arr[i] = reversed_arr[i];
    for (int i = 1; i <= n; ++i) {
        prefix[i] = prefix[i - 1] + arr[i];
        if (arr[i] == arr[i - 1]) last_diff[i] = last_diff[i - 1];
        else last_diff[i] = i - 1;
    }
    for (int i = 1; i <= n; ++i) {
        if (arr[i] < arr[i - 1]) {
            result[n - i + 1] = 1;
            continue;
        }
        int low = 1, high = i - 1, ans_pos = -1;
        while (low <= high) {
            int mid = (low + high) / 2;
            if (can_eat_from_left(mid, i)) {
                ans_pos = mid;
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        if (ans_pos != -1) result[n - i + 1] = min(result[n - i + 1], (int64)(i - ans_pos));
    }
    for (int i = 1; i <= n; ++i) {
        cout << (result[i] == INF ? -1 : result[i]) << " ";
    }
    cout << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int tests;
    cin >> tests;
    while (tests--) compute_direction();
    return 0;
}