Блог пользователя mraron

Guards in museum — How to solve this greedy problem?
Автор mraron, 8 лет назад, По-английски

Hi!

I've a problem with this problem, could anyone help me out with a hint? Anything is appreciated :)

Statement: There's a museum made up by N * N cells, forming a square. We should place N guards, so that in every column and row there's exactly 1 guard. Also the guards have their "preferences", so every of them have a rectangular area where he wants to be placed to guard. The problem is to give a distribution of the guards (N points) where everyone is in his preferred rectangle or state that there's no such distribution.

Here's the statement in hungarian language with a picture too: here.

Thank you for reading, have a nice day.

  • Проголосовать: нравится
  • +39
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится
Hint

I think that it is the same problem as here : http://main.edu.pl/en/archive/oi/3/wie

→ Ответить
»
8 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

First solve problem for single dimension i.e. given n cells for guards to stand, each having preference of type (l,r) i.e. he will stand only in cells numbered from l to r, how will you place all in different cells. Once this problem is solved, solution for two dimensions is similar.

→ Ответить
»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Thank you for your help, I've solved it finally :)

→ Ответить
  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится

    Would you kindly share the idea or the solution :D ?

    → Ответить
    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится +2 Проголосовать: не нравится
      Solution
      → Ответить
    • »
      »
      »
      8 лет назад, # ^ |
      ← Rev. 3   Проголосовать: нравится +3 Проголосовать: не нравится

      Yes of course, here it is :)

      Every rectangle of form (a;b;c;d) (where (a;b) stands for lower left corner and (c;d) stands for upper right corner) actually limits the place of guard on x-axis by (a;c), on y-axis by (b;d). So then we have a bunch of limits. First let's solve for x-axis, sort the limits by their right endpoint (if their right endpoint is equal, sort by their left). Second, let's mark all points unoccupied on the axis, then loop trough them: if we're at limit (p, q) then the x-coordinate of the guard with this limit is the leftmost point k, that is not occupied yet and p ≤ k ≤ q (if there's no such k then there's no solution). Next mark k occupied and continue the loop. This way we got x-coordinates of the guards, it can be done similarly for the y-coordinates.

      Link to implementation: ideone

      → Ответить