CO92JUDG - EDITORIAL

Author: Trung Nguyen
Tester and Editorialist: Alei Reyes

Problem Link

Practice

Contest

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.

Implementation

Author’s Solution

Tester’s and Editorialist’s Solution

1 Like