JOIN
 Select a Forum     Round Tables New Member Discussions News Discussions Algorithm Matches Marathon Matches NASA Tournament Lab TopCoder Cookbook High School Matches Sponsor Discussions Development Forums Design Forums Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings View: Flat (newest first)  | Threaded  | Tree Previous Thread  |  Next Thread Forums Algorithm Discussions General Algorithm Discussions Maximum Number of Points on wall
 Maximum Number of Points on wall | Reply Hi, I couldn't come up with a N^2 or N^2logN solution for this problem. any help is appreciated. Here is the basic problem: basically, on a X*Y(x,y<10^9) sized wall, there are k(k<2500) integer coordinated points, a M*N(m,n < 10^9) sized rectangular panel is to be put on wall so that maximum number of points are covered. the rectangle must be put as it is, i.e you cant rotate it, its sides must be parallel to axes.thanks in advance for any hints!
 Re: Maximum Number of Points on wall (response to post by kolistivra) | Reply It's easy too see that panel could be placed in such a way that its left and top borders contain at least one point.So, if you fix the left border you can move the top border from down to up and count the number of points inside the panel. Use map and binary search where needed.So, overall complexity will be depending on implementation something like O(k^2*log(k)) or O(k^2*log(k)*log(k)).
 Re: Maximum Number of Points on wall (response to post by it4.kp) | Reply I think you can get O(k*k*log(k)) without maps nor binary searches.```for each coordinate x: A = all points from [x,x+N] sort(A) by y coordinate traverse A with two pointers to find the most crowded interval end ``` Actually you can avoid the sort step if you have all the points sorted by y at the beginning, thus the whole algorithm becomes O(k^2)
 Re: Maximum Number of Points on wall (response to post by slex) | Reply And how are you getting A = all points from [x,x+N] if all points are sorted on y?EDIT: Ok, I see how. So basically the problem is solved :)
 Forums Algorithm Discussions General Algorithm Discussions Maximum Number of Points on wall Previous Thread  |  Next Thread