1798. Print the Timetable, Not Just Whether One Exists

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 the slot each task gets, or No if no plan exists. Problem 1797 answers only whether a plan exists.

## The plan is not unique, so one is pinned

On three tasks offering (1, 2), (2, 3) and (1, 3) both 1, 2, 3 and 2, 3, 1 are legal, so the problem would have two answers. The statement therefore fixes one:

> Among all legal plans, print the one that prefers task 1's FIRST listed slot; > among those, the one that prefers task 2's first listed slot; and so on down > the tasks.

Equivalently, write 0 when a task takes its first listed slot and 1 when it takes its second, read the n digits as a string with task 1 at the front, and print the plan whose string is smallest.

## What most people try first

Printing whatever plan the first correct method produced. That is the same mistake as in problem 1787 and it makes the problem unanswerable.

The second attempt is a greedy sweep: give each task its first free option, in order. That is not even a correct feasibility test, as problem 1797 shows with four tasks, so it certainly does not produce the pinned plan.

The third attempt is to find any legal plan and then improve it, moving task 1 to its first slot if that stays legal, then task 2, and so on. Each step has to re-establish legality for everything after it, which is a new feasibility question each time, so this is the right idea done the expensive way: n feasibility tests instead of one pass.

## The formula, then the smallest satisfying setting

The reduction is problem 1797's. Let x_i be true when task i takes its SECOND slot. For every slot and every two tasks that could both land there, forbid that pair with a rule of two conditions. A legal plan is exactly a setting satisfying every rule, and the pinned plan is exactly the lexicographically smallest such setting with x_1 most significant.

Finding it is a greedy with propagation:

> Check the whole system is satisfiable first; if not, print No. Then take the > variables in order. If x_i is already decided, skip it. Otherwise FORCE > x_i false and follow every implication; if that reaches a contradiction, > undo everything it set and force x_i true instead.

## Why forcing false and keeping it is safe

This is the claim worth arguing, because it is false for constraint systems in general. Suppose the partial setting so far extends to some satisfying setting, which holds at the start because the system is satisfiable. Force x_i false and close under implication. If that closure contains no variable both ways, then the closure is consistent, and every rule it touches is satisfied: a rule is an implication in both directions, and the closure followed every arc out of everything it set. Nothing it set contradicts the earlier variables either, since the earlier variables were already closed and a newly set condition whose negation was already set would have been caught as the contradiction. So the extended partial setting still extends to a satisfying setting, and since x_i false comes first in the ordering, taking it can only make the printed string smaller. If the closure DOES contradict itself, no satisfying setting extends the partial one with x_i false, so x_i true is forced and is also safe, because the whole system was satisfiable and some satisfying setting extends the partial one.

The undo matters. A failed force must leave no trace, which means remembering exactly which conditions it set and clearing those and only those.

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

rules: slot 1 holds NOT x1 and NOT x3 -> x1 or x3 slot 2 holds x1 and NOT x2 -> NOT x1 or x2 slot 3 holds x2 and x3 -> NOT x2 or NOT x3

x1 false: slot 1's rule forces x3 true, slot 3's rule then forces x2 false. No contradiction, so keep it. plan: task 1 -> 1, task 2 -> 2, task 3 -> 3 ```

## The boundary that breaks a careless implementation

Decide satisfiability BEFORE the greedy. The greedy with no satisfiability check will happily force a variable true after a failed false and produce a plan with a slot used twice, because the fallback is only safe when a satisfying setting is known to exist.

With n = 1 there are no rules and the answer is the task's FIRST slot, not its second. Both traversals, the propagation and the component search, must carry explicit stacks: at n = 300 the implication graph has 600 nodes and a chain can run through every one of them.

## Cost

O(n^2) to build the rules, O(n + rules) to decide satisfiability, and O(n + rules) for the greedy, because a condition is set at most once across all the successful forces and each failed force is paid for by the variable it decides. So O(n^2) overall.

## Overflow

Every printed number is a slot index, at most 300.

Constraints - `1 ≤ n ≤ 300` - `2 ≤ p ≤ 300` - `1 ≤ a ≤ p` and `1 ≤ b ≤ p`, and `a` is never equal to `b` - the two slots are given in a fixed order and that order is what the tie-break refers to - two different tasks may offer exactly the same pair of slots