(Note: the editorials are written in a hurry and without having solved the problems, so there may be mistakes. Feel free to correct them / inform me.)
PROBLEM LINK:
Author: Rishabh Jain
Tester: Sergey Kulik
Editorialist: Xellos
DIFFICULTY:
MEDIUM
PREREQUISITES:
sweepline, segment tree
PROBLEM:
Given N points with weights, find the largest sum of weights within an axis-parallel square of side length L. Then, find the smallest axis-parallel square with sum S inside it.
QUICK EXPLANATION:
Given L, move a sweepline and add/remove points; remember subsegment sums in a segment tree. Binary-search the smallest side length.
EXPLANATION:
First of all, let’s get computing the smallest L out of the way. Suppose that we can compute the maximum S for given L; it’s clear that when L increases, S can’t decrease, so we can binary-search the smallest L that gives at least the given S. That contributes to the time complexity by a factor \log{L_{max}}.
So how to compute the maximum S? We can start by sorting the points by their x-coordinate. Then, we can move a sweepline corresponding to the right end of our square from left to right, add points that are crossed by this sweepline to the set of points that can be in our square and remove from that set all points that end up further than L to the left from the sweepline. This way, each point can only be added and removed once and we don’t have to bother with x-coordinates anymore.
Our problem now changes to this: find the maximum sum of weights of points from the given set whose y-coordinates belong to an interval of length \le L. We’re looking for the maximum of sums of weights within [y,y+L] for each y; when a point at y_i with weight w_i is added, the sums for y_i-L \le y \le y_i increase by w_i and when it’s removed, they decrease by w_i. And it’s well-known that a data structure that supports range add / find maximum is a segment tree with lazy propagation; there are plenty other resources about it online, too.
There are O(N) additions/removals/maximum queries in the segment tree, which holds y_{max} vertices, so the time complexity of finding S is O(y_{max}+N\log{y_{max}}) and of finding the minimum L is O(y_{max}\log{y_{max}}+N\log^2{y_{max}}); the memory complexity is O(y_{max}+N).
AUTHOR’S AND TESTER’S SOLUTIONS:
The author’s solution can be found here.
The tester’s solution can be found here.