A café splits its n staff (numbered 0 to n - 1) into two shifts. Some pairs do not get
along: clashes is a list of (a, b, strength) triples. A clash causes no trouble when a and b
work different shifts. Write split_shifts(n, clashes) that returns a list shift of length
n with shift[i] equal to 0 or 1, keeping apart as much clash strength as possible.
The tests build their lists with clash_list(n, seed), and kept_apart(clashes, shift) adds up
the strength of the clashes your split keeps apart. Both are available in your code, so you can
try them with Run.
How this problem is scored
This is a maximisation problem. A split passes if it is valid and keeps apart at least as much strength as this simple rule: take people in index order, and put each one on the shift that keeps apart more strength with the people already placed (shift 0 on a tie), never moving anyone again. Its quality (0 to 100) says how much of the gap between that rule and the best split we know you close: 0 matches the rule, 100 matches (or beats) the best known split.
Examples
Input: n = 4, clashes = [(0, 1, 5), (1, 2, 3), (2, 3, 4), (0, 3, 1), (0, 2, 2)]
Output: [0, 1, 0, 1]
Explanation: every clash except (0, 2) is kept apart: 5 + 3 + 4 + 1 = 13 of 15.
Input: n = 14, clashes = clash_list(14, 1)
Output: any list of 14 zeros and ones keeping apart at least as much as the simple rule
Constraints
2 <= n <= 150,1 <= strength <= 9, no pair appears twice- Each test must finish in well under a second in your browser. Limit your loops by a number of rounds, not by the clock, so the result is the same on every run.
Goals
- Build a two-way split greedily
- Improve it by flipping one element at a time while that helps
- Compute the gain of a move without re-evaluating the whole solution