Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- https://www.codingame.com/ide/puzzle/fantastic-bits
- Description sommaire du problème hongrois:
- https://www.developpez.net/forums/blogs/283256-f-leb/b17/python-problemes-daffectation-methode-hongroise/
- Implementation choice in this challenge:
- - First, we build a 2d matrix representing distances between each wizard and each snaffle
- distances---s1------s2-----s3------s4-------s5------s6------s7
- wiz_1-------50------70-----100-----120------80------150-----200
- wiz_2-------130-----20------5------179------20------30------40
- - Second, we create a dictionary to create an association from each wizard to a distinct snaffle describing the cost matrix in term of distance/duration of moves:
- `costs[(0, i), (1, j)] = matrix[0][i] + matrix[1][j] (i, j going from 1 to snaffles_count and i != j)
- `
- - Third, we choose the best combination to optimize global team effort (extracts the dictionary key (tuple) of minimum cost value)
- `best_combination = min(costs)`
- `i, j = best_combination[0][1], best_combination[1][1]`
- - Finally, we extract the snaffle target for each wizard:
- `wiz_1.target, wiz_2.target = snaffles[i], snaffles[j]`
- Replays:
- - Ligue Bois 2: https://www.codingame.com/replay/496545129
- - Ligue Bois 1 (with bludgers): https://www.codingame.com/share-replay/496563891
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement