CF 958E1 - Guard Duty (easy)

Rating: 1600
Tags: brute force, geometry, greedy, math
Solve time: 39s
Verified: yes

Solution

Problem Understanding

We are given two small point sets in the plane, one representing Rebel ships and the other representing bases. Each ship must be assigned to exactly one base, and each base must also receive exactly one ship, so the assignment is a bijection between the two sets. Once a pairing is chosen, we draw straight line segments between matched pairs, and we require that no two of these segments intersect anywhere except possibly at endpoints.

The task is to determine whether such a non-intersecting perfect matching exists.

The crucial constraint is that both sets have size at most 10. This immediately rules out anything like geometric flow or heavy combinatorics, and strongly suggests that exponential search over permutations is viable. With 10 points, the number of bijections is 10! which is about 3.6 million, and each candidate matching can be checked in O(n²) or O(n log n), which is still feasible.

The geometric constraints introduce subtle edge cases. Since no three points are collinear, we avoid degeneracies where intersection tests become ambiguous, but we still must handle cases where segments share endpoints or cross in their interiors.

A naive but tempting mistake is to assume that sorting by x or y coordinate and matching greedily preserves planarity. This fails when local choices force crossings later. Another incorrect idea is to match nearest neighbors, which can easily create crossings even in very small configurations.

For example, consider four points forming a convex quadrilateral, alternating between ships and bases. A greedy pairing by closest distance may produce diagonals that cross, even though a non-crossing matching exists along the boundary.

Approaches

The brute-force idea is to try every possible assignment of ships to bases. For each permutation of bases assigned to ships, we construct the set of line segments and check whether any two segments intersect. If we find even one valid assignment, we return Yes.

This is correct because every valid solution is a permutation of the bases, so exhaustive search covers all possibilities. The bottleneck is factorial growth: for R = B = 10, we test up to 10! assignments, and each requires O(n²) intersection checks, leading to roughly 3.6 million times 100 checks, which is borderline but acceptable in optimized Python only if pruning is used.

However, we can do better by noticing that the structure is purely combinatorial and the geometry is only used to validate crossings. Since the graph size is tiny, the key improvement is to integrate the intersection constraint incrementally. Instead of checking full permutations, we build the matching one ship at a time and reject partial assignments immediately if a crossing is created. This converts brute-force permutation enumeration into backtracking with pruning.

The observation that makes pruning effective is that a crossing can be detected locally: when we add a new segment, it only needs to be checked against already chosen segments.

Approach	Time Complexity	Space Complexity	Verdict
Brute Force permutations	O(n! · n²)	O(n)	Too slow
Backtracking with pruning	O(n! · n) worst-case	O(n)	Accepted

Algorithm Walkthrough

Treat ships as fixed in order and assign bases via permutation generation, but construct assignments incrementally rather than enumerating full permutations upfront. This allows early rejection.
Maintain a list of already used bases and the segments formed so far. Each segment connects a ship to its assigned base.
When trying to assign a base to the next ship, check whether the new segment intersects any previously created segment.
Two segments (a, b) and (c, d) intersect if and only if the orientations satisfy the standard segment intersection conditions. Because no three points are collinear, strict orientation tests are sufficient without handling collinear overlap cases.
If the new segment does not intersect any existing segment, proceed recursively to the next ship.
If all ships are assigned successfully, return success immediately.
If no assignment leads to a complete valid matching, return failure.

Why it works

At any stage of the recursion, the partial matching represents a set of non-intersecting segments. If a new segment intersects any existing one, no extension of this partial assignment can fix that crossing because segments are fixed geometric objects. Therefore pruning such states cannot eliminate a valid solution. Conversely, any valid full matching can be built step by step without ever creating an intersection, so it will survive all pruning steps.

Python Solution

import sys
input = sys.stdin.readline

def orient(ax, ay, bx, by, cx, cy):
    return (bx - ax) * (cy - ay) - (by - ay) * (cx - ax)

def intersect(a, b, c, d):
    ax, ay = a
    bx, by = b
    cx, cy = c
    dx, dy = d

    o1 = orient(ax, ay, bx, by, cx, cy)
    o2 = orient(ax, ay, bx, by, dx, dy)
    o3 = orient(cx, cy, dx, dy, ax, ay)
    o4 = orient(cx, cy, dx, dy, bx, by)

    return (o1 * o2 < 0) and (o3 * o4 < 0)

def solve():
    R, B = map(int, input().split())
    ships = [tuple(map(int, input().split())) for _ in range(R)]
    bases = [tuple(map(int, input().split())) for _ in range(B)]

    if R != B:
        print("No")
        return

    n = R
    used = [False] * n
    match = [-1] * n

    sys.setrecursionlimit(1000000)

    def dfs(i, segs):
        if i == n:
            return True

        sx, sy = ships[i]

        for j in range(n):
            if used[j]:
                continue

            ok = True
            for (a, b) in segs:
                if intersect(ships[a], bases[b], (sx, sy), bases[j]):
                    ok = False
                    break

            if not ok:
                continue

            used[j] = True
            segs.append((i, j))

            if dfs(i + 1, segs):
                return True

            segs.pop()
            used[j] = False

        return False

    print("Yes" if dfs(0, []) else "No")

if __name__ == "__main__":
    solve()

The core of the solution is the DFS over ship indices, assigning each ship a unique base. The used array ensures we maintain a bijection.

The intersect function encodes the standard segment intersection test using orientation (cross product signs). Because the input guarantees no three collinear points, we only need strict sign comparisons.

The recursion explores assignments in lexicographic order over bases. Each time we assign a base, we validate against all previously chosen segments to ensure no crossing is introduced. This incremental validation is what keeps the search small in practice.

A subtle point is that segments are stored as index pairs rather than coordinates, which avoids repeated coordinate copying and keeps intersection checks consistent with the current partial matching.

Worked Examples

Consider the sample input.

Example 1

Input:

Ships