mraron's blog

Guards in museum — How to solve this greedy problem?
By mraron, 8 years ago, In English

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.

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

»
8 years ago, # |
  Vote: I like it +5 Vote: I do not like it
Hint

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

→ Reply
»
8 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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.

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +2 Vote: I do not like it
      Solution
      → Reply
    • »
      »
      »
      8 years ago, # ^ |
      ← Rev. 3   Vote: I like it +3 Vote: I do not like it

      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

      → Reply