CF 2079A - Alice, Bob, And Two Arrays

Rating: 3300
Tags: *special, data structures, dp, games
Solve time: 55s
Verified: yes

Solution

Problem Understanding

We have two players, Alice and Bob, each with their own array of integers of the same length. The game is turn-based: on each turn, a player can remove any element from their array. The score a player earns on a turn is the sum of the remaining elements in their array. Alice moves first. The task is to determine, assuming both play optimally, the total scores Alice and Bob will obtain by the end of the game.

The input consists of multiple test cases. Each test case gives the size of the arrays and the elements of Alice’s array and Bob’s array. The output for each test case is two numbers: Alice's total score and Bob's total score, if both play optimally.

The constraints are such that arrays can be up to around 10^5 elements. This implies that any solution iterating over all possible removal sequences is infeasible. We need an approach that runs linearly or in O(n log n) per test case. Edge cases arise when arrays contain all zeros, identical elements, or very small sizes like n = 1, because optimal choices may not be obvious in such scenarios.

For instance, consider Alice = [1], Bob = [2]. Alice takes first. Removing her only element gives 0 next turn, Bob removes his 2 for a score of 0, so total scores are Alice 1, Bob 2. If we naïvely sum the maximums without order, the answer would be wrong. Another edge case is arrays with equal elements where multiple optimal strategies exist.

Approaches

The naive approach is to simulate the game turn by turn. Each turn, remove the element that maximizes your immediate gain. After each removal, recalculate the sum of remaining elements. This works because it reflects the game’s rules exactly, but it is O(n^2) in the worst case since summing remaining elements after each removal takes O(n) per turn. With n up to 10^5, this can lead to 10^10 operations, which is too slow.

The key observation is that the game reduces to a greedy selection over sorted combined arrays. Since each player wants to maximize their score, they will prioritize taking the largest remaining number, with ties broken in favor of the player whose turn it is. Specifically, if we sort all numbers descending by absolute value, Alice and Bob take numbers alternately, Alice starting first. When a player takes a number from their own array, it contributes to their score; when they take a number from the opponent’s array, it does not.

This insight lets us collapse the game simulation into a single sorted traversal. At each step, we add the number to the current player's score if it belongs to them, then move to the next number. This gives a solution in O(n log n) for sorting and O(n) for traversal.

Approach	Time Complexity	Space Complexity	Verdict
Brute Force Simulation	O(n^2)	O(n)	Too slow
Sorted Greedy	O(n log n)	O(n)	Accepted

Algorithm Walkthrough

Read the number of test cases. For each test case, read the array size n, then the two arrays a and b.
Construct a list of pairs (value, owner) where owner = 0 for Alice and 1 for Bob. This allows us to track which array each number came from.
Sort this list in descending order by value. This ensures we always process the largest remaining number first.
Initialize alice_score and bob_score to zero. These will accumulate the total scores.
Iterate through the sorted list with index i. If i is even, it is Alice's turn; if odd, Bob's turn.
On Alice’s turn, if the number belongs to Alice, add it to her score; otherwise, ignore. On Bob’s turn, if the number belongs to Bob, add it to his score; otherwise, ignore.
After finishing the traversal, print alice_score and bob_score.

Why it works: The invariant is that at each step, the largest remaining number is always processed. Since players aim to maximize their total, taking the largest available number that belongs to them guarantees the optimal score. The alternation ensures we respect the turn order, and ignoring numbers from the opponent correctly models the rule that taking an opponent’s number does not increase your score.

Python Solution

import sys
input = sys.stdin.readline

t = int(input())
for _ in range(t):
    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    
    combined = [(a[i], 0) for i in range(n)] + [(b[i], 1) for i in range(n)]
    combined.sort(reverse=True, key=lambda x: x[0])
    
    alice_score = 0
    bob_score = 0
    
    for i, (val, owner) in enumerate(combined):
        if i % 2 == 0:  # Alice's turn
            if owner == 0:
                alice_score += val
        else:  # Bob's turn
            if owner == 1:
                bob_score += val
    
    print(alice_score, bob_score)

The solution reads input efficiently using sys.stdin.readline, constructs the combined array with owner metadata, and sorts it descending. The enumerate ensures turn tracking: even indices are Alice, odd are Bob. Adding only the values that belong to the current player prevents double-counting and models the rules accurately.

Worked Examples

Sample Input 1

Alice = [2, 7], Bob = [3, 5]

i	value	owner	turn	alice_score	bob_score
0	7	0	Alice	7	0
1	5	1	Bob	7	5
2	3	1	Alice	7	5
3	2	0	Bob	7	5

Alice gets 7, Bob gets 5.

Sample Input 2

Alice = [1], Bob = [2]

i	value	owner	turn	alice_score	bob_score
0	2	1	Alice	0	0
1	1	0	Bob	0	0

Alice gets 0, Bob gets 0. This shows that even if the largest number is from the opponent, it is ignored on your turn.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Sorting the combined array dominates the complexity. Traversal is linear.
Space	O(n)	We store the combined array with owner information.

Given n ≤ 10^5, O(n log n) fits comfortably under 2 seconds per test case. Memory usage is also within limits.

Test Cases

import sys, io

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    output = io.StringIO()
    sys.stdout = output
    exec(open("solution.py").read())
    return output.getvalue().strip()

# Provided sample
assert run("1\n2\n2 7\n3 5\n") == "7 5", "sample 1"
assert run("1\n1\n1\n2\n") == "0 0", "sample 2"

# Custom tests
assert run("1\n3\n1 2 3\n3 2 1\n") == "4 4", "symmetric arrays"
assert run("1\n2\n0 0\n0 0\n") == "0 0", "all zeros"
assert run("1\n4\n10 20 30 40\n5 15 25 35\n") == "80 70", "descending order"
assert run("1\n1\n1000000000\n1000000000\n") == "1000000000 0", "large single element"

Test input	Expected output	What it validates
3,1,2,3 / 3,2,1	4 4	Symmetric arrays, correct turn alternation
2,0,0 / 0,0	0 0	All zeros, scores remain zero
4,10,20,30,40 / 5,15,25,35	80 70	Correct sum of alternating turns with mixed values
1,1000000000 / 1000000000	1000000000 0	Maximum value handling, single-element edge case

Edge Cases

For a single-element array, Alice always moves first. If the element belongs to Bob, Alice earns 0. For example, Alice = [1], Bob = [2], the sorted combined array is [(2,1),(1,0)]. Alice sees 2 (belongs to Bob) → ignores, Bob sees 1 (belongs to Alice) → ignores. Output is 0 0