PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: iceknight1093
Tester: raysh07
Editorialist: iceknight1093
DIFFICULTY:
Simple
PREREQUISITES:
None
PROBLEM:
You are given an array A. You can delete at most one of its elements.
Is it possible for the resulting array to have all non-negative prefix sums?
EXPLANATION:
There are a couple of different ways to solve this problem, but here’s a fairly simple one.
Let i be the smallest index such that A_1 + \ldots + A_i \lt 0.
This i can be found by simply scanning the array from left to right, and maintaining a running sum.
(Note that if no such i exists, then the array is already good and nothing needs to be done; so we assume such an i does exist.)
Now that we have i, observe that if we delete an element after index i, the resulting array cannot be good; because A_1 + \ldots + A_i will remain negative.
So, we must delete an element from some index in [1, i].
Which one to delete?
Of course, the smallest value!
That is, let m = \min(A_1, \ldots, A_i), and then delete one copy of m from this prefix (if there are many copies, it doesn’t matter which one we delete.)
Note in particular that m must be negative (since the overall sum is negative), so what we’re doing is removing the “most negative” value from the prefix; which in turn will cause all the other sums to increase in value.
After deleting m, simply check if the resulting array is good, which is trivial to do in linear time.
If this works, great - the answer is Yes. If not, the answer is No.
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Editorialist's code (PyPy3)
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
mn, sm, flag = 0, 0, 0
for x in a:
if flag == 1:
sm += x
if sm < 0:
print('No')
break
else:
sm += x
mn = min(mn, x)
if sm < 0:
sm -= mn
flag = 1
else:
print('Yes')