Preface
This virtual contest didn't go as smoothly as expected. I spent longer than anticipated on problem B. For problem D, I identified the solution approach quickly but failed to account for several edge cases, resulting in three wrong submissions. Moving forward, I need to pay closer attention to edge cases during competition and work through sample data manually rather than hoping to get lucky with the solution.
A. Moving Chips
Each move can fill in a single zero. The problem reduces to counting the zeros that appear between ones in the array. Zeros at the beginning and end of the array should be ignored since they don't require any moves to "bridge" the ones.
The approach is straightforward: find the leftmost and rightmost positions containing ones, then count zeros within this bounded range. If no ones exist (all zeros), the answer is zero.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int testCases;
cin >> testCases;
const int MAXN = 55;
while (testCases--) {
int length;
cin >> length;
vector<int> cells(length + 1);
for (int i = 1; i <= length; ++i) {
cin >> cells[i];
}
// Find boundaries containing ones
int left = 1;
while (left <= length && cells[left] == 0) ++left;
int right = length;
while (right >= 1 && cells[right] == 0) --right;
if (left > right) {
cout << 0 << '\n';
continue;
}
int movesRequired = 0;
for (int i = left; i <= right; ++i) {
if (cells[i] == 0) ++movesRequired;
}
cout << movesRequired << '\n';
}
return 0;
}
B. Monsters Attack!
This problem required more careful consideration. Since attacking monsters to the left or right yields identical results, we can mirror all monsters from the left side to the right side, effectively working with only one direction.
The greedy strategy involves always targeting the nearest monster. Let sum_i represent the cumulative health of all monsters at positions [1, i]. This value also indicates the total bullets required to eliminate these monsters. By time i, a player can fire i * k bullets (since k bullets are fired per unit time).
If there exists any index i where i * k < sum_i, it means the player cannot fire enough bullets before monsters reach position zero—the player loses. Conversely, if i * k >= sum_i holds for all positions, all monsters can be eliminated before reaching the player.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int testCases;
cin >> testCases;
const int MAXN = 300005;
while (testCases--) {
int monsterCount, fireRate;
cin >> monsterCount >> fireRate;
vector<int> health(monsterCount + 1);
vector<int> position(monsterCount + 1);
for (int i = 1; i <= monsterCount; ++i) {
cin >> health[i];
}
vector<long long> requiredBullets(monsterCount + 1, 0);
for (int i = 1; i <= monsterCount; ++i) {
cin >> position[i];
if (position[i] < 0) position[i] = -position[i];
requiredBullets[position[i]] += health[i];
}
bool canSurvive = true;
long long cumulativeHealth = 0;
for (int i = 1; i <= monsterCount; ++i) {
cumulativeHealth += requiredBullets[i];
long long availableBullets = 1LL * i * fireRate;
if (cumulativeHealth > availableBullets) {
canSurvive = false;
break;
}
}
cout << (canSurvive ? "YES" : "NO") << '\n';
}
return 0;
}
C. Find B
If the query interval contains no ones, constructing array b is straightforward—for example, using a large number combined with multiple ones. The complexity arises when ones are present in the interval.
To minimize the impact of ones, assign them the value 2 in array b. This approach maximizes the sum available for remaining elements, providing more flexibility. The remaining elements can at most be reduced to 1. If reducing all non-one elements to 1 still cannot achieve the required sum, the interval cannot form a valid array b.
Let len be the interval length, total be the sum of elements, and onesCount be the count of ones. The number of non-one elements is len - onesCount, with a sum of total - onesCount. When converting to array b, this sum can decrease by at most (total - onesCount) - (len - onesCount) = total - len. Raising all ones to 2 requires atleast an increase of onesCount. If total - len >= onesCount, the construction is possible.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int testCases;
cin >> testCases;
const int MAXN = 300005;
while (testCases--) {
int arraySize, queryCount;
cin >> arraySize >> queryCount;
vector<int> arr(arraySize + 1);
vector<int> prefixOnes(arraySize + 1, 0);
vector<long long> prefixSum(arraySize + 1, 0);
for (int i = 1; i <= arraySize; ++i) {
cin >> arr[i];
prefixOnes[i] = prefixOnes[i - 1] + (arr[i] == 1);
prefixSum[i] = prefixSum[i - 1] + arr[i];
}
while (queryCount--) {
int left, right;
cin >> left >> right;
if (left == right) {
cout << "NO\n";
continue;
}
int intervalLength = right - left + 1;
int onesInInterval = prefixOnes[right] - prefixOnes[left - 1];
long long sumInInterval = prefixSum[right] - prefixSum[left - 1];
if (sumInInterval - intervalLength >= onesInInterval) {
cout << "YES\n";
} else {
cout << "NO\n";
}
}
}
return 0;
}
D. Slimes
This problem is genuinely challenging—it's puzzling why platforms rate it yellow rather than higher.
First observation: if all slimes in a segment are not identical, they can always be merged into a single slime. Second, since a slime can only consume adjacent slimes, each slime must eventually be consumed by either its left or right neighbor. We first analyze consumption from the left; consumption from the right simply requires reversing the sequence and recomputing.
Let the shortest interval needed for slime i to consume from the left be [l, i-1], where l should be maximized while satisfying sum[j from l to i-1] > a[i]. With prefix sums, this becomes prefix[i-1] - prefix[l-1] > a[i], or equivalently prefix[i-1] - a[i] > prefix[l-1]. When iterating through i, the left side is fixed, enabling binary search for the largest valid l due to the monotonicity of prefix sums.
The binary search can use lower_bound, but we must ensure the merged segment doesn't contain all identical elements. Track the position of the last element differing from a[i-1] (called boundary); all elements from this boundary to i-1 are identical. The search must occur only within this boundary and earlier positions.
Special case: if a[i-1] can consume a[i] alone, this should be recorded despite not qualifying as a true merge.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int testCases;
cin >> testCases;
const int MAXN = 3000005;
const int INF = 0x3f3f3f3f;
while (testCases--) {
int slimeCount;
cin >> slimeCount;
vector<long long> mass(slimeCount + 2, 0);
vector<long long> prefix(slimeCount + 2, 0);
vector<int> result(slimeCount + 2, INF);
auto solve = [&](bool reverseMode) {
int lastDifferent = 0;
for (int i = 1; i <= slimeCount; ++i) {
prefix[i] = prefix[i - 1] + mass[i];
int currentIdx = reverseMode ? (slimeCount - i + 1) : i;
// Direct consumption when left neighbor is larger
if (mass[i - 1] > mass[i]) {
result[currentIdx] = 1;
}
// Attempt finding valid merge interval
if (mass[i] < prefix[i - 1] && lastDifferent > 0) {
if (mass[i] < mass[i - 1]) {
result[currentIdx] = min(result[currentIdx], 1);
}
long long targetValue = prefix[i - 1] - mass[i];
int searchEnd = lastDifferent;
int searchPos = lower_bound(
prefix.begin() + 1,
prefix.begin() + searchEnd + 1,
targetValue
) - prefix.begin() - 1;
result[currentIdx] = min(result[currentIdx], i - searchPos);
}
// Update boundary when encountering different values
if (mass[i] != mass[i - 1]) {
lastDifferent = i - 1;
}
}
};
for (int i = 1; i <= slimeCount; ++i) {
cin >> mass[i];
}
solve(false);
reverse(mass.begin() + 1, mass.begin() + slimeCount + 1);
solve(true);
for (int i = 1; i <= slimeCount; ++i) {
int output = (result[i] == INF) ? -1 : result[i];
cout << output << ' ';
}
cout << '\n';
}
return 0;
}
E. Count Paths
Let colorCount[i] represent the available vertices with color i at the current point in the traversal.
During depth-first search, add colorCount[currentColor] to the answer—these vertices can pair with the current node. During recursive traversal of subtrees, the stored vertices in colorCount are all outside the current subtree. The current node blocks all other vertices of the same color, leaving only itself, so we set colorCount[currentColor] = 1.
When backtracking from the current node to process other branches, all vertices of the current color within the subtree are blocked by the current node. Therefore, regardless of the subtree's color count, we restore colorCount[currentColor] to its pre-subtree value plus one (accounting for the current node itself).
#include <bits/stdc++.h>
using namespace std;
struct Edge {
int destination;
int nextEdge;
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int testCases;
cin >> testCases;
const int MAXN = 200005;
while (testCases--) {
int nodeCount;
cin >> nodeCount;
vector<int> nodeColor(nodeCount + 1);
for (int i = 1; i <= nodeCount; ++i) {
cin >> nodeColor[i];
}
vector<Edge> edges(nodeCount * 2);
vector<int> head(nodeCount + 1, 0);
int edgeIndex = 0;
auto addEdge = [&](int u, int v) {
edges[++edgeIndex] = {v, head[u]};
head[u] = edgeIndex;
};
for (int i = 0; i < nodeCount - 1; ++i) {
int u, v;
cin >> u >> v;
addEdge(u, v);
addEdge(v, u);
}
vector<int> colorCounter(nodeCount + 1, 0);
long long totalPairs = 0;
function<void(int, int)> dfs = [&](int current, int parent) {
totalPairs += colorCounter[nodeColor[current]];
int previousCount = colorCounter[nodeColor[current]];
for (int e = head[current]; e != 0; e = edges[e].nextEdge) {
int neighbor = edges[e].destination;
if (neighbor == parent) continue;
colorCounter[nodeColor[current]] = 1;
dfs(neighbor, current);
}
colorCounter[nodeColor[current]] = previousCount + 1;
};
dfs(1, 0);
cout << totalPairs << '\n';
}
return 0;
}