0

Given a rectangular grid of N*M (1-based indexing) in which their are k monsters on k different cells.Now we need to answer Q queries in which we will be given lowest row number(L) and highest row number(H) we need to tell maximum area of rectangle between those rows that don't have a monster.(Here area of rectangle means count of cells only)

Example : Say we have a grid of 4 * 5 (mean n=4 and m=5) and monsters are located on 7(=k) cells which are (1,3) , (1,4) , (2,1) , (2,4) , (3,2) , (4,1) , (4,2) and let we have 1 query in which L=3 and H=4 then the maximum area is 6 here.

Now if the queries are very large say 10^6.Then how to tackle this problem.Is their any dynamic approach or so for doing it?

enter image description here

Here red blocks indicate monster and purple one is solution rectangle

user3086701
  • 63
  • 1
  • 5
  • 1
    Monsters are everywhere even on SO ! – P0W Jan 05 '14 at 18:45
  • @P0W i dont get what u wanna say.In the solution rectangle we can see their is no monster – user3086701 Jan 05 '14 at 18:46
  • When you are say queries are very large do you mean `H-L` is very large? – Robin Green Jan 05 '14 at 18:58
  • 1
    P0W was just joking, ignore P0W. – Robin Green Jan 05 '14 at 18:58
  • @RobinGreen Numbers of queries are large.and H,L can be anything from 1 to n – user3086701 Jan 05 '14 at 19:00
  • This looks very similar to http://stackoverflow.com/questions/2478447/find-largest-rectangle-containing-only-zeros-in-an-nn-binary-matrix – mcdowella Jan 05 '14 at 19:24
  • @mcdowella actually their are large number of queries..So i was thinking of some precomputation or so – user3086701 Jan 05 '14 at 19:30
  • The bottom of http://www.informatik.uni-ulm.de/acm/Locals/2003/html/judge.html gives you 6 different ways to solve a related problem. If there was a cheap way to solve your problem I would expect it to show up as one of these 6 answers, or at least as something you could convert from these 6 answers by using http://en.wikipedia.org/wiki/Persistent_data_structure. I can't see anything likely there, but perhaps somebody else can. – mcdowella Jan 06 '14 at 06:19
  • 1
    @user3086701 Please remove the question because it is same as problem in codechef ongoing long contest http://www.codechef.com/JAN14/problems/METEORAK . I am not blaming you for cheating – Vikram Bhat Jan 06 '14 at 06:30
  • @VikramBhat: Asking the OP to remove the question is also asking to delete all efforts by others to provide answers and additional information. Do you really want that? – M Oehm Jan 06 '14 at 07:54
  • @MOehm The efforts that you have done are part of your growth as a programmer but the OP will not grow as programmer if he copies answers from SO. SO is about learning new things in programming isnt it, not solving problems by cheating. – Vikram Bhat Jan 06 '14 at 10:12
  • @VikramBhat: Thank you for lecturing me about my _growth as a programmer_. The OP didn't mention the competition. If the post is about the competition, he disguised the craters as monsters, throwing me off the track. (Monsters move, craters don't - I missed the part about the queries.) It didn't look like homework. If anything, this has to do with the OP not being honest about his or her intentions, not about people finding links and giving hints. – M Oehm Jan 06 '14 at 11:44
  • @MOehm Are you angry at me? because i didnt mean to hurt u in any way. I am sorry if i did. – Vikram Bhat Jan 06 '14 at 11:50
  • 1
    @VikramBhat: No. Well, maybe a bit. I took the question to be about a role-playing game, a typical newbie programming exercise. (You have to give the OP credit for camouflaging the question well.) Anyway, the problem of the effective algo hasn't been solved here and people seem to have lost interest in the question. No hard feelings. – M Oehm Jan 06 '14 at 12:44

2 Answers2

1

Here's a recursive solution that works for dungeons of arbirary size and relatively few monsters.

If there is one monster (x, y) in the dungeon (n, w, s, e), there are two cases. Case 1 is trivial: The monster is outside the dungeon. Then the maximum rectangle is the dungeon. (Dungeons are always rectangular, right?).

In Case 2, the maximum rectangle is one of the rectangles north, west, south or east of the monster:

NNNNNNNNNN    ....EEEEEE    ..........    WWW.......
NNNNNNNNNN    ....EEEEEE    ..........    WWW.......
NNNNNNNNNN    ....EEEEEE    ..........    WWW.......
NNNNNNNNNN    ....EEEEEE    ..........    WWW.......
NNNNNNNNNN    ....EEEEEE    ..........    WWW.......
...@......    ...@EEEEEE    ...@......    WWW@......
..........    ....EEEEEE    SSSSSSSSSS    WWW.......
..........    ....EEEEEE    SSSSSSSSSS    WWW.......
..........    ....EEEEEE    SSSSSSSSSS    WWW.......

Now apply this reasoning recursively for your list of monster locations and keep track of the maximum so far. Here's some pseudo code:

max_area = 0
max_rect = Null

sub find_max_rect(Dungeon, Monsters)

    if area(Dunegon) <= max_area: 
        return                      # save time for small dungeons

    if Monsters is empty:
        if area(Dungeon) > max:
            max_rect = Dungeon
            max_area = area(Dungeon)

    else
        M = Monsters.pop()          # Remove head from list

        if M in Dungeon:
            find_max_rect(Subrect(Dungeon, M, North), Monsters)
            find_max_rect(Subrect(Dungeon, M, East), Monsters)
            find_max_rect(Subrect(Dungeon, M, South), Monsters)
            find_max_rect(Subrect(Dungeon, M, West), Monsters)
        else:
            find_max_rect(Dungeon, Monsters)

Note: I've actually made a glaring mistake in the sketches above: @ represents, of course, the player and not a monster.

M Oehm
  • 28,726
  • 3
  • 31
  • 42
  • @M Ohem Isnt their any dynammic approach to do the same?.Iknow a O(n^4) solution.But it will be very slow as N,M can be upto 1000.I am asking because numberof queries can be very large and solving it again and again isnt so efficient – user3086701 Jan 06 '14 at 05:14
  • @MOehm It is problem from ongoing coding competition please remove the answer – Vikram Bhat Jan 06 '14 at 06:32
  • 1
    @VikramBhat: Who are you, SO Police? I'll keep my answer. I thought it was an interesting problem and I spent some time implementing an example solution with some test cases and writing up the answer. I'm not going to check the possibility of spoiling a competition before I post the answer. Wouldn't it have been the OP's task to point that out? (Also: There's nothing new under the sun. I'm quite sure that there are already answers to this or similar problems on the Web. Do you want to remove these solutions, too?) – M Oehm Jan 06 '14 at 07:16
  • @user3086701: What is so "static" about my approach? Have you actually read and tried to understand my answer? The "playing field" can be as large as it likes, because it is not a pixelmap, but just a set of four dimensions: The north and south _y_ as well as the west and east _x_ coordinates. The defining dimension of the algorithm is the number of monsters. But even so, as the sub-rectangles get smaller, the likelihood of containing a monster decreases and I expect the algorithm to be reasonably fast. – M Oehm Jan 06 '14 at 07:28
  • @MOehm i dont find it useful to calculate the result again and again for each of queries.f their are 10^6 queries.Then do i need to calculate it all the time.I think we can precompute all results in start itself – user3086701 Jan 06 '14 at 08:21
  • @user3086701: Okay, I didn't get the significance of what you meant with queries. The "monsters" are always the same, you're just analysing different strips of the playing field in each query. – M Oehm Jan 06 '14 at 09:01
  • @MOehm yeah exactly what i am saying.can i maintain an array which initially precompute the maximum array between ith and jth row – user3086701 Jan 06 '14 at 09:16
  • @user3086701: The queries are all for different is and js, aren't they? You could do some memoization, because with this approach you'll end up testing the same rectangles over and over again, but maybe this approach isn't suited to this problem. (Bummer, I thought it was rather nice.) – M Oehm Jan 06 '14 at 11:39
0

Do you know maximum matrix sum problem? That problem can be solved in O(n^3) time using dynamic programming.

Your question is very similar to that. What you need is to assign every empty grid value 1 and every monster grid value -INF. Then after you apply the maximum matrix sum solution, you got the maximum area.

songlj
  • 927
  • 1
  • 6
  • 10
  • How to reduce it to this problem? Can u please help – user3086701 Jan 06 '14 at 06:38
  • For instance, in your example, the map becomes ((1,1,-INF,-INF,1),(-INF,1,1,-INF,1),(1,-INF,1,1,1),(-INF,-INF,1,1,1)). Then you can apply maximum matrix sum solution. – songlj Jan 06 '14 at 06:48
  • @songlj Remove answer because it is question from ongiong programming contest – Vikram Bhat Jan 06 '14 at 06:52
  • @VikramBhat which contest? – songlj Jan 06 '14 at 06:54
  • @VikramBhat even if it is from a contest, you should not down vote my answer. – songlj Jan 06 '14 at 06:54
  • @songlj delete the answer and down vote will go automatically, check this link http://www.codechef.com/JAN14/problems/METEORAK – Vikram Bhat Jan 06 '14 at 07:11
  • @songlj But how to answer large number of queries?I can find the maximum sum in 2d array in O(n^3). – user3086701 Jan 06 '14 at 07:12
  • @VikramBhat ok, I wont provide more details for this question until the contest ends. – songlj Jan 06 '14 at 07:31
  • @user3086701 He has given you enough info here now you need to solve it on your own and now i am sure you are participating in the contest. Should be ashamed to call yourself a programmer. – Vikram Bhat Jan 06 '14 at 07:54
  • @VikramBhat I can understand you. But don't take it too seriously. It's just a game. I don't know if this contest has some cash rewards. But anyway, just treat it as a game. I used to take part in many contests and used to be as serious as you. I guess you are a young and passionate programmer. That's why you feel so angry. Just remember, don't take it too seriously. :) – songlj Jan 06 '14 at 08:20
  • @songlj My point here is that there is no need for asking such questions when contest gives you solutions at the end. It is just to score points but if he tries on his own he might be able to become a better programmer. – Vikram Bhat Jan 06 '14 at 10:06