PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: iceknight1093
Tester: sushil2006
Editorialist: iceknight1093
DIFFICULTY:
Cakewalk
PREREQUISITES:
None
PROBLEM:
There are N matches.
You get A_i coins for winning the i-th match and B_i coins for losing it.
It’s known that A_i \ge B_i for all i.
Find the maximum number of coins you can get, given that you must lose at least one match.
EXPLANATION:
The condition A_i \ge B_i for every i tells us that it’s never more profitable to lose than it is to win.
So, our absolute best-case scenario is when we win every single match.
However, this is explicitly prohibited.
Thus, it’s optimal for us to lose exactly one match.
(If we lose two or more matches, we can convert all but one loss to a victory, and our profit will not reduce.)
This gives an easy solution with \mathcal{O}(N^2) time complexity: iterate over the index of the match we’re losing, and then compute the number of coins we receive assuming this match is a loss and everything else is a win.
For the constraints, this is fast enough.
It’s possible (though not necessary here) to improve the solution to \mathcal{O}(N) time.
To do this, we first assume we win every match, giving us a score of
Now, if we decide to lose the i-th match, we get a “profit” of B_i - A_i compared to the above base score.
Since we want to lose exactly one match, clearly it’s optimal to choose whichever i maximizes B_i - A_i.
TIME COMPLEXITY:
\mathcal{O}(N) or \mathcal{O}(N^2) per testcase.
CODE:
Editorialist's code (PyPy3)
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
ans = sum(a)
add = b[0] - a[0]
for i in range(n): add = max(add, b[i] - a[i])
print(ans + add)