Disney Optimization

Revision en4, by MVernik, 2020-11-16 11:56:34
Good Morning

Problem

You're given a set of hotel rooms, each room has it's own priority and each room has a client.

You have to minimize the number of repeating clients in the hotel rooms, according to the rules:

  • You can only swap clients with the same priority.
  • You are not allowed to swap rooms.
  • You are not allowed to swap priorities.

Limitations:
0 < Rooms < 1000
0 < Priority < 10^9
'A' < Client < 'Z'

Example


Input:
image
Output:
image


The following example shows:
- in the picture1 — client "B" is repeating.
- in the picture2 — there are no repeating clients.


Thoughts

  1. I converted it to the graph and tried DFS + Multiset, but the complexity was exponential
    image
  2. Tried to create a solution using randomization, but I didn't get to it.
  3. I googled and didn't find similar problems.


Tags disney, #optimization

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English MVernik 2020-11-16 11:56:34 15
en3 English MVernik 2020-11-16 00:44:29 14 Tiny change: '\n<spoiler s' -> '<spoiler s'
en2 English MVernik 2020-11-15 19:23:21 15 Tiny change: '\n<spoiler summary="Good Morning">\nGo' -> '<spoiler summary="Good Evening">\nGo'
en1 English MVernik 2020-11-15 13:29:17 1527 Initial revision (published)