# SPR - Editorial

Author: harshit_300
Tester: sky_nik
Editorialist: iceknight1093

TBD

# PREREQUISITES:

Prefix sums, binary search/two pointers

# PROBLEM:

There are N monsters, the i-th at position X_i and has health H_i.
Every second, you can shoot one monster, which reduces its health by 1. Then, every alive monster will move one step closer to you.

You also have a single bomb, which can be placed at the start at some position x and instantly kills all monsters in [x-K, x+K].
Is there a way to kill all the monsters?

# EXPLANATION:

First, letâ€™s look at the problem if the bomb wasnâ€™t available to us â€” so every monster is present, and only one HP can be reduced at a time.
In this scenario, itâ€™s always optimal to shoot at the leftmost alive monster.
So,

• The first monster can be killed if H_1 \leq X_1.
• The second monster can be killed if H_1 + H_2 \leq X_2
• The third monster can be killed if H_1 + H_2 + H_3\leq X_3
\vdots
• The i-th monster can be killed if H_1 + H_2 + \ldots + H_i \leq X_i

Let P_i = H_1 + H_2 + \ldots + H_i denote the prefix sum array of H.
Our earlier observation then says that we can kill all the monsters if and only if P_i \leq X_i for every i.

Next, letâ€™s look at what happens when the bomb is available.
To make things slightly easier to deal with, rather than [x-K, x+K], we can pretend the bomb deletes all enemies in [x, x+2K] (essentially rather than fixing the middle, weâ€™re fixing the left end).

Now, clearly the set of monsters deleted by the bomb will form some subarray [l, r].
Using our initial condition, itâ€™s easy to see that for the remaining monsters:

• For i \lt l, nothing really changes: to kill the first i monsters, P_i \leq X_i should hold.
• For i\gt r, we now no longer have to worry about the monsters from l to r.
So, for these indices, we instead want the condition P_i - (H_l + H_{l+1} + \ldots + H_r) \leq X_i to hold.

The first condition is easy to check: for example, precompute whether P_i \leq X_i for every i, then for each prefix you can once again precompute whether the condition holds.
As for the second condition, notice that (H_l + H_{l+1} + \ldots + H_r) is a constant (and in fact equals P_r - P_{l-1}), so what we really want to know is whether P_i - X_i \leq P_r - P_{l-1} for every i \gt r.
For this, note that itâ€™s enough to know the maximum value of P_i - X_i across all i \gt r, since if that satisfies the inequality then everything will. In other words, we only need to know a certain suffix minimum!

So, with appropriate prefix/suffix computations (which take linear time), we are in fact able to figure out in \mathcal{O}(1) whether placing the bomb at a certain range allows us to kill all the monsters.
This only leaves the task of choosing the range [l, r] of monsters that should be deleted.

Here, we simply try all possibilities - notice that if l is fixed, itâ€™s optimal to choose r to be as large as possible, i.e, the largest index such that X_r - X_l \leq 2K.
For a fixed l, finding such an r can be done in \mathcal{O}(\log N) time using binary search; or you can use two-pointers since r increases with l.

It is also possible to solve this task using a segment tree, as can be seen in the testerâ€™s code below.

# TIME COMPLEXITY:

\mathcal{O}(N) or \mathcal{O}(N\log N) per testcase.

# CODE:

Author's code (C++)
#include <bits/stdc++.h>
using namespace std;
#define IOS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ll long long

int main(){
IOS
int t;
cin>>t;
while(t--){
int n,k;
cin>>n>>k;
vector<int> a(n+1);
for(int i=1;i<=n;++i){
cin>>a[i];
}
vector<int> h(n+1);
for(int i=1;i<=n;++i){
cin>>h[i];
}
vector<ll> pref(n+2,1e9);
pref[0]=0;
for(int i=1;i<=n;++i){
pref[i]=pref[i-1]+h[i];
}
vector<ll> suff(n+2,-1e9);
suff[n+1]=a[n]+1;
for(int i=n;i>=1;--i){
suff[i]=min((ll)a[i],suff[i+1]-1)-h[i]+1;
}
int chk=0;
for(int i=1;i<=n;++i){
if(pref[i-1]>a[i-1]) break;
auto j=upper_bound(a.begin(),a.end(),a[i]+2*k)-a.begin();
if(pref[i-1]<suff[j]){
chk=1;
}
}
if(chk){
cout<<"Yes"<<'\n';
}else{
cout<<"No"<<'\n';
}
}
return 0;
}

Tester's code (C++)
#ifndef ATCODER_INTERNAL_BITOP_HPP
#define ATCODER_INTERNAL_BITOP_HPP 1

#ifdef _MSC_VER
#include <intrin.h>
#endif

#if __cplusplus >= 202002L
#include <bit>
#endif

namespace atcoder {

namespace internal {

#if __cplusplus >= 202002L

using std::bit_ceil;

#else

// @return same with std::bit::bit_ceil
unsigned int bit_ceil(unsigned int n) {
unsigned int x = 1;
while (x < (unsigned int)(n)) x *= 2;
return x;
}

#endif

// @param n 1 <= n
// @return same with std::bit::countr_zero
int countr_zero(unsigned int n) {
#ifdef _MSC_VER
unsigned long index;
_BitScanForward(&index, n);
return index;
#else
return __builtin_ctz(n);
#endif
}

// @param n 1 <= n
// @return same with std::bit::countr_zero
constexpr int countr_zero_constexpr(unsigned int n) {
int x = 0;
while (!(n & (1 << x))) x++;
return x;
}

}  // namespace internal

}  // namespace atcoder

#endif  // ATCODER_INTERNAL_BITOP_HPP

#ifndef ATCODER_LAZYSEGTREE_HPP
#define ATCODER_LAZYSEGTREE_HPP 1

#include <algorithm>
#include <cassert>
#include <functional>
#include <vector>

namespace atcoder {

#if __cplusplus >= 201703L

template <class S,
auto op,
auto e,
class F,
auto mapping,
auto composition,
auto id>
struct lazy_segtree {
static_assert(std::is_convertible_v<decltype(op), std::function<S(S, S)>>,
"op must work as S(S, S)");
static_assert(std::is_convertible_v<decltype(e), std::function<S()>>,
"e must work as S()");
static_assert(
std::is_convertible_v<decltype(mapping), std::function<S(F, S)>>,
"mapping must work as F(F, S)");
static_assert(
std::is_convertible_v<decltype(composition), std::function<F(F, F)>>,
"compostiion must work as F(F, F)");
static_assert(std::is_convertible_v<decltype(id), std::function<F()>>,
"id must work as F()");

#else

template <class S,
S (*op)(S, S),
S (*e)(),
class F,
S (*mapping)(F, S),
F (*composition)(F, F),
F (*id)()>
struct lazy_segtree {

#endif

public:
lazy_segtree() : lazy_segtree(0) {}
explicit lazy_segtree(int n) : lazy_segtree(std::vector<S>(n, e())) {}
explicit lazy_segtree(const std::vector<S>& v) : _n(int(v.size())) {
size = (int)internal::bit_ceil((unsigned int)(_n));
log = internal::countr_zero((unsigned int)size);
d = std::vector<S>(2 * size, e());
lz = std::vector<F>(size, id());
for (int i = 0; i < _n; i++) d[size + i] = v[i];
for (int i = size - 1; i >= 1; i--) {
update(i);
}
}

void set(int p, S x) {
assert(0 <= p && p < _n);
p += size;
for (int i = log; i >= 1; i--) push(p >> i);
d[p] = x;
for (int i = 1; i <= log; i++) update(p >> i);
}

S get(int p) {
assert(0 <= p && p < _n);
p += size;
for (int i = log; i >= 1; i--) push(p >> i);
return d[p];
}

S prod(int l, int r) {
assert(0 <= l && l <= r && r <= _n);
if (l == r) return e();

l += size;
r += size;

for (int i = log; i >= 1; i--) {
if (((l >> i) << i) != l) push(l >> i);
if (((r >> i) << i) != r) push((r - 1) >> i);
}

S sml = e(), smr = e();
while (l < r) {
if (l & 1) sml = op(sml, d[l++]);
if (r & 1) smr = op(d[--r], smr);
l >>= 1;
r >>= 1;
}

return op(sml, smr);
}

S all_prod() { return d[1]; }

void apply(int p, F f) {
assert(0 <= p && p < _n);
p += size;
for (int i = log; i >= 1; i--) push(p >> i);
d[p] = mapping(f, d[p]);
for (int i = 1; i <= log; i++) update(p >> i);
}
void apply(int l, int r, F f) {
assert(0 <= l && l <= r && r <= _n);
if (l == r) return;

l += size;
r += size;

for (int i = log; i >= 1; i--) {
if (((l >> i) << i) != l) push(l >> i);
if (((r >> i) << i) != r) push((r - 1) >> i);
}

{
int l2 = l, r2 = r;
while (l < r) {
if (l & 1) all_apply(l++, f);
if (r & 1) all_apply(--r, f);
l >>= 1;
r >>= 1;
}
l = l2;
r = r2;
}

for (int i = 1; i <= log; i++) {
if (((l >> i) << i) != l) update(l >> i);
if (((r >> i) << i) != r) update((r - 1) >> i);
}
}

template <bool (*g)(S)> int max_right(int l) {
return max_right(l, [](S x) { return g(x); });
}
template <class G> int max_right(int l, G g) {
assert(0 <= l && l <= _n);
assert(g(e()));
if (l == _n) return _n;
l += size;
for (int i = log; i >= 1; i--) push(l >> i);
S sm = e();
do {
while (l % 2 == 0) l >>= 1;
if (!g(op(sm, d[l]))) {
while (l < size) {
push(l);
l = (2 * l);
if (g(op(sm, d[l]))) {
sm = op(sm, d[l]);
l++;
}
}
return l - size;
}
sm = op(sm, d[l]);
l++;
} while ((l & -l) != l);
return _n;
}

template <bool (*g)(S)> int min_left(int r) {
return min_left(r, [](S x) { return g(x); });
}
template <class G> int min_left(int r, G g) {
assert(0 <= r && r <= _n);
assert(g(e()));
if (r == 0) return 0;
r += size;
for (int i = log; i >= 1; i--) push((r - 1) >> i);
S sm = e();
do {
r--;
while (r > 1 && (r % 2)) r >>= 1;
if (!g(op(d[r], sm))) {
while (r < size) {
push(r);
r = (2 * r + 1);
if (g(op(d[r], sm))) {
sm = op(d[r], sm);
r--;
}
}
return r + 1 - size;
}
sm = op(d[r], sm);
} while ((r & -r) != r);
return 0;
}

private:
int _n, size, log;
std::vector<S> d;
std::vector<F> lz;

void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
void all_apply(int k, F f) {
d[k] = mapping(f, d[k]);
if (k < size) lz[k] = composition(f, lz[k]);
}
void push(int k) {
all_apply(2 * k, lz[k]);
all_apply(2 * k + 1, lz[k]);
lz[k] = id();
}
};

}  // namespace atcoder

#endif  // ATCODER_LAZYSEGTREE_HPP

using namespace atcoder;

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

// b[i] = sum(h[j] for j in range(n) if a[j] == i)
// dp[i] = i - sum(b[j] for j in range(i + 1))
// min(dp[i]) >= 0

// remove (a[i], h[i]):
// b[a[i]] -= h[i]
// for j in range(i, n):
//     dp[j] += h[i]

// insert (a[i], h[i]):
// b[a[i]] += h[i]
// for j in range(i, n):
//     dp[j] -= h[i]

using S = int64_t;
S op(S l, S r) { return min(l, r); }
S e() { return numeric_limits<S>::max(); }
using F = int64_t;
S mapping(F f, S x) { return f + x; }
F composition(F f, F g) { return f + g; }
F id() { return 0; }

int main() {
cin.tie(0)->sync_with_stdio(0);

int t; cin >> t; while (t--) {
int n, k;
cin >> n >> k;
vector<int> a(n), h(n);
for (auto& ai : a) {
cin >> ai;
}
for (auto& hi : h) {
cin >> hi;
}

map<int, int64_t> mp;
for (int i = 0; i < n; ++i) {
mp[a[i]] += h[i];
}
map<int, int64_t> ps = {{0, 0}};
for (const auto& [key, val] : mp) {
ps[key] = prev(ps.end())->second + val;
}

vector<pair<int, int64_t>> ab(ps.cbegin(), ps.cend());
const int sz = ab.size();
map<int, int> idx;
for (int i = 0; i < sz; ++i) {
const auto& [a, _] = ab[i];
idx[a] = i;
}

lazy_segtree<S, op, e, F, mapping, composition, id> dp(sz);
for (int i = 0; i < sz; ++i) {
const auto& [a, b] = ab[i];
dp.set(i, a - b);
}

set<int> events;
for (const auto& [a, b] : ab) {
events.insert(a - k);
events.insert(a + k);
}

bool any = false;
for (const auto x : events) {
if (idx.count(x + k)) {
dp.apply(idx[x + k], sz, mp[x + k]);
}
any |= dp.all_prod() >= 0;
if (idx.count(x - k)) {
dp.apply(idx[x - k], sz, -mp[x - k]);
}
}
cout << (any ? "YES" : "NO") << '\n';
}
}

Editorialist's code (Python)
for _ in range(int(input())):
n, k = map(int, input().split())
a = list(map(int, input().split()))
h = list(map(int, input().split()))

sm = 0
pref, suf = [0]*n, [0]*n
for i in range(n):
sm += h[i]
pref[i] = 1 if sm <= a[i] else 0
if i > 0: pref[i] &= pref[i-1]
suf[i] = sm - a[i]
for i in reversed(range(n-1)):
suf[i] = max(suf[i], suf[i+1])

r = 0
ans = 'No'
removed = 0
for l in range(n):
while r < n and a[r] - a[l] <= 2*k:
removed += h[r]
r += 1
good = 1
if l > 0: good &= pref[l-1]
if r < n: good &= suf[r] - removed <= 0
if good: ans = 'Yes'
removed -= h[l]
print(ans)


2 Likes

Can anyone help me . Why my logic is not working . Which testcase my code is failing ?
Code: CodeChef: Practical coding for everyone

1 Like

O(n^2) is getting accepted. I was getting wrong answer on my logic so submitted a brute force. Surprisingly it got accepted. Ig testcases are weak.

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

#define md                  1000000007
#define pb                  push_back
#define endl                "\n"
#define F                   first
#define S                   second
#define sz(x)               (int)(x).size()
#define inp(v)              for(auto &x: v) cin>>x
#define all(x)              (x).begin(), (x).end()
#define rep(i, a, b)        for (int i = a; i < (b); ++i)
#define fast_io             cin.tie(0)->sync_with_stdio(0);cin.exceptions(cin.failbit);

using ll  = long long;
using ull = unsigned long long;
using lld = long double;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using vl  = vector<ll>;
using vi  = vector<int>;

bool check(ll n,ll k,ll ind,vl &v,vl &h){
ll mx=v[ind]+2*k,mn=v[ind],x=0;
rep(i,0,n){
if(v[i]<=mx and v[i]>=mn) continue;
if(v[i]-x<h[i]){
return 0;
}
x+=(h[i]);
}
return 1;
}

void dk(){
ll n,k;
cin>>n>>k;
vl v(n);
inp(v);
vl h(n);
inp(h);
ll x=0,ind=0;
set<int>st;
st.insert(ind);
st.insert(0);
for(int i=0;i<n;i++){
st.insert(i);
}
for(auto i:st){
if(check(n,k,i,v,h)){
cout<<"YES"<<endl;
return;
}
}
cout<<"NO"<<endl;
}

int main()
{
fast_io;

int _=1;
cin>>_;
for(int i=0;i<_;i++){
dk();
}
return 0;
}

2 Likes

I apologize for the oversight and hope it didnâ€™t affect the contest significantly. I focused on a different suboptimal approach during testing, but it TLEd as expected so I greenlit the problem. Unfortunately, I didnâ€™t think about the most obvious suboptimal approach. Of course, we wonâ€™t change the test cases after the contest, but maybe weâ€™ll add stronger tests to the practice section to enhance the training experience.

1 Like

someone please provide the wrong testcase for my solution.
thank you !! <3

https://www.codechef.com/viewsolution/1063421832

Is this a valid approach? I greedily kill all the monsters that can be killed initially(prefix sums) and the first monster that canâ€™t be killed, from that x i place the bomb so that itâ€™s range is x to x + 2k, and then i calculate for the rest of the monsters ofc taking into account the monsters before the bomb.
@sky_nik

Imagine a case where monster which youâ€™ll be killing greedily have more health than the monsters that are situated later on. So itâ€™d make more sense to kill the monsters that would leverage us more time.

Can someone explain what is happening in the suffix block in the authorâ€™s code