typedeftemplate's blog

Maximum side-length square that can be obtained from tiles
By typedeftemplate, history, 4 years ago, In English

Given M one-by-one tiles and N two-by-two tiles, what's the largest side-length of a square that you can make if the square must be completely filled in the middle?

I was recently asked this problem in an interview, and I came up with an incorrect dynamic programming approach. I did some sort of three-state DP with (m, n, k), where k is the current square side-length. From (m, n, k), we can transition to a state with k' = k + 1 by using some number of one-by-one tiles (around the border of the current square with side-length k), and we can transition to a state with k' = k + 2 by using some number of two-by-two tiles.

However, this is clearly not exhaustive: It doesn't take into account when we can use a combination of both tiles.

I think this might be purely a combinatorial problem. Could someone please help me with the right approach? Even after thinking for a few more days, I can't come up with a solution.

  • Vote: I like it
  • +4
  • Vote: I do not like it

»
4 years ago, # |
← Rev. 3   Vote: I like it +5 Vote: I do not like it

We can not build a square having length greater than sqrt(4*n+m).

Let x=sqrt(4*n+m).

if x is even then the whole x by x grid can be divide into 2 by 2 squares. So we will use the maximum possible 2 by 2 squares and since 4*n+m>=x*x so simply x is the answer.

if x is odd then the maximum possible 2 by 2 squares that can be used is ((x-1)*(x-1))/4; Let val1=((x-1)*(x-1))/4.

So 2 by 2 squares used will be min(val1,n); now if 4*min(val1,n)+m>=x*x then x is answer otherwise x-1 is the answer.

Hope it helps.

→ Reply
»
4 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

The side length of the square is either odd or even. If it's even, then we can always rearrange the tiles such that every four 1x1 tiles can be clumped together into a 2x2 tile. If it's odd, then we can rearrange it so that there's an "outer L" of 1x1 tiles around an even-side length square.

Suppose we wanted to make the largest even-length square. So, let's group every four 1x1 tiles into a single 2x2 tile. Now, we have M/4 + N 2x2 tiles to play with. The biggest square we can make with that many tiles has s = floor(sqrt(M/4+N)) tiles on each side. However, since the tiles are 2x2 in size, the actual side length is $$$2s$$$.

Okay, so $$$2s$$$ is the largest even-length square we can make so far. The only way we could improve it is if we can make it odd length. To do so, we need $$$2(2s)+1$$$ total 1x1 tiles to add the "L-frame" around one of the edges. Just check if you can do that.

So, in summary...

Let s = floor(sqrt(M/4+N)). We can construct a square that uses $$$s^2$$$ 2x2 tiles.

If it can be made entirely with 2x2 tiles (i.e. if $$$s^2 \leq N$$$), then great! Otherwise, we need to take $$$4(s^2 - N)$$$ different 1x1 tiles to complete it.

Then, look at all your leftover 1x1 tiles. If they are at least $$$4s+1$$$, then the answer is $$$2s+1$$$. Otherwise, the answer is $$$2s$$$.

→ Reply