BUILDING - Editorial

editorial
, , ,
1

PROBLEM LINKS

Practice
Contest

DIFFICULTY

MEDIUM

EXPLANATION

This problem will be easier to solve if the square needed has edges paralleled to the axes. So the task now is transforming this problem to that. To do it, we do “rotate” the axes by an angel of 45°, calculate the new co-ordinates and solve the problem like doing with the squares having edges paralleled to the new axes. All the converting formula are simple!
Complexity: O(w×h).

1 Like
2

why none of the accepted solutions , seems to be using the above suggested method ? I’m trying to understand how dp is applied to this problem . any suggestions ?

3

still not able to solve this. can you give more hints or add more details to the editorial ?