3 ms·
Is there a linear time solution? The normal solution is O(N^3) in the number of windows (and does not depend on W,H at all).
by anonymoushn 14y ago
Is there a linear time solution? The normal solution is O(N^3) in the number of windows (and does not depend on W,H at all).
- rlanday 14y agoFacebook Hacker Cup had a similar problem: https://www.facebook.com/hackercup/problems.php?pid=532506256782917&round=189890111155691 https://www.facebook.com/hackercup/problems.php?pid=53250625... I almost solved it; after screwing around for a while trying to record only one value for each square, I realized you need to store two values for each square. If we’re looking for the upper-left corner we can put a window, each dead pixel/pixel “poisons” all the pixels less than the width of the window to the left of it and the height of the window above it. Then you just do a linear scan over the remaining pixels. I think my problem was that I used too much RAM because I was trying to store the whole 2D grid; you only need to keep one dimension in memory. You can see people’s submissions here: https://www.facebook.com/hackercup/scoreboard?round=189890111155691 https://www.facebook.com/hackercup/scoreboard?round=18989011...
- anonymoushn 14y agoThis problem is interesting. It doesn't make any sense to use an N^3 solution like the Meebo problem if N can be so large. I haven't looked at any solutions, but it seems like an N*lg N + WH solution would pass.