MAXPARR - Editorial

editorial
, ,
1

PROBLEM LINK:

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

Author: iceknight1093
Tester: sushil2006
Editorialist: iceknight1093

DIFFICULTY:

Easy

PREREQUISITES:

None

PROBLEM:

There are N attacks in a row; the i-th attack needs A_i skill to dodge and B_i skill to parry.
A_i \leq B_i.
Parrying an attack reduces your skill level by 1, dodging does nothing.

Your initial skill is X.
Let M be the maximum number of attacks that can be parried, while still being able to either dodge or parry each of the N attacks.
For each i from 1 to N, decide whether there exists a sequence of M parries that also parries the i-th attack.

EXPLANATION:

Recall from the solution to the easy version that we had a fairly straightforward greedy algorithm to compute M, the maximum number of parries: from left to right, greedily parry as long as nothing in the future breaks.

Importantly, note that the greedy algorithm is in fact optimal for each prefix of attacks.
That is, we now know, in each prefix, the maximum number of attacks we can safely parry.

Now, let’s fix an index i.
Let P_i be the maximum number of parries that can be obtained from the attacks before (and not including) i.
Then, before i we can choose to perform anywhere between 0 and P_i parries.

If we want to parry the i-th attack, our best hope is to shift as many parries as possible to after index i; and leave the minimum possible before it.
This will result in our skill being as high as possible when dealing with attack i.
Of course, we can’t arbitrarily minimize the number of early parries, since we need to ensure we’re able to reach M in the end.

Minimizing the number of parries before i is equivalent to maximizing the number of parries after it.
So, let’s try to find, for each index i, the maximum number of parries we can perform among attacks i, i+1, \ldots, N.

Solving just “maximum number of parries” for each suffix is a hard problem – luckily for us, that’s not exactly what we want.
What we want is the maximum number of parries in the suffix, while ensuring that M parries can be reached in the end.

To do this, we can simply reverse the initial algorithm with which we found M in the first place.
That is, start with skill level X-M+1 (which is the value just before the final parry), and process attacks in reverse.
If the current attack can be parried by the current skill level, simply increase it by 1.

The reason this works is exactly the same as the reason the initial greedy worked.
However, since this algorithm worked on suffixes, it computes the last possible parries while still being able to reach M on each suffix.
This is exactly what we want!

Let S_i be the number of parries that can be performed on the suffix starting at i, as per our algorithm above.
P_i is, if you recall, the number of parries that can be performed before index i.

Now, to answer the question for index i:

  • There can be at most S_{i+1} parries after index i.
  • This means at least M-1-S_{i+1} parries should come before i; with the last one coming from i itself.
  • So, if P_i \lt M-1-S_{i+1}, it’s impossible to parry attack i.
  • Otherwise, we can always take S_{i+1} parries after index i, and exactly M-1-S_{i+1} before it.
  • So, it’s possible to parry attack i if and only if X - (M-1-S_{i+1}) \geq B_i.

These checks take \mathcal{O}(1) time once the P and S arrays are known; and as noted earlier both arrays can be computed in linear time.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (C++) 
// #include <bits/allocator.h>
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include "bits/stdc++.h"
using namespace std;
using ll = long long int;
mt19937_64 RNG(chrono::high_resolution_clock::now().time_since_epoch().count());

int main()
{
    ios::sync_with_stdio(false); cin.tie(0);

    int t; cin >> t;
    while (t--) {
        int n, x; cin >> n >> x;
        vector a(n, 0), b(n, 0);
        for (int &i : a) cin >> i;
        for (int &i : b) cin >> i;

        vector lim(n, 0);
        // lim[i] = maximum number of parries < i
        for (int i = n-1; i >= 0; --i) {
            lim[i] = x - a[i];
            if (i < n-1) lim[i] = min(lim[i], lim[i+1]);
        }

        int mx = 0, first = n;
        vector<int> pref(n, 0);
        for (int i = 0; i < n; ++i) {
            pref[i] = mx;
            if (x - mx >= b[i] and (i == n-1 or mx+1 <= lim[i+1])) {
                first = min(first, i);
                ++mx;
            }
        }

        // cout << mx << '\n';
        // continue;
        
        if (mx == 0) {
            cout << string(n, '0') << '\n';
            continue;
        }

        int cur = 0;
        vector suf(n, 0);
        for (int i = n-1; i >= 0; --i) {
            suf[i] = cur;
            if (b[i] <= x - mx + 1 + cur) ++cur;
        }

        for (int i = 0; i < n; ++i) {
            int after = suf[i];
            // mx - after - 1 before this
            if (i >= first and pref[i] >= mx - after - 1) {
                if (x - max(0, mx - after - 1) >= b[i]) cout << 1;
                else cout << 0;
            }
            else cout << 0;
        }
        cout << '\n';
    }
}
3 Likes