1206. The Smallest Assignment Under Same and Different

There are n variables numbered 1 to n, each to be given a value from 1 to c. A list of q constraints restricts them. Each constraint is a line same i j, meaning variables i and j must get the same value, or diff i j, meaning they must get different values. No constraint names the same variable twice. Report the lexicographically smallest assignment, read as the values of variables 1, 2, ..., n, or report that none exists.

4 variables, 2 values same 1 2 diff 2 3 diff 3 4 answer 1 1 2 1

## What most people try first

Process the constraints and propagate. Merge the variables joined by same into groups, then colour the groups so that diff constraints land between different groups. That is a good instinct and it is a different problem: it is graph colouring on the quotient graph, which is #1200, and it does not by itself give the lexicographically smallest assignment, because the smallest assignment is not the one a colouring algorithm happens to produce. It also needs care when a same and a diff both join the same pair, which is an immediate contradiction.

The search below is simpler and answers the question that was asked. The propagation idea is worth knowing as the faster method for large inputs, and it is named here so the contrast is deliberate rather than a surprise.

## Why the answer is the SMALLEST one and not just any one

There are usually many solutions, and a list of them has no order anyone can guess, so the answer is pinned to a single object: read the assignment as one sequence in the stated reading order and return the one that is smallest compared position by position. That makes the answer unique, which means a program is either right or wrong rather than differently right.

It also makes the search simpler, not harder. Fill the positions in reading order, and at each position try the values in increasing order. The FIRST complete solution the search reaches is then the smallest one, because any other solution differs from it at some position where it chose a larger value, and a larger value at the earliest difference is exactly what larger means. There is no comparison step and nothing is kept to compare against.

## When a constraint can first be tested

A constraint between variables i and j cannot be tested until both have values, and it should be tested the instant the second of them gets one. So for each variable keep the constraints whose LARGER index is that variable: when variable i is assigned, exactly those become testable, and every other constraint is either already tested or still has an unassigned side.

Getting that wrong in either direction is a real defect rather than an inefficiency. Testing too early means reading an unassigned variable, whose value is whatever your array was initialised to, and an array of zeros makes two unassigned variables look equal, so a same passes that should not have been considered and a diff fails that should not have been considered. Testing too late, only at a complete assignment, turns the search back into brute force over c^n.

## The method

go(i): if i == n: return true for v in 1 .. c: cur[i] = v if every constraint whose larger side is i now holds: if go(i + 1): return true return false

## Why it is correct

Every assignment the search reaches obeys every constraint, because each constraint is tested at the step where its second variable is set and nothing later changes either side within that branch. Every valid assignment is reachable, because no value is refused except by a constraint it genuinely breaks. And the first one reached is the smallest, by the argument above.

## The two contradictions to settle

A same i j and a diff i j on the same pair can never both hold, so the answer is none; the search discovers that without special handling, which is worth checking rather than assuming. And diff constraints can exhaust the values: three variables pairwise different need c at least 3. Both are tested.

## A note for C

The operator is a word, not a letter. Comparing only the first character would work here, since same and diff begin differently, and it is still the wrong habit: on another problem in this bank a one-letter test on set and sub silently failed every C test while passing in the other four languages. Use a full string comparison.

## Cost

One node per prefix that breaks no constraint, with O(q) work per node to test the newly testable constraints. The worst case is c^n when there are no constraints, which is also the case where the answer is the very first leaf.

Constraints - `1 ≤ n ≤ 10` - `1 ≤ c ≤ 5` - `0 ≤ q ≤ 20` - each operator is exactly `same` or `diff`