Author: Trung Nguyen
Tester and Editorialist: Alei Reyes
Problem Link
Difficulty
Cakewalk
PREREQUISITES:
Implementation
Problem
The penalty of an array is defined as the sum of its elements. Given two arrays, remove one element of each array to minimize its penalty. Which array will have the minimum penalty?
Explanation
Let X be an array containing the penalties of some player. The total penalty is the sum of elements of X, let’s denote it by sum(X). We want to remove one of the elements to minimize the sum of elements. Which element should we remove? Since elements are positive is always more convenient to remove the maximum element, let’s denote it by max(X).
Therefore, the best penaly for Alice is pa = sum(A) - max(A), and the best penalty for Bob is pb = sum(B) - max(B).
Now we have to check which of them has a better penalty. Namely if pa is smaller than pb, then Alice Winns. If pb is smaller than pa, then Bob Winns. Otherwise it is a draw.