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.