Remember that this is the 4-th SRM in the python experiment. This time I felt really fast when solving the div1 250 pointer. When python helps, it really helps. Unfortunately...
Div1 250: Square, points, etc.
You are given up to 100 pair-wise distinct, lattice points with coordinates with absolute value up to 10^9. Find the minimum area square with lattice vertices and side paralel to the x and y axises that strictly contains at least `K` of the input points.
So I code my initial idea: One of the optimal squares will have a bottom-left corner equal to (x-1,y-1) for some point (x,y) in the input. Try all `O(n)` of such candidate corners. Once you fix a corner, you just need the side length. We can just binary search for the smallest `L` such that the square will strictly contain all those points.
FAST submission! I was first in room for a while and was happy.
This is a complex dp/implementation problem mix. Eventually decided to skip it. I had no idea how to work around the high constraint for `K`. And I am tired after staying late trying to do SRM 613's editorial. Plus I won't have to solve this problem anyway because I am not writing SRM 614.
Oh boy, I am so happy I am not writing this editorial.
Back to Div1 250
So I decided it was best to start writing this blog post. As I was explaining the div1 250, I noticed: My logic is wrong! The test cases were awfully weak in this case. In reality, if the optimal corner is `(x-1,y-1)` , then `(x,y)` is not necessarily a point in the input. x and y could come from different points. The counter example is simple, points: `(0,3), (1,3), (2,3), (3,3), (3,2), (3,1), (3,0)` and `K = 6`. The best square has `x = -1` and `y = -1`.
By the time I noticed this, it was incredibly late. The resubmit was very costly, I hope to be able to compensate by finding similar mistakes in the challenge phase.
The python code is lovely though:
def binarySearch(f, lo, hi): # f(hi) and not f(lo) while lo + 1 < hi: ha = (lo + hi) / 2 if f(ha): hi = ha else: lo = ha return hi class MinimumSquare: def minArea(self, X, Y, K): points = zip(X,Y) res = 10**20 # oops, initial submission had: for (x,y) in points instead of for x in X: for y in Y: # find smallest square with bottom-left corner (x-1, y-1) def canIt(L): return sum( (x-1 < xi < x-1+L) and (y-1 < yi < y-1+L) for (xi,yi) in points) >= K if canIt(res) : res = min(res, binarySearch( canIt, 0, res) ) return res ** 2
Take a look to the beautiful binary search, thanks to first class functions I can do binary search on a higher level, rather than mixing it with other code.
Post will be created automatically once the challenge phase ends.