1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ @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. $\endgroup$ – userforfun Aug 14 '16 at 2:27
  • 2
    $\begingroup$ 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. $\endgroup$ – D.W. Aug 14 '16 at 4:09
  • 1
    $\begingroup$ @userforfun wait for the contest to get over. Codechef posts very good editorials after the contest. Read that. $\endgroup$ – sashas Aug 14 '16 at 8:05
  • $\begingroup$ @sasha Now the contest has ended. So could you give the answer. $\endgroup$ – userforfun Aug 15 '16 at 10:04
2
$\begingroup$

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.

enter image description here

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – D.W. Sep 15 '16 at 13:35
  • $\begingroup$ @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. $\endgroup$ – sashas Sep 15 '16 at 13:58
  • $\begingroup$ @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. $\endgroup$ – sashas Sep 15 '16 at 14:01
  • $\begingroup$ 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! $\endgroup$ – D.W. Sep 15 '16 at 15:40
  • $\begingroup$ @D.W. Thanks. I will surely make edit shortly to include your suggestion. $\endgroup$ – sashas Sep 15 '16 at 16:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.