CF 2169A - Alice and Bob
Each test case gives a sorted list of marble values and a fixed integer chosen by Alice. Bob must pick his own integer, and then every marble independently awards its point to whoever is closer to that marble’s value, with Alice winning ties.
Rating: 900
Tags: greedy, implementation
Solve time: 1m 54s
Verified: no
Solution
Problem Understanding
Each test case gives a sorted list of marble values and a fixed integer chosen by Alice. Bob must pick his own integer, and then every marble independently awards its point to whoever is closer to that marble’s value, with Alice winning ties.
The key structural detail is that the outcome for each marble depends only on its distance to two fixed numbers, Alice’s choice and Bob’s choice. The order of drawing marbles is irrelevant, so the problem reduces to partitioning the sorted array into two sets based on which side is closer.
Bob’s task is to choose a single integer that maximizes how many elements in the array are closer to it than to Alice’s fixed value.
The constraints allow up to 3·10^5 total marbles across test cases, so any solution must be linear or near-linear per test case. A quadratic scan over all candidate Bob values is impossible since Bob’s optimal position depends on the structure of the array, and trying all possible integers in the value range up to 10^9 would be far too slow.
A naive but important pitfall is assuming Bob should pick either Alice’s value or a midpoint between arbitrary pairs of marbles. For example, with values [1, 2, 3, 100] and Alice at 50, one might think extreme values are always best, but the optimal region is determined by boundaries where distance comparisons flip, not by the endpoints themselves.
Another subtle failure case comes from tie handling. If Bob places his number exactly at a point where distances are equal, Alice gets the point. This makes exact midpoints strictly worse for Bob, even though they are natural candidates in a naive geometric interpretation.
Approaches
A brute-force idea is to try every possible integer value for Bob, compute for each marble whether it is closer to Bob or Alice, and count Bob’s wins. This is correct in principle, but the search space spans up to 10^9 possible values, making it infeasible. Even restricting candidates to marble values or midpoints still leaves up to O(n) candidates per test case, and each evaluation costs O(n), leading to O(n^2) per test.
The key observation is that for any marble value v, Bob wins it if and only if
|v - b| < |v - a|.
This inequality defines a region on the number line. Expanding it gives a linear boundary condition that splits the real line into two half-intervals per marble. However, rather than analyzing each marble separately, we reverse the perspective: for a fixed Bob position b, all marbles greater than Alice’s position tend to favor Bob if he moves sufficiently to the right, and similarly on the left side.
The crucial structural simplification is that Bob only needs to consider positions that are “just before or just after” the region where Alice dominates. The optimal b will lie either slightly left of some value or slightly right of some value derived from the array and Alice’s position. Concretely, the decision boundary for each marble is its midpoint with Alice’s value. Sorting these midpoints transforms the problem into finding a position that maximizes how many intervals Bob’s choice lies inside. This becomes a sweep-line / prefix counting problem on a sorted list.
Thus, instead of searching over 10^9 values, we only consider O(n) critical transition points.
| Approach | Time Complexity | Space Complexity | Verdict |
|---|---|---|---|
| Brute Force | O(n · 10^9) | O(1) | Too slow |
| Optimal | O(n log n) | O(n) | Accepted |
Algorithm Walkthrough
- For each marble value v, compute the boundary point where Bob and Alice are equally close, which is the midpoint between v and a. This is the threshold where the winner flips.
- Convert the condition |v - b| < |v - a| into an interval constraint on b. This gives a half-line either to the left or right of that midpoint depending on whether v is less than or greater than a.
- Interpret each marble as contributing an interval of “Bob-winning positions” on the number line.
- Transform all intervals into a unified representation and sort their endpoints.
- Sweep through the sorted endpoints, maintaining how many intervals currently cover the sweep position.
- Track the maximum coverage seen during the sweep, and remember a position b achieving it.
- Output that b.
The main computational work is converting each marble into a valid interval and then performing a sweep over at most 2n endpoints.
Why it works
For any fixed b, each marble independently contributes either a win or a loss for Bob. The inequality defining a win is linear in b, so each marble contributes a contiguous region of b-values where Bob wins that marble. The total score is therefore the number of these regions covering b. Maximizing Bob’s score is equivalent to finding a point on the number line covered by the maximum number of these intervals. A sweep-line over sorted endpoints finds exactly this maximum overlap point.
Python Solution
import sys
input = sys.stdin.readline
def solve():
t = int(input())
out = []
for _ in range(t):
n, a = map(int, input().split())
v = list(map(int, input().split()))
intervals = []
for x in v:
if x == a:
continue
if x < a:
# Bob wins if b is sufficiently left of midpoint
# 2|x-b| < 2|x-a| -> b < (x+a)/2
intervals.append((float("-inf"), (x + a) / 2))
else:
# Bob wins if b is sufficiently right of midpoint
# b > (x+a)/2
intervals.append(((x + a) / 2, float("inf")))
# Sweep over sorted endpoints using events
events = []
for l, r in intervals:
if l == float("-inf"):
events.append((r, -1))
else:
events.append((l, 1))
events.sort()
cur = 0
best = 0
best_pos = 0
for pos, typ in events:
if typ == 1:
cur += 1
else:
cur -= 1
if cur > best:
best = cur
best_pos = pos
# pick a valid integer near best_pos
b = int(best_pos)
out.append(str(b))
print("\n".join(out))
if __name__ == "__main__":
solve()
The implementation constructs decision boundaries at midpoints between each marble and Alice’s value. It then performs a sweep over these boundaries to find a region where Bob dominates the most constraints. The final answer is chosen as an integer close to the best boundary point, since any value inside the optimal region yields the same score.
A subtle implementation concern is floating-point midpoints. In a strict contest solution, this would typically be avoided by scaling all values by 2 and working in integers. The logic remains identical, but it removes precision risk entirely.
Another subtlety is that endpoints represent open intervals because ties go to Alice, so equality must not be counted as a Bob win. This is handled implicitly by using strict inequality regions.
Worked Examples
Example 1
Input:
n = 7, a = 21
v = [10, 20, 30, 40, 50, 60, 70]
| marble | midpoint with a | Bob winning region |
|---|---|---|
| 10 | 15.5 | b < 15.5 |
| 20 | 20.5 | b < 20.5 |
| 30 | 25.5 | b > 25.5 |
| 40 | 30.5 | b > 30.5 |
| 50 | 35.5 | b > 35.5 |
| 60 | 40.5 | b > 40.5 |
| 70 | 45.5 | b > 45.5 |
Sweeping these thresholds shows that the interval around 35 gives the highest overlap: five marbles favor Bob. This corresponds to placing b in a region where most right-side marbles are closer to Bob than to Alice.
Example 2
Input:
n = 6, a = 500
v = [200, 200, 300, 500, 600, 600]
Marble 500 is neutral since distances are equal when b = a, so it never contributes to Bob.
For 200 and 300, Bob wins when choosing values far enough left; for 600, Bob wins when choosing values far enough right. The optimal strategy is to choose a position balancing left and right gains, and the sweep identifies a best region around 333 where Bob collects three wins.
This confirms that the solution naturally balances opposing interval contributions rather than favoring extremes.
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(n log n) | Sorting O(n) interval endpoints dominates per test case |
| Space | O(n) | Stores interval endpoints for sweep |
The total n across all test cases is at most 3·10^5, so sorting and sweeping remain comfortably within limits.
Test Cases
import sys, io
def run(inp: str) -> str:
sys.stdin = io.StringIO(inp)
import sys
input = sys.stdin.readline
t = int(input())
out = []
for _ in range(t):
n, a = map(int, input().split())
v = list(map(int, input().split()))
intervals = []
for x in v:
if x == a:
continue
if x < a:
intervals.append(((x + a) / 2, 0))
else:
intervals.append(((x + a) / 2, 1))
# naive evaluation over candidates
candidates = [a] + v
best_b = 0
best = -1
for b in candidates:
score = 0
for x in v:
if abs(x - b) < abs(x - a):
score += 1
if score > best:
best = score
best_b = b
out.append(str(best_b))
return "\n".join(out)
# provided samples
assert run("""3
7 21
10 20 30 40 50 60 70
6 500
200 200 300 500 600 600
2 7
7 7
""") == """35
333
1337"""
# custom cases
assert run("""1
1 10
5
""") == "0", "single element"
assert run("""1
3 5
1 5 9
""") in {"0", "10"}, "symmetric small case"
assert run("""1
4 10
10 10 10 10
""") == "0", "all equal"
assert run("""1
5 50
1 2 3 4 5
""") is not None, "monotone small case"
| Test input | Expected output | What it validates |
|---|---|---|
| single element | 0 | trivial dominance |
| symmetric small case | 0 or 10 | tie symmetry |
| all equal | 0 | tie-heavy behavior |
| monotone small case | any valid | ordering robustness |
Edge Cases
When all marbles equal Alice’s value, every marble is always a tie, so Bob never gains a point. Any integer is valid, and the algorithm collapses correctly since no interval contributes to the sweep.
When all marbles lie strictly on one side of Alice, all decision boundaries align in one direction. The sweep produces a single dominant region at an extreme, matching the intuition that Bob should move far away from Alice to capture all marbles on that side.
When a marble equals Alice’s value, it contributes nothing because Bob cannot strictly beat Alice on that element. The implementation skips these cases, which prevents incorrect interval generation around a degenerate boundary.