CCC "22 J5

Problem J5 - Square pool

Problem Description: 

Ron wants to build a square pool in his square N-by-N yard, but his yard contains T trees. Your job is to determine the side length of the largest square pool he can build. 

Input Specification: 

The first line of input will be an integer N with N ≥ 2. The second line will be the positive integer T where T < N² . The remaining input will be T lines, each representing the location of a single tree. The location is given by two positive integers, R and then C, separated by a single space. Each tree is located at row R and column C where rows are numbered from top to bottom from 1 to N and columns are numbered from left to right from 1 to N. No two trees are at the same location.

Output Specification:

Output one line containing M which is the largest positive integer such that some M-by-M square contained entirely in Ron’s yard does not contain any of the T trees.

First Approach:

The first and most obvious approach is to brute force the question by testing every possible square pool and take the maximum size amongst these as the response. However, naturally, this only gets us half the marks. The motivation from here however is to realise that there are far fewer trees, T, compared to the N² tiles from the specification and so we may want to design an algorithm that scales with the number of trees.

Second Approach:

By analysing each tree we know that the greatest pool must either to the left, right, top or bottom of the tree meaning that each tree subdivides the area wherein the biggest square pool could reside. Considering all the valid subsections of the larger area and comparing them we get the maximum square. For smaller values of T the algorithm performs well, however the time complexity of the algorithm is an exponential in O(4ᵀ) which quickly becomes infeasible.

Final Approach:

We see that we are on the right track, but there must be a better way of recursing through the areas by skipping the subareas we can invalidate with our knowledge whilst looping. This encourages us to use a dynamic programming approach. This approach utilises a 3D arrays, with dimensions (T+1)x(T+1)x(T+1). The first two dimensions of the array represent the coordinates of the top-left corner of a square pool, and the third dimension represents the size of the square pool.

The algorithm starts by initialising all the elements of the 3D arrays to 0, indicating that no square pool can be built using the specific tree as one of the corners. Then, for each tree, it updates the value of the element corresponding to its location, setting it to 1, indicating that a square pool of size 1x1 can be built using that tree as one of the corners.

The algorithm then iterates through all the trees, starting from the tree with the largest size of the square pool and moving towards the tree with the smallest size. For each tree, it updates the value of the element corresponding to each possible top-left corner of the square pool, setting it to the minimum of the values of the elements corresponding to the bottom-right corner of the square pool. This way, the algorithm can efficiently memoize the maximum size of the square pool that can be bounded at each location. The time complexity of this approach is O(T^3).