CF 1091B - New Year and the Treasure Geolocation

Rating: 1200
Tags: brute force, constructive algorithms, greedy, implementation
Solve time: 1m 18s
Verified: yes

Solution

Problem Understanding

We are given a set of obelisks on a 2D plane and a set of clues that indicate vectors from obelisks to a hidden treasure. Each obelisk has exactly one clue, but the mapping is scrambled, so we do not know which clue belongs to which obelisk. Each clue is a vector, and when added to its obelisk's coordinates, it points exactly to the treasure. The goal is to determine the coordinates of the treasure, without having to find the permutation of clues to obelisks.

The input size allows up to 1000 obelisks and 1000 clues. Each coordinate can be as large as 10^6 in magnitude, and the clues can go up to ±2×10^6. The time limit is 2 seconds. For n = 1000, a brute-force check of all permutations is impossible, because n! is astronomically large. This rules out solutions that attempt to test every possible pairing directly.

A naive mistake would be assuming the first clue belongs to the first obelisk and computing the treasure as T = obelisk + clue. This fails because the clues may be scrambled. For example, if n = 2, obelisks at (0,0) and (1,1) and clues (1,0) and (0,1), assigning clues in order gives T = (1,0) for the first obelisk and T = (1,2) for the second obelisk, which is inconsistent. The correct solution swaps the clues, giving T = (0+0,0+1) = (1,1), consistent for both obelisks.

We also need to handle negative coordinates and large values carefully to avoid overflow in languages with bounded integers. In Python this is safe, but in C++ or Java one would need long long.

Approaches

The brute-force approach is to try all permutations of clues mapped to obelisks. For each permutation, we compute the treasure coordinates for all pairs and check if they are identical. While this is correct, its complexity is O(n!) which is infeasible even for n = 10.

The key insight to speed this up comes from linearity. If the treasure is T, then the sum of all treasure coordinates over all obelisks equals the sum of obelisk coordinates plus the sum of clue vectors, because each clue is used exactly once. Formally:

T * n = sum_over_obelisks(x_i, y_i) + sum_over_clues(a_j, b_j)

From this, we can immediately compute the treasure coordinates as:

T_x = (sum of all x_i + sum of all a_j) / n
T_y = (sum of all y_i + sum of all b_j) / n

Since the problem guarantees an integer solution, division by n will yield integers.

This approach works because addition is commutative: the sum of clues assigned to obelisks does not depend on the permutation. This reduces the problem from factorial complexity to linear time.

Approach	Time Complexity	Space Complexity	Verdict
Brute Force	O(n!)	O(n)	Too slow
Sum-based (Optimal)	O(n)	O(1)	Accepted

Algorithm Walkthrough

Read n, the number of obelisks and clues. Initialize accumulators for sums of x, y coordinates of obelisks and sums of a, b vectors from clues.
Loop over the n obelisks. For each obelisk, read its coordinates (x_i, y_i) and add x_i to the x-sum and y_i to the y-sum. This collects the total contribution of all obelisk positions.
Loop over the n clues. For each clue vector (a_j, b_j), add a_j to a-sum and b_j to b-sum. This collects the total contribution of all clue vectors.
Compute the treasure coordinates as T_x = (x-sum + a-sum) // n and T_y = (y-sum + b-sum) // n. Integer division works because the problem guarantees an integer solution.
Output T_x and T_y.

Why it works: The sum of all treasure coordinates over all obelisks must equal the sum of all obelisks plus all clues. Since there is exactly one clue per obelisk, this sum is independent of the permutation. Dividing by n gives the correct treasure coordinates.

Python Solution

import sys
input = sys.stdin.readline

n = int(input())
ob_x_sum = 0
ob_y_sum = 0

for _ in range(n):
    x, y = map(int, input().split())
    ob_x_sum += x
    ob_y_sum += y

clue_x_sum = 0
clue_y_sum = 0

for _ in range(n):
    a, b = map(int, input().split())
    clue_x_sum += a
    clue_y_sum += b

T_x = (ob_x_sum + clue_x_sum) // n
T_y = (ob_y_sum + clue_y_sum) // n

print(T_x, T_y)

The solution first accumulates sums for obelisks and clues separately. We could have accumulated into a single pair of variables, but separating them makes the logic clearer and matches the algorithm. Integer division is safe because the problem guarantees the treasure coordinates are integers. Python automatically handles large integers, so no overflow concerns arise.

Worked Examples

Sample 1:

obelisks	x-sum	y-sum	clues	a-sum	b-sum	T_x	T_y
(2,5),(-6,4)	-4	9	(7,-2),(-1,-3)	6	-5	(-4+6)//2=1	(9-5)//2=2

Explanation: The sum of obelisk x-coordinates is -4, clues sum to 6, total 2, divided by 2 is 1. Similarly for y: 9-5=4, divided by 2 is 2. This matches the correct treasure at (1,2).

Sample 2:

obelisks	x-sum	y-sum	clues	a-sum	b-sum	T_x	T_y
(2,3),(4,5),(6,7)	12	15	(1,1),(2,2),(3,3)	6	6	(12+6)//3=6	(15+6)//3=7

This confirms the algorithm correctly handles more than 2 obelisks and arbitrary vectors.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each obelisk and clue is read and summed exactly once
Space	O(1)	Only four integer accumulators are needed, independent of n

With n ≤ 1000, the total number of operations is roughly 2n = 2000, far below any performance limit. Memory use is minimal, and Python handles the integer arithmetic safely.

Test Cases

import sys, io

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    n = int(input())
    ob_x_sum = ob_y_sum = 0
    for _ in range(n):
        x, y = map(int, input().split())
        ob_x_sum += x
        ob_y_sum += y
    clue_x_sum = clue_y_sum = 0
    for _ in range(n):
        a, b = map(int, input().split())
        clue_x_sum += a
        clue_y_sum += b
    T_x = (ob_x_sum + clue_x_sum) // n
    T_y = (ob_y_sum + clue_y_sum) // n
    return f"{T_x} {T_y}"

# Provided samples
assert run("2\n2 5\n-6 4\n7 -2\n-1 -3\n") == "1 2", "sample 1"

# Minimum input
assert run("1\n0 0\n0 0\n") == "0 0", "minimum input"

# All positive coordinates
assert run("3\n1 2\n3 4\n5 6\n1 1\n2 2\n3 3\n") == "6 7", "positive coordinates"

# Negative coordinates
assert run("2\n-1 -1\n-2 -3\n1 0\n2 1\n") == "0 -1", "negative coordinates"

# Maximum values
assert run("2\n1000000 1000000\n-1000000 -1000000\n2000000 2000000\n-2000000 -2000000\n") == "500000 500000", "large values"

Test input	Expected output	What it validates
1 obelisk	0 0	minimal input edge case
3 obelisks, all positive	6 7	sum-based computation correctness
2 obelisks, negative	0 -1	handles negative coordinates
2 obelisks, large	500000 500000	handles large coordinates without overflow