A banquet has n guests and k round tables, and every table seats exactly n // k guests.
Some guests are friends, some would rather not share a table: like[i][j] (from -9 to 9, the same
as like[j][i]) says how much guests i and j enjoy sitting together. The happiness of a
plan is the sum of like[i][j] over all pairs of guests at the same table.
Write seat_guests(like, k) that returns a list tables of length n, where tables[g] is the
table (from 0 to k - 1) of guest g. Every table must get exactly n // k guests.
The tests build their guest lists with guest_list(n, seed), and happiness(like, tables) scores
a plan. Both are available in your code.
How this problem is scored
The checker makes its own plan: guests 0, 1, 2, ... in turn join the table (with a free seat)
whose guests they like most in total, the lowest-numbered table on a tie; then, scanning the pairs
(i, j) in order, it swaps two guests at different tables whenever that raises the happiness, until
a whole scan finds no such swap. Your plan passes if it is at least as happy as that one. Its
quality (0 to 100) says how much of the gap between that plan and the best plan we know you
close.
Examples
Input: like = guest_list(12, 1), k = 3
Output: a list such as [0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2] (four guests per table)
the checker's plan has happiness 58; the best plan has 64
Constraints
12 <= n <= 100,3 <= k <= 10,nis a multiple ofk- Each test must finish in well under a second in your browser. Limit your loops by a number of
steps, not by the clock, and use
random(the tests seed it) so the result is the same every run.
Goals
- Recognise when swap-based hill climbing is stuck in a local optimum
- Accept some worse moves on purpose, less often as the temperature cools
- Update a score incrementally instead of recomputing it after every move