EQEXCH - Editorial

editorial
, ,
1

PROBLEM LINK:

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

Author: iceknight1093
Tester: kingmessi
Editorialist: iceknight1093

DIFFICULTY:

Cakewalk

PREREQUISITES:

None

PROBLEM:

A shop has K stones: each of them is either red or blue.
N trades will occur. The i-th trade asks for |A_i| stones of one color, and will pay using the same number of stones of the other color.

Is it possible to start with enough red/blue stones so that at any point of time, the number of stones of each color is always non-negative?

EXPLANATION:

The i-th trade was described as:

  • If A_i \gt 0, obtain A_i red stones but give out A_i blue stones.
  • If A_i \lt 0, obtain -A_i blue stones but give out -A_i red stones.

Observe that both trades in fact change the number of red and blue stones in the same way:
if we currently have R red stones and B blue stones, then after the trade we will have R+A_i red stones and B-A_i blue stones (this applies whether A_i is positive or negative.)

So, if we start with X red stones and K-X blue stones, after i trades we will have:

  • X+A_1+A_2+\ldots+A_i red stones, and
  • K-X-A_1-A_2-\ldots-A_i blue stones.

We want to check if there’s some value of X in [0, K] such that these two quantities are \ge 0 for all 1 \le i \le N.

To do this quickly, observe that only the maximum and minimum values of A_1 + \ldots + A_i across all i matter.
As for why:

  • Let MX denote the maximum value of A_1 + \ldots + A_i across all i.
    Let MN denote the minimum value of A_1 + \ldots + A_i across all i.
  • The minimum number of blue stones we’ll have at any point of time is K-X-MX, while the minimum number of red stones we’ll have is X+MN.

So, we need K-X-MX \ge 0 and X+MN \ge 0 to hold.

These two conditions together tell us that X \le K-MX and X \ge -MN must hold.
We also know that 0 \le X \le K must hold.
It’s now easy to check if any valid X satisfying these conditions holds:

  • First, certainly -MN \le K-MX must be true.
  • Then, K-MX \ge 0 must hold (otherwise X \le K - MX would force X \lt 0 which is bad.)
  • Similarly, -MN \le K must hold.
  • If these three conditions hold, then any X in the range [-MN, K-MX] is a valid choice of X.
  • That is, the answer is Yes if and only if
    0 \le -MN \le K-MX \le K

This gives a solution in \mathcal{O}(N) per test.

(Further, you may note that there’s no need to explicitly check for 0 \le -MN and K-MX \le K because these will always be true; given that MN \le 0 and MX \ge 0 are always true by taking the empty prefix with sum 0.)

Note that the constraints are small enough that simply trying every X \in [0, K] and simulating the process is also fast enough to solve the problem, if you don’t want the optimized solution described above.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    
    mn, mx = 0, 0
    sm = 0
    for i in range(n):
        sm += a[i]
        mn = min(mn, sm)
        mx = max(mx, sm)
    
    if -mn <= k-mx: print('Yes')
    else: print('No')
2 Likes