1800. Spread Them As Far Apart As Two Choices Allow

There are n posters and each must go at one of two offered positions on a single long wall. Position a and position b are given for every poster, and they may be the same number, which means that poster has no real choice.

Choose one position per poster so that the SMALLEST distance between any two chosen positions is as large as possible, and print that largest smallest distance. Two posters may be placed at the same position, in which case their distance is 0.

## What most people try first

Sorting and spreading. There is nothing to sort: the choice for one poster changes which positions are near which, and no order on the input reflects that.

The second attempt is greedy: place the posters left to right, each at whichever offered position is further from the last one placed. With posters offering {0, 10}, {1, 11} and {5, 6}, the greedy takes 0, then 11, then 6 or 5, giving a smallest gap of 5; the best is 0, 11, 5 giving 5 as well, but on {0, 100}, {1, 2}, {50, 51} the greedy takes 0, then 2, then 51, giving 2, while 100, 1, 51 gives a smallest gap of 49. One early choice spends the room the rest of the wall needed.

The third attempt is to try all 2^n choices. Correct and far too slow at n = 100.

## Fix the answer first, then it is a two-condition system

Suppose someone tells you the answer is at least d. Then the question is no longer an optimisation, it is a feasibility test, and the test is pairwise:

> For every two posters and every combination of their offered positions, if > those two positions are closer than d, that combination is BANNED.

Let x_i be true when poster i takes its second offered position and false when it takes its first. Each banned combination says "not both of these two single conditions", which is a rule of exactly two conditions. Collect them all and the question is whether that system is satisfiable, which problem 1725 decides on the implication graph.

Two offered positions per poster is exactly what makes a ban a two-condition rule. With three positions each, a ban would need three conditions and this method would not exist.

## Why that is enough to find the answer

If a placement achieves a smallest gap of at least d, it achieves at least d - 1: the same placement, a weaker claim. So feasibility is downward closed in d, the yes answers form an unbroken run starting at d = 0, and the answer is the boundary. d = 0 is always feasible, since no pair of positions is closer than 0, so the run is never empty.

> lo = 0, hi = (largest offered position) - (smallest offered position). > While lo < hi, let mid = (lo + hi + 1) / 2 rounded down; if mid is > feasible set lo = mid, otherwise set hi = mid - 1. The answer is lo.

The + 1 is required. With lo = 0 and hi = 1, a plain midpoint probes 0, succeeds, leaves lo at 0 and loops forever.

hi cannot need to be larger: every chosen position lies between the smallest and largest offered position, so no gap can exceed their difference.

## Overflow

This is the part worth getting right rather than guessing. Positions reach 10^9, so lo + hi + 1 reaches 2000000001. A signed 32-bit integer holds up to 2147483647, so that FITS and no 64-bit type is needed anywhere. The differences abs(p - q) are at most 10^9. Nothing in this problem overflows, and a solution that reaches for a 64-bit accumulator is being careful about a risk that is not there.

``` n = 3 poster 1: 0 or 100 poster 2: 1 or 2 poster 3: 50 or 51

d = 50? ban pairs closer than 50: poster 1 at 0 with poster 2 at 1 or 2 banned poster 2 at 1 or 2 with poster 3 at 50 or 51 banned poster 2 has nowhere to go, so d = 50 is not feasible d = 49? poster 1 at 100, poster 2 at 1, poster 3 at 51: distances 99, 49, 50 feasible answer: 49 ```

## The boundary that breaks a careless implementation

A poster whose two offered positions are equal must still generate both of its conditions, because the ban is on the PAIR of posters and the other poster's choice is what the rule constrains. Treating it as a fixed position and skipping it loses those rules.

Two posters offered the identical pair at distance 0 from each other force the answer to 0, and 0 is a legal output, so the search must be able to return its lower bound.

Both passes of the component search need explicit stacks. The graph has 2n nodes and up to 4 * C(n, 2) arcs, and it is rebuilt from scratch on every probe, which is fine: there are only about 30 probes.

## Cost

O(n^2 log S) where S is the span of the offered positions: each probe generates up to 2n(n - 1) rules and decides them in linear time, and there are log2(S) probes, about 30. At n = 100 that is 30 passes over 19800 rules.

Constraints - `2 ≤ n ≤ 100` - `0 ≤ a ≤ 10^9` and `0 ≤ b ≤ 10^9` - `a` may equal `b`, which means that poster has no real choice - two posters may offer identical pairs, and two chosen positions may coincide, giving a distance of 0 - `lo + hi + 1` reaches 2000000001, which a signed 32-bit integer holds, so no 64-bit type is needed anywhere