PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: iceknight1093
Tester: sushil2006
Editorialist: iceknight1093
DIFFICULTY:
Simple
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.
Find the maximum number of attacks that can be parried, while still being able to either dodge or parry each of the N attacks.
EXPLANATION:
First, let’s look at possibility.
Just before processing the i-th attack, we definitely need our skill level to be at least A_i; since if it’s any lower we’ll be unable to even dodge, and hence lose the fight.
Since we start with a skill level of X, and each parry reduces it by 1, this puts an upper bound on the number of parries we can perform: among the first i-1 attacks, we can parry at most X - A_i attacks: any more and we’ll end up below A_i before reaching i.
On the other hand, as long as we follow all these restrictions we’ll definitely be able to at least dodge every attack; so we no longer need to worry about failing: we can focus on maximizing parries.
A simple greedy algorithm should come to mind now: for each i from 1 to N, if it’s possible to parry the i-th attack without breaking any of the prefix restrictions, do so.
It turns out that this greedy is in fact optimal!
Proof
The proof is just as simple as the algorithm itself.
Let i_1, i_2, i_3, \ldots be the indices of attacks parried by the greedy algorithm.
Let j_1, j_2, \ldots be the indices of attacks parried by some optimal solution.First, note that j_1 \lt i_1 is impossible: by nature of the greedy, i_1 is the first attack that can be parried at all.
So, we have j_1 \geq i_1.Now, suppose j_1 \gt i_1.
What happens if we replace j_1 with i_1? That is, instead of parrying attack j_1, we parry attack i_1 instead.
It’s easy to see that this is always valid: obviously there’s no contradiction when looking at indices \lt i_1 or \gt j_1, so only the range [i_1+1, j_1] matters.
But we’re not parrying anything extra in that range anyway since j_2 \gt j_1; and since i_1 was a valid first parry due to the greedy choosing it, certainly no constraints can be broken if that’s the only parry made.So, we can replace j_1 with i_1 in the optimal solution, and it remains optimal.
Once we have i_1 = j_1, simply apply the same argument to i_2 and j_2, i_3 and j_3, and so on.
By doing this repeatedly, we’ll end up in a situation where the optimal solution matches the greedy one, meaning the greedy solution is optimal as claimed.
The only thing remaining is actually implementing this fast.
To do that, let’s analyze what we’re actually doing.
Let X_0 denote the initial value of X, and X_c denote the current value of X (after some parries).
For each i from 1 to N, we parry the i-th attack if:
- Xc \geq B_i, and
- X_c-1 \geq A_j for every j \gt i.
That is, we need to ensure that every restriction after i remains satisfied if we perform this parry.
The second check is the potentially slow one.
To optimize it, note that we only really care about the largest value of A_j across all j \gt i.
If we’re able to satisfy the this restriction, we’ll definitely satisfy all the other restrictions too.
So, all that needs to be done is to precompute the largest A_j in each suffix (which is easy to do in linear time, just iterate in reverse); after which performing the check takes constant time.
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Editorialist's code (PyPy3)
for _ in range(int(input())):
n, x = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
mx = [0]*(n+1)
for i in range(n): mx[i] = a[i]
for i in reversed(range(n-1)): mx[i] = max(mx[i], mx[i+1])
ans = 0
for i in range(n):
if x - ans >= b[i] and x - ans - 1 >= mx[i+1]:
ans += 1
print(ans)
