PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: apoorv_me
Tester: sky_nik
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
None
PROBLEM:
There are N balls on the x-axis. The i-th is at X_i and has power P_i.
A ball can be activated to move either left or right.
When it moves:
- It will move P_i units in its direction.
- If it hits another ball, it will disappear, and the newly hit ball will instead be activated in the same direction.
- If it never hits a ball, it won’t disappear.
Is it possible to activate at most two balls such that in the end, at most two balls remain?
EXPLANATION:
Note that when Alice activates some ball, its movement will then further activate some range of balls.
Further, since a ball can only be activated once, the two ranges of activated balls cannot intersect.
On the other hand, we also want to activate every ball at the end of both moves.
This is only possible if one move activates some prefix of the balls, and the other move activates the remaining suffix - that is, for some i, one move should activate balls 1, 2, \ldots, i, and the other should activate balls i+1, i+2, \ldots, N.
Now, we need to check whether that’s possible.
Let’s look at the prefix of length i. Note that if we are to activate them all with a single move, we only have two options: either activate 1 to the right, or activate i to the left.
So, let’s precompute some values:
- x_1, the last ball activated if 1 is activated to the right.
This can be easily computed in \mathcal{O}(N) time by just simulating what happens when 1 is activated. - \text{left}_i, which is a boolean value that denotes whether activating i to the left will activate its entire prefix.
This is fairly easy to calculate too: \text{left}_i is true if and only if ball i can reach ball i-1, and also \text{left}_{i-1} is true.
\text{left}_1 is true by default.
With these two values in hand, observe that the prefix of length i can be activated if and only if one of these two conditions is true:
- x_1 \geq i
- \text{left}_i = 1
Similarly, we can compute x_N and \text{right}_i, which will tell us whether each suffix can be activated in a single move.
Finally, for each i from 1 to N, check if the prefix ending at i and the suffix starting at i+1 can both be activated in a single move each.
If this is true for any index i, the answer is Yes, otherwise it’s No.
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Tester's code (C++)
#include <bits/stdc++.h>
using namespace std;
int main() {
cin.tie(0)->sync_with_stdio(0);
int t; cin >> t; while (t--) {
int n;
cin >> n;
vector<int> x(n), p(n);
for (auto& xi : x) {
cin >> xi;
}
for (auto& pi : p) {
cin >> pi;
}
auto max_right = [&](int l, bool dir) -> int {
while (l + 1 < n && x[l + 1] - x[l] <= p[l + dir]) {
++l;
}
return l;
};
auto min_left = [&](int r, bool dif) -> int {
while (r > 0 && x[r] - x[r - 1] <= p[r - dif]) {
--r;
}
return r;
};
cout << (max(max_right(0, true), max_right(0, false)) + 1 >=
min(min_left(n - 1, true), min_left(n - 1, false)) ? "YES" : "NO") << '\n';
}
}
Editorialist's code (Python)
for _ in range(int(input())):
n = int(input())
pos = list(map(int, input().split()))
a = list(map(int, input().split()))
pref, suf = [0]*n, [0]*n
pref[0] = 1
for i in range(1, n):
if pref[i-1] == 0: break
if pos[i] - a[i] <= pos[i-1]: pref[i] = 1
suf[-1] = 1
for i in reversed(range(n-1)):
if suf[i+1] == 0: break
if pos[i] + a[i] >= pos[i+1]: suf[i] = 1
x = 0
while x+1 < n:
if pos[x] + a[x] >= pos[x+1]: x += 1
else: break
y = n-1
while y > 0:
if pos[y] - a[y] <= pos[y-1]: y -= 1
else: break
ans = 'NO'
for i in range(n-1):
if (x >= i or pref[i]) and (y <= i+1 or suf[i+1]): ans = 'YES'
if x == n-1 or y == 0 or pref[-1] or suf[0]: ans = 'YES'
print(ans)
