## Saturday, March 29, 2014

### SRM 614: Cursed weak test cases

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.

## Div1 525

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.

## Div1 1000

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.