MVernik's blog

By MVernik, history, 4 years ago, In English
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.


  • Vote: I like it
  • +37
  • Vote: I do not like it

| Write comment?
»
4 years ago, # |
  Vote: I like it +23 Vote: I do not like it

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

Do you mean minimize number of pairs of adjacent rooms with the same client? Or something else?