So, I was looking through my notes to find what I've written in my spare time. Turns out, I have this problem written in one of the notes.
I have an $$$N \times N$$$ square grid that needs to be fully covered with tiles. I can only use square tiles with the size of $$$i \times i$$$ where $$$1 \leq i \leq M$$$ to fill it. What is the minimum number of tiles needed to be used to fully cover the grid?
For example: If $$$N = 9$$$ and $$$M = 5$$$, then the minimum number of tiles needed is $$$9$$$, since I can use nine $$$3 \times 3$$$ square tiles to fully cover the $$$9 \times 9$$$ grid.
Constraint: $$$1 \leq M \leq N$$$
Further Constraint: idk, since I don't know the fastest complexity for this.
What is the fastest complexity and how to achieve it? Is it just brute force or is there an efficient algorithm to solve this?
Edit: I just realised that this can be solved in around $$$O(N^2M)$$$ using simple DP. But can it be solved faster than that?
Edit 2: Turns out, some value of $$$N$$$ and $$$M$$$ can't be solved with the simple DP. See this.
Auto comment: topic has been updated by KitasCraft (previous revision, new revision, compare).
sorry, but how are you supposed to solve this problem with DP? i can't come up with the solution. thanks! :)
Basically, define $$$dp_{i,j}$$$ as number of minimum tiles needed to cover grid with the size of $$$i \times j$$$. To count $$$dp_{i,j}$$$, find the minimum between $$$\min(dp_{i,a}+dp_{i,j-a})$$$ and $$$\min(dp_{b,j}+dp_{i-b,j})$$$ for $$$1 \leq a \leq j-1$$$ and $$$1 \leq b \leq i-1$$$ if $$$i,j > M$$$ or $$$i \neq j$$$. For $$$i,j \leq M$$$ and $$$i=j$$$, the value of $$$dp_{i,j}$$$ is always $$$1$$$ (obviously). I'm pretty sure you only need to check this since the grid must formed by square tiles, which means the grid can always be split into two different grid sizes (if the optimal tiling sequence needs more than $$$1$$$ tile). $$$O(N^2)$$$ states with $$$O(N)$$$ transition results in $$$O(N^3)$$$ time complexity.
Edit: Turns out, an $$$O(M)$$$ transition is possible as pointed by this user by changing the checking constraint from $$$1 \leq a \leq j-1$$$ and $$$1 \leq b \leq i-1$$$ to $$$1 \leq a \leq \min(\frac{j-1}{2},M)$$$ and $$$1 \leq b \leq \min(\frac{i-1}{2},M)$$$.
thank you! really appreciate it.
This DP is wrong. The problem With $$$N=M$$$ and small $$$N$$$ is sometimes asked for rectangles (https://leetcode.com/problems/tiling-a-rectangle-with-the-fewest-squares/) and the solution is not always to cut it along one line into two rectangles. Things like this can be needed: http://www.squaring.net/sq/ss/siss/o13/o13siss.pdf
This condition should be true -> i*(Something) == N (So, N must be divisible by i). Therefore, Let x be the max value of i (1 <= i <= M) that divides the N. Then the answer should be (N/x)^2.
Time Complexity = O(M).
But what if $$$N = 8$$$ and $$$M = 3$$$? The optimal tiling sequence consist of four $$$3 \times 3$$$ grid and seven $$$2 \times 2$$$ grid, which is $$$11$$$ tiles.
Yeah, I was thinking that the tiles are identical in size (between 1 and M). if it is not the case, I am wrong.
The answer for n = 9*9 and m = 5 should be 6 no? 25 + 25 + 25 + 4 + 1 + 1. Brute force solution is O(n^2*m) [DP] but I feel intuitively greedy solution should work here and that would be O(m).
How do you fit this in the grid tho?
Nvm,I understood the question incorrectly.
I think your greedy solution doesn't work in your problem ($$$n = 4$$$, $$$m = 3$$$, the optimal solution is $$$4+4+4+4$$$, greedy produces $$$9+4+1+1+1$$$).
Auto comment: topic has been updated by KitasCraft (previous revision, new revision, compare).
Auto comment: topic has been updated by KitasCraft (previous revision, new revision, compare).