SRM 629: A mistake

I think reading the problem statement is half the batte. Or actually, understanding the problem statement is half the battle.

Div1 250: The one with a rectangular hole

You have a rectangular hole of some possibly large dimensions. Also some boards that you can use to cover the rectangle. The boards are rectangles themselves. They may be rotated and overlap. But all of their corners must lie strictly outside the whole. Also the sides of the boards must be paralel to the sides of the hole. I put emphasis in all because I spent most of the match with the ridiculous assumption that only one of the corners must be outside the hole. This assumption makes no sense to be made because the statement is quite clear. I have no idea what happened, but this other variation of the problem seems very difficult, might even be impossible with the given constraints :/. Also note that the corners do not need to be put in integral coordinates, the statement doesn't mention this explicitly but an example needs this. Of course, you return the minimum number of boards needed to cover the rectangle. There are up to 50 boards.

So the trick to this problem is to notice that with the corner constraint, then all boards must be put in sequence either horizontally or vertically . Overlaps are not helpful. With this knowledge, we can first try horizontally and then vertically. As easy as swapping the dimensions of the rectangle, so we first try with W = holeW, H = holeH and then with H = holeW, W = holeH. The idea is that each board's height must be strictly larger than the hole's height (H). Then the board will cover a part of the width. Just find the top X possible widths, if those widths can cover the whole width W, then you have a result `t`. Note that when choosing each board's width and height we need to pick a good rotation...

import itertools

INF = 10**9

def minimumNumberInf(holeH, holeW, boardH, boardW):
    res = INF
    for (W,H) in ( (holeH,holeW), (holeW,holeH) ):
        # all vertical
        def correctWidths():
            for (wr,hr) in zip(boardH, boardW):
                best = -1
                for  (w,h) in ( (wr,hr), (hr,wr) ):
                    if h > H:
                        best = max(best, w)
                yield best
    
        widths = sorted( [ w for w in correctWidths() if w != -1 ] )
        
        if sum(widths) >= W:
            r = next( t for t in itertools.count(1) if sum(widths[-t:]) >= W )
            res = min(res, r ) 
    return res


class RectangleCovering:
 def minimumNumber(self, holeH, holeW, boardH, boardW):
    r = minimumNumberInf(holeH, holeW, boardH, boardW)
    return -1 if r >= INF else r

Because of the interpretation mistake, I took way too long to solve this problem. I also started the match a bit late so I didn't have time to read div1 500 either :/