PROBLEM LINK:
Author: Yuri Shilyaev
Tester: Hasan Jaddouh
Editorialist: Yury Shilyaev
DIFFICULTY:
Hard
PREREQUISITES:
Binary search, sweep line, binary indexed tree.
PROBLEM:
You are given N points (X_i, Y_i) on plane. You are allowed to place squares with arbitrary side in any integer coordinates, but each square can be placed only if it contains at least 3 points inside it. The task is to cover all the points with squares, minimizing the side of the largest square placed.
QUICK EXPLANATION:
Let’s binary search the answer, let the current proposed answer is D. Imagine you placed all the possible squares with side equal to D, how to check that they cover all the points?
EXPLANATION:
Let \{X, Y\} be a square with side D placed such that it’s down left corner is in (X, Y). Note that a specific point (X_i, Y_i) could be covered only by squares \{x \in [X_i - D, X_i], y \in [Y_i - D, Y_i]\}. This is also a square with side equal to D. Let’s replace our points (X_i, Y_i) to the corresponding squares described above. The problem of checking the binary search condition is now reduced to checking for each square from new N, that this square has an intersection of other two squares inside. Such intersection would mean that there is a square that covers this point and some other two at the same time.
The main observation is that any intersection of three squares contains at least one corner of some square inside it.
Let’s use it. Leave only 4 \cdot N corners of the squares and for each let’s find how many squares cover this point. This could be done with a sweep line and binary indexed tree in O(N \cdot log(N)). The queries are add on subrange and get at point, so this would be not a classic usage of BIT, but with idea of prefix sums.
Of course, we should leave only corners that are covered by at least 3 squares after we found this value for each corner.
The last part is to find for each square if it contains at least 1 corner from those leaved inside. Let’s use our combination of sweep line and BIT for another time. This time, the queries are add at point and sum on subrange, so we the usage of BIT is as usual.
The total complexity per testcase is O(N \cdot log^2(N)).
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.