IOAI Training: Learn AI by solving problems

J. Dividing the Stars

Cette page donne toute la méthode. Lisez-la une fois que vous avez cherché.

Métrique: valid line on hidden tests
Évaluée sur: self-generated tests (official tests are hidden)
Notre score: 1740/1740 random instances valid
Niveau attendu: a valid line on every hidden test

Niveau attendu atteint

Nous avons résolu l'épreuve nous-mêmes : téléchargé les données, mené les expériences et mesuré le score ci-dessous. L'énoncé et les données appartiennent à leurs organisateurs. Cette correction est rédigée en anglais.

The problem in brief

The plane holds $n$ neutron stars and $n$ giant stars ( $1 < n < 10^5$ , real coordinates in $(0, 10^6)$ , no three stars collinear). You must output a line $y = ax + b$ that passes through exactly one neutron star and one giant star and leaves, in one of its two open half-planes, as many neutron stars as giant stars. The statement guarantees such a non-vertical line exists. This is a computational-geometry warm-up hidden in an AI olympiad: the tools (signed balances, sorting by angle, a discrete intermediate value argument) are the same ones behind linear classifiers and ROC sweeps.

How you are scored

A stdin/stdout program with a 1-second limit. Many lines are valid, so the judge must check your line rather than compare it with one reference answer; the official tests and checker are hidden. We therefore validate our program with an exact (rational arithmetic) checker on 1 740 random instances and time it on the largest size.

First look: one side balanced means both sides balanced

The line goes through one neutron and one giant star, so the remaining $2n-2$ stars contain $n-1$ of each kind. If one open half-plane holds $k$ neutrons and $k$ giants, the other holds $n-1-k$ of each. So "one side balanced" is the same as "both sides balanced": we are looking for a halving line between the two colours, a discrete cousin of the ham-sandwich theorem.

A brute force tries all $n^2$ pairs and counts both sides in $O(n)$ : $O(n^3)$ , hopeless for $n = 10^5$ (and even $O(n^2)$ is too slow in 1 second). We need a structure that tells us where to look.

The key idea

Give each neutron star the value $+1$ and each giant star $-1$ . Pick a star $P$ on the boundary of the cloud, for example the leftmost one (smallest $x$ , ties broken by smallest $y$ ). Because $P$ is extreme, all other stars lie in a half-plane to its right, so their directions seen from $P$ span less than a half-turn and can be sorted by angle, equivalently by slope $(y_i - y_P)/(x_i - x_P)$ .

Now sweep a ray around $P$ from "straight down" to "straight up" and keep a running balance. Say $P$ is a neutron star (otherwise swap the roles of the colours), and define

B_k = \sum_{j \le k} v_j, \qquad v_j = \begin{cases} +1 & \text{same colour as } P \\ -1 & \text{other colour} \end{cases}

over the first $k$ stars in angular order. Two facts:

$B_0 = 0$ , and $B_{2n-1} = (n-1) - n = -1$ , because apart from $P$ there are $n-1$ stars of its colour and $n$ of the other.
The balance moves by steps of $\pm 1$ .

A walk that starts at $0$ , ends at $-1$ and moves by single steps must at some moment step from $0$ down to $-1$ . Let $Q$ be the star responsible for that step. Then:

$Q$ has value $-1$ : it is of the other colour, so line $PQ$ joins a neutron and a giant, as required.
The stars before $Q$ in the angular order have balance $B = 0$ : equally many of each colour.
Since all stars sit within a half-turn around $P$ , the stars before $Q$ are exactly the stars strictly on one side of line $PQ$ (no three collinear, so nobody lies on it).

So $PQ$ is a valid answer, and we have also proved that one always exists through any extreme star. This "start at 0, end at $-1$ , steps of size 1, hence a crossing" is the discrete intermediate value theorem, and it is worth recognising: the same argument proves the existence of balanced splits in many olympiad problems.

Left: 9 neutron and 9 giant stars; the leftmost star P is circled, the others are numbered in the order a ray rotating around P meets them, and the answer line PQ is drawn in black: stars 1 to 10 on its lower side are 5 neutrons and 5 giants. Right: the running balance along the sweep starts at 0, wanders, and first steps from 0 to -1 at star 11, which is Q.

Why not a vertical answer?

The output format $y = ax + b$ cannot express a vertical line. With the leftmost pivot, every other star has $x_i > x_P$ , except possibly one star with the same $x$ (two points can share an $x$ , three cannot since they would be collinear). That star comes last in the order (slope $+\infty$ ). Our program lists every valid $Q$ for the pivot (all steps $0 \to -1$ , not only the first) and keeps the first one with $x_Q \ne x_P$ ; in the very unlikely case all of them are vertical, it repeats the sweep from the rightmost, lowest and highest stars, obtained by negating or swapping the coordinates. In 1 740 random tests (with integer coordinates, where equal $x$ values are frequent) a non-vertical answer was always found.

The full solution

Read the $2n$ stars, with value $+1$ for the first $n$ and $-1$ for the last $n$ .
Pivot $P$ = lexicographically smallest $(x, y)$ .
Sort the others by slope from $P$ (vertical direction = $+\infty$ ), multiply the values by $P$ 's value, take prefix sums.
Valid $Q$ : value $-1$ and prefix balance $0$ just before it. Output the line through $P$ and $Q$ .

The core, vectorised with NumPy so it runs in about 0.1 s for $n = 10^5$ :

p = np.lexsort((Y, X))[0]                         # leftmost pivot
others = np.delete(np.arange(len(X)), p)
dx, dy = X[others] - X[p], Y[others] - Y[p]       # dx >= 0
slope = np.where(dx > 0, dy / np.where(dx > 0, dx, 1), np.inf)
order = others[np.argsort(slope)]
v = s[order] * s[p]                               # +1 same colour as P
before = np.concatenate(([0], np.cumsum(v)[:-1])) # balance before each star
good = order[(v == -1) & (before == 0)]           # valid partners Q

Then $a = (y_Q - y_P)/(x_Q - x_P)$ and $b = y_P - a x_P$ , printed with 12 significant digits.

A note on precision: sorting by floating-point slopes can misorder two stars that are almost collinear with $P$ . A fully robust version compares directions with the exact cross product $\Delta x_i \Delta y_j - \Delta y_i \Delta x_j$ (integer or rational arithmetic); the self-test uses exact rational arithmetic in the checker, and with coordinates below $10^6$ the float version passed every test.

Results

approach	complexity	result
brute force over all neutron-giant pairs, count both sides	$O(n^3)$	correct but far too slow for $n = 10^5$
angular sweep around the leftmost star, prefix balance	$O(n \log n)$	1 740 / 1 740 random instances verified exactly; 0.11 s for $n = 99\,999$
same, but pivot taken at a star inside the cloud	n/a	wrong: directions span a full turn, "before $Q$ " is no longer one side of the line
same, but keep the first $0 \to -1$ step only	$O(n \log n)$	correct except when that partner is directly above $P$ (vertical line not printable); enumerate all steps

What to remember

Turn the geometry into a 1D walk. Around an extreme point, "one side of a line" becomes "a prefix of a sorted list", and counting becomes a prefix sum.
Discrete intermediate value theorem: a $\pm 1$ walk from $0$ to $-1$ must cross from $0$ to $-1$ . It gives both an existence proof and an algorithm.
Signed values make balance conditions easy: $+1/-1$ labels turn "as many of each" into "sum is zero", exactly like counting errors when sweeping a threshold for a ROC curve.
Pick the pivot on the convex hull: the leftmost point guarantees all directions lie within a half-turn, so the sort by slope is valid.
Respect the output format: a vertical line cannot be written as $y = ax + b$ ; keep all candidates and choose one that fits.

Code complet (solution.py)

"""FAIO 2024 qualification, Problem J "Dividing the Stars".

n neutron stars (+1) and n giant stars (-1), no three collinear. Find a line
y = a x + b through one neutron and one giant star with equally many neutron
and giant stars in one open half-plane.

Idea: pivot on an extreme point P (here the leftmost one), sort the other
2n-1 points by slope around P and walk through them with a running balance.
The balance starts at 0 and ends at -sign(P) (the other colour has one more
point), so it must step from 0 to -sign(P) somewhere: that step is a point Q
of the opposite colour with a perfectly balanced set of points before it,
i.e. on one side of line PQ. O(n log n).

Judge mode:   python solution.py < input.txt
Self-test:    python solution.py --check
"""
import sys
import numpy as np


def candidates_from_leftmost(X, Y, s):
    """Pivot = lexicographically smallest (x, y). Returns (p, list of valid q)."""
    p = np.lexsort((Y, X))[0]
    others = np.delete(np.arange(len(X)), p)
    dx, dy = X[others] - X[p], Y[others] - Y[p]          # dx >= 0 for everybody
    with np.errstate(divide="ignore"):
        slope = np.where(dx > 0, dy / np.where(dx > 0, dx, 1), np.inf)
    order = others[np.argsort(slope, kind="stable")]     # counter-clockwise from "down"
    v = s[order] * s[p]                                  # +1 same colour as P, -1 opposite
    before = np.concatenate(([0], np.cumsum(v)[:-1]))    # balance strictly before each point
    good = order[(v == -1) & (before == 0)]              # opposite colour, balanced side
    return p, good


def solve(X, Y, s):
    """Try the leftmost point under 4 symmetries (leftmost, rightmost, lowest,
    highest) and return the first valid pair whose line is not vertical."""
    for tx, ty in [(X, Y), (-X, -Y), (Y, X), (-Y, -X)]:
        p, good = candidates_from_leftmost(tx, ty, s)
        for q in good:
            if X[q] != X[p]:
                a = (Y[q] - Y[p]) / (X[q] - X[p])
                return a, Y[p] - a * X[p], p, q
    raise RuntimeError("no non-vertical solution found from the four extreme points")


def read_input(text):
    t = text.split()
    n = int(t[0])
    v = np.array(t[1:1 + 4 * n], dtype=float).reshape(2 * n, 2)
    s = np.concatenate([np.ones(n, int), -np.ones(n, int)])   # neutrons first
    return v[:, 0], v[:, 1], s


# --------------------------------------------------------------- checking
def exact_check(Xf, Yf, s, p, q):
    """Exact (rational) check that line pq has a balanced open half-plane."""
    from fractions import Fraction as F
    if s[p] == s[q]:
        return False
    px, py, qx, qy = F(Xf[p]), F(Yf[p]), F(Xf[q]), F(Yf[q])
    left = right = 0
    for i in range(len(Xf)):
        if i in (p, q):
            continue
        c = (qx - px) * (F(Yf[i]) - py) - (qy - py) * (F(Xf[i]) - px)
        assert c != 0, "three collinear points"
        if c > 0:
            left += s[i]
        else:
            right += s[i]
    return left == 0 or right == 0


def check():
    rng = np.random.default_rng(0)
    tested = 0
    for trial in range(3000):
        n = int(rng.integers(2, 12))
        P = rng.integers(1, 60, size=(2 * n, 2)).astype(float)      # small ints: exact maths
        if len({tuple(r) for r in P}) < 2 * n:
            continue
        # reject collinear triples (the statement forbids them)
        A = P[:, None, None, :] - P[None, :, None, :]
        B = P[None, None, :, :] - P[None, :, None, :]
        cr = A[..., 0] * B[..., 1] - A[..., 1] * B[..., 0]
        idx = np.arange(2 * n)
        distinct = (idx[:, None, None] != idx[None, :, None]) & (idx[None, :, None] != idx[None, None, :]) & (idx[:, None, None] != idx[None, None, :])
        if np.any((cr == 0) & distinct):
            continue
        s = np.concatenate([np.ones(n, int), -np.ones(n, int)])
        rng.shuffle(s)                                   # colours in any order
        try:
            a, b, p, q = solve(P[:, 0], P[:, 1], s)
        except RuntimeError:
            continue
        assert exact_check(P[:, 0], P[:, 1], s, p, q), (trial, P, s)
        assert abs(P[p, 1] - (a * P[p, 0] + b)) < 1e-9 and abs(P[q, 1] - (a * P[q, 0] + b)) < 1e-9
        tested += 1
    print(f"{tested} random valid instances (n = 2..11): every answer exactly verified")
    import time
    n = 99_999
    txt = f"{n}\n" + "\n".join(f"{x:.6f} {y:.6f}" for x, y in rng.uniform(1, 1e6, (2 * n, 2)))
    t0 = time.time(); X, Y, s = read_input(txt); a, b, p, q = solve(X, Y, s)
    print(f"n = {n}: solved in {time.time() - t0:.2f} s, a = {a:.6f}, b = {b:.3f}")
    figure()


def figure():
    import matplotlib
    matplotlib.use("Agg")
    import matplotlib.pyplot as plt
    rng = np.random.default_rng(5)
    n = 9
    P = rng.uniform(0, 10, (2 * n, 2))
    s = np.concatenate([np.ones(n, int), -np.ones(n, int)])
    X, Y = P[:, 0], P[:, 1]
    a, b, p, q = solve(X, Y, s)
    others = np.delete(np.arange(2 * n), p)
    order = others[np.argsort((Y[others] - Y[p]) / (X[others] - X[p]))]
    v = s[order] * s[p]
    bal = np.concatenate(([0], np.cumsum(v)))
    fig, ax = plt.subplots(1, 2, figsize=(10, 4.3), dpi=150, gridspec_kw={"width_ratios": [1.1, 1]})
    for k, i in enumerate(order):
        ax[0].plot([X[p], X[i]], [Y[p], Y[i]], color="0.85", lw=0.7, zorder=0)
        ax[0].annotate(str(k + 1), (X[i], Y[i]), xytext=(4, 3), textcoords="offset points", fontsize=7, color="0.35")
    ax[0].scatter(X[s == 1], Y[s == 1], c="#4c72b0", s=40, label="neutron (+1)")
    ax[0].scatter(X[s == -1], Y[s == -1], c="#dd8452", marker="s", s=36, label="giant (-1)")
    ax[0].scatter([X[p]], [Y[p]], s=160, facecolors="none", edgecolors="k", lw=1.5)
    xs = np.array([-0.5, 10.5])
    ax[0].plot(xs, a * xs + b, "k-", lw=1.5, label="answer line PQ")
    ax[0].set_xlim(-0.5, 10.5); ax[0].set_ylim(-0.5, 10.5)
    ax[0].set_title("pivot P (circled), others numbered by angle")
    ax[0].legend(frameon=False, fontsize=8, loc="upper right")
    kq = int(np.where(order == q)[0][0]) + 1
    ax[1].step(np.arange(len(bal)), bal, where="post", color="k")
    ax[1].plot(np.arange(len(bal)), bal, "o", ms=3, color="k")
    ax[1].axhline(0, color="0.7", lw=0.8)
    ax[1].annotate("Q: first step 0 -> -1", (kq, -1), xytext=(kq + 1.5, -2.3),
                   arrowprops=dict(arrowstyle="->"), fontsize=9)
    ax[1].set_xlabel("number of points swept around P")
    ax[1].set_ylabel("balance (same colour as P minus other)")
    ax[1].set_title("running balance: starts at 0, ends at -1")
    for a_ in ax:
        a_.spines[["top", "right"]].set_visible(False)
    fig.tight_layout()
    fig.savefig("figures/sweep.png", facecolor="white")
    print("saved figures/sweep.png")


if __name__ == "__main__":
    if "--check" in sys.argv:
        check()
    else:
        X, Y, s = read_input(sys.stdin.read())
        a, b, _, _ = solve(X, Y, s)
        print(f"{a:.12g} {b:.12g}")