1797. Every Task Gets One of Its Two Slots

There are n tasks and p time slots. Task i can be run in slot a or in slot b, and those two are different. At most one task may occupy a slot.

Print Yes if every task can be given a slot and No otherwise.

## What most people try first

Counting: if n <= p there are enough slots, so yes. Three tasks that all offer only slots 1 and 2 break that at once, with p as large as you like.

The second attempt is a greedy sweep: take the tasks in order and give each one its first free option. It survives every three-task case, which is why it gets written. It fails on four:

``` task 1: slots 1 or 2 task 3: slots 1 or 3 task 2: slots 3 or 4 task 4: slots 2 or 4

greedy: task 1 -> 1, task 2 -> 3, task 3 -> 1 and 3 both taken, stuck a plan: task 1 -> 1, task 2 -> 4, task 3 -> 3, task 4 -> 2 ```

Greedy gave slot 3 to task 2 when slot 4 would have done, and nothing in the sweep goes back. That is the same failure as the greedy plan in problem 1786, and no input order fixes it: reverse this input and greedy gives task 4 slot 2, task 3 slot 1, task 2 slot 3, and task 1 finds 1 and 2 taken.

The third attempt is a matching. That IS correct here, since tasks and slots form a two-sided list, and problem 1786 solves it. This problem exists to show the OTHER reduction, the one that keeps working when the constraints stop being "at most one per slot" and start being arbitrary pairwise bans.

## Two options means one bit, which means a formula

Give task i one true or false value: let x_i be true when task i takes its SECOND listed slot and false when it takes its first. Any setting of the n values is a complete plan, and the plan is legal exactly when no slot is taken twice.

"Task i is in slot s" is then a single condition: it is x_i false when s is a, and x_i true when s is b. For every slot s and every two tasks i and j that could both land there, the ban "not both in s" is

NOT (i is in s) OR NOT (j is in s)

which is a rule of exactly two conditions. Collect one such rule per colliding pair and the answer is whether the resulting 2-condition system is satisfiable, which problem 1725 decides with the implication graph.

Two options per task is what makes every ban a TWO-condition rule. With three options per task the ban needs three conditions and the problem becomes graph colouring, which has no comparable method.

## How many rules there are

A task contributes itself to exactly two slots, so the slot lists hold 2n entries in total, and a task appears at most once in a given list because its two slots differ. The rules are one per pair inside a list, so with the lists of sizes L_1, ..., L_p summing to 2n there are at most 2 * C(n, 2), which is n * (n - 1). At n = 300 that is 89700, so bucket the tasks by slot once and walk each bucket pairwise rather than looping over all pairs of tasks.

``` n = 3, p = 2. task 1: slots 1 or 2 task 2: slots 1 or 2 task 3: slots 1 or 2

slot 1 holds: NOT x1, NOT x2, NOT x3 (each takes slot 1 when false) slot 2 holds: x1, x2, x3

rules from slot 1: x1 or x2, x1 or x3, x2 or x3 rules from slot 2: NOT x1 or NOT x2, NOT x1 or NOT x3, NOT x2 or NOT x3

the first three say at most one is false, the last three at most one is true, and three values cannot have at most one of each. answer: No ```

## The boundary that breaks a careless implementation

n = 1 has no pairs, so there are no rules and the answer is Yes. An empty rule list must come out satisfiable rather than crashing the component search.

A slot nobody offers contributes an empty bucket and must be skipped without generating anything. The two options of a task are guaranteed different, which is what keeps the pair (NOT x_i, x_i) from ever being generated as a rule; that rule would be satisfied by both values and would silently allow a task to be in two places.

Build the component search with explicit stacks. At n = 300 the graph has 600 nodes and nearly 180000 arcs.

## Cost

O(n^2) to generate the rules in the worst case and O(n + rules) to decide them, so O(n^2) overall. At n = 300 that is under 2 * 10^5 steps.

## Overflow

n * (n - 1) at n = 300 is 89700, and the arc count is twice that. Nothing approaches 2147483647.

Constraints - `1 ≤ n ≤ 300` - `2 ≤ p ≤ 300` - `1 ≤ a ≤ p` and `1 ≤ b ≤ p`, and `a` is never equal to `b` - two different tasks may offer exactly the same pair of slots - a slot may be offered by no task at all