MAXADD - Editorial

editorial
, , ,
1

PROBLEM LINK:

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

Author: raysh07
Tester: satyam_343
Editorialist: iceknight1093

DIFFICULTY:

Easy

PREREQUISITES:

None

PROBLEM:

You’re given two arrays A and B, both of length N.
Define f(X) as follows:

  • Let Y = X.
  • For i = 1, 2, \ldots, N, set Y \gets \max(Y+B_i, A_i).
  • f(X) is the final value of Y.

Given M, compute f(1) + f(2) + \ldots + f(M).

EXPLANATION:

Let’s define f_i(X) to be the final value of Y, assuming we’ve already processed indices 1, 2, \ldots, i and the current value is Y = X.
The value we’re interested in is then f_0(X).

f_i(X) has a pretty simple recurrence: f_i(X) = f_{i+1}(\max(X + B_{i+1}, A_{i+1})).
In particular, note that for all “small enough” values of X, we have f_i(X) = f_{i+1}(A_{i+1}), while all “large” values of X will satisfy f_i(X) = f_{i+1}(X + B_{i+1}).

Let’s try to use this observation to solve the problem.

Let’s move left to right.
Initially, we have every possible “input” X from 1 to M.
When processing i = 1,

  • All X for which X+B_1 \le A_1 will be “pushed” to A_1.
    This is all X for which X \le A_1 - B_1.
  • Everything else will have their values increased by B_1 instead.
  • So, we’ll have the following values:
    • For each X such that A_1 - B_1 \lt X \le M, one copy of X + B_1.
      This corresponds to one copy of each element in the range [A_1+1, M+B_1].
    • For each X such that 1 \le A_1 - B_1 \le X, one copy of A_1.
      This corresponds to \max(0, A_1 - B_1) copies of A_1.

Next, let’s look at i = 2.
Again,

  • All existing elements with X \le A_2 - B_2 will be “pushed” to A_2.
  • Everything else that’s large enough will be increased by B_2.

However, note that after processing i = 1, our inputs currently lie in [A_1, M + B_1].
Moreover, there’s exactly one copy of each input in [A_1+1, M+B_1], but several possible copies of A_1.
It’s easy to see that after processing i = 2, our resulting values will end up lying in [\max(A_1, A_2), M+B_1+B_2].
Further, yet again, every “large enough” value will have only a single copy, and only the lowest element will have multiple copies.

At each index, this will continue to be the case: there will be one copy each of “large” elements, and several copies of a single small element.

That is, after processing all the indices i = 1, 2, \ldots, N, we’ll end up with some contiguous range [L, R] where:

  • We have one copy of each of L+1, L+2, \ldots, R
  • Everything else will be bunched up at L.

After making the above observation, note that finding L and R is not too hard.

R is simply the value of f(M), while L will be the value of f(1).
Once L and R are known, computing the answer is simple.
Let K = R-L be the length of the range [L+1, R], i.e. the number of elements with only one copy.
Then, the answer is

(L+1) + (L+2) + \ldots + R + (M - K)\cdot L

since every element other than those that end up in [L+1, R] will end up at L instead; and there are M - K such elements.

Computing f(1) and f(M) can be done in \mathcal{O}(N) each with direct simulation.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (PyPy3) 
def psum(n): # 1+2+...+n
    return n*(n+1)//2
for _ in range(int(input())):
    n, m = map(int, input().split())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    
    f1, fm = 1, m
    for i in range(n):
        f1 = max(b[i] + f1, a[i])
        fm = max(b[i] + fm, a[i])
    
    k = fm - f1
    print(psum(fm) - psum(f1) + f1*(m - k))
1 Like