Overview

Given \(N\) employees, select a non-empty subset to maximize the minimum of the total programming ability and the total design ability (overall strength).

Analysis

Key Insight: Selecting Everyone is Optimal

The most important observation in this problem is that “it is always optimal to include everyone in the team.”

This is because when considering adding a new employee \(j\) to the current team \(S\), the following inequality holds:

\[\min\left(\sum_{i \in S} A_i + A_j,\ \sum_{i \in S} B_i + B_j\right) \geq \min\left(\sum_{i \in S} A_i,\ \sum_{i \in S} B_i\right) + \min(A_j, B_j)\]

From the constraints, \(A_j \geq 1\) and \(B_j \geq 1\), so \(\min(A_j, B_j) \geq 1 > 0\).

In other words, adding an employee always increases the overall strength.

Verification with a Concrete Example

For example, suppose there are 3 employees: - Employee 1: \(A_1 = 5, B_1 = 3\) - Employee 2: \(A_2 = 2, B_2 = 7\) - Employee 3: \(A_3 = 4, B_3 = 1\)

Selecting everyone: programming total \(= 11\), design total \(= 11\), overall strength \(= \min(11, 11) = 11\)

If we exclude employee 3: programming total \(= 7\), design total \(= 10\), overall strength \(= \min(7, 10) = 7\)

We can see that including everyone is better.

Why a Brute-Force Approach is Unnecessary

Trying all \(2^N - 1\) subsets would take exponential time, but from the above analysis, we only need to select everyone, so it suffices to simply compute the totals.

Algorithm

1. Compute the total programming ability of all employees: \(\text{total\_a} = \sum_{i=1}^{N} A_i\)
2. Compute the total design ability of all employees: \(\text{total\_b} = \sum_{i=1}^{N} B_i\)
3. Output \(\min(\text{total\_a}, \text{total\_b})\)

Complexity

• Time complexity: \(O(N)\) (just a single pass over all employees’ ability values)
• Space complexity: \(O(1)\) (only variables to hold the totals)

Implementation Notes

• Since \(A_i\) can be up to \(10^9\) and \(N\) can be up to \(2 \times 10^5\), the total can be as large as approximately \(2 \times 10^{14}\). In Python, there is no need to worry about integer overflow, but in C++ and similar languages, you need to use long long.

• There is no need to store each employee’s information in an array; it is sufficient to accumulate the values while reading input.

  Source Code

import sys
input = sys.stdin.readline

def main():
    N = int(input())
    total_a = 0
    total_b = 0
    for _ in range(N):
        a, b = map(int, input().split())
        total_a += a
        total_b += b
    print(min(total_a, total_b))

main()

---

This editorial was generated by claude4.6opus-thinking.