SPR - Editorial

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: harshit_300
Tester: sky_nik
Editorialist: iceknight1093

DIFFICULTY:

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