Square sub-grid with maximum sum

Given $N$ points in a grid having some weight, I have to find the side length of a square sub-grid with maximum sum of weight of points contained in that square sub-grid. Also square sub-grid must have side length less than $L$ (given integer).

$1\le N \le 100000$, $1 \le L \le 100000$ , $1 \le x_i \le100000$, $1 \le y_i \le 100000$, $1 \le \text{weight}_i \le 10^9$, where $i$ is the $i^{th}$ point.

I have tried using prefix sum array and iterating over all the possible square sub-grids, but this is not efficient.

I need to know in which direction should I start thinking.

• @sasha Thank you for your hint. I was looking for line sweep algorithm but i was not able to figure out how to use it in the context of the problem. – userforfun Aug 14 '16 at 2:27
• Copied from a live programming contest: codechef.com/AUG16/problems/MAXGRID. Please don't ask us to solve your programming contest for you. Also, asking others to solve this is against the rules of that contest. – D.W. Aug 14 '16 at 4:09
• @userforfun wait for the contest to get over. Codechef posts very good editorials after the contest. Read that. – sashas Aug 14 '16 at 8:05
• @sasha Now the contest has ended. So could you give the answer. – userforfun Aug 15 '16 at 10:04

Firstly you did not write the complete question, to complete it, if $S$ is the maximum sum of weights in any sub-grid of lenght $\le L$, then we have to report $S$ and length of the sub-grid with smallest integral side where sum of weights inside it is $S$ ( hint: it won't change the complexity of the solution ). But that is slight detail which I leave to you to figure out. In this answer my aim is to calculate $S$.

Now we come to some pre-requisites for solving the problems. Firstly you should be comfortable with segment tree implementation. Second you need familiarity with binary search. Lastly I also assume ( as you have mentioned ) you also have familiarity with computing the prefix/suffix sum arrays. Plus I assume the points are given in the array $arr$ .

Now I describe the algorithm.

1. It can be argued that one of the corner points of the square sub-grid we make should be a point from the set of points that is given to us. Thus for each point from $(x,y)$ from the set of points given to us, we consider the four possible squares, one with $(x,y)$ as bottom left corner, one with $(x,y)$ as top right corner, one with $(x,y)$ as bottom right corner and one with $(x,y)$ as bottom left corner.
2. I describe it for one case say when $(x,y)$ is bottom left corner of a square grid with size $L$ ( as to calculate $S$ we should take the side of the square sub-grid as long as possible which is $L$ ). That is our question reduces to finding the sum of weights of points in the red region in the figure below.
3. I have labelled the sum of weights of the other eight regions by using letters $a$-$h$. One way to calculate the sum of weights of the red region is to subtract the from total $a+b+c+d+e+f+g+h$.
4. I can calculate $b+a+h$ by using combination of binary search and prefix/suffix sum arrays. In a similar manner I can find the sums $b+c+d$,$d+e+f$ and $h+g+f$. But now the problem is that I have summed each of $b$,$h$,$d$ and $f$ twice. Thus I need to find the sum of weights $b$,$h$,$d$ and $f$ separately.
5. You can find the sum $h$ ( and similarly the three others ) using segment tree in $O(log(n)^2)$ where $n$ is the total number of points given. The trick is to build the segment tree on say the $x$ co-ordinate. And if there is a node in the segment tree denoting the range $i$-$j$ ( $1 \le i \le j\le n$ ) then that node should store the $y$ co-ordinates of all points of array $arr$ from index $i$ to $j$ in sorted order, plus a suffix sum array for the same sorted array ( this is the main point, comment if you can't understand ). In this way by combination of querying on segment tree and binary search ( thus the $O(log(n)^2)$ factor comes ) you can find the sum of weights $h$.
6. So in nutshell you repeat the procedure for each point from the given set and for each point you try all $4$ square-sub grids of length $L$ and then select the one having maximum sum of the red region overall. The complexity will come out to be $O(nlog(n)^2)$ which is sufficient to pass the online judge. • I'm a bit confused. This answer seems to describe looking at a sub grid of side length exactly $L$, but the problem statement requests that you search over all sub grids of side length at most $L$. How does your solution handle that? – D.W. Sep 15 '16 at 13:35
• @D.W. In my first two points I argue it would suffice to consider squares of maximum size ie. $L$ with a given point as it's corner point. – sashas Sep 15 '16 at 13:58
• @D.W. ( It would be optimal ) Basically it would suffice to take each of the given points $(x_i,y_i)$ and consider all the four squares of side $L$ having $x_i,y_i$ as the corner point. – sashas Sep 15 '16 at 14:01
• OK. Feedback on how to improve your answer: right now you don't say why it suffices to consider side length exactly $L$. As I think about it, it's probably not too hard to justify (it's because all grid weights are positive), but it might help to explain that explicitly. Nice algorithm! – D.W. Sep 15 '16 at 15:40
• @D.W. Thanks. I will surely make edit shortly to include your suggestion. – sashas Sep 15 '16 at 16:13