The living space in your new apartment is a 2 x 2 -foot square (which you mental
ID: 3786003 • Letter: T
Question
The living space in your new apartment is a 2 x 2 -foot square (which you mentally divide into 22e cells, each 1 foot square). Bizarrely, exactly one cell of the floor is covered by carpet and the rest is bare cement (Figure 1 (b)). Fortunately, a friend has given you a pile of 22 carpet pieces. Each carpet piece is L shaped, formed by three 1-by-1 adjacent squares (Figure 1(a)). Each piece covers 3 cells, so you have just enough carpet to cover the whole cement part of the floor, if the pieces can fit. Your job is to find a way to lay the pieces so they cover the cement. The carpet should cover all cells except the covered one with no overlaps. You may not cut the carpet pieces you have to use them as they are but it is fine to rotate them. (b) (a) Figure 1: (a) A carpet piece in one of its 4 possible orientations. (b) A 16 x 16 floor with one covered cell.Explanation / Answer
(A) Algorithm: This is a standard trimono puzzle.
1. Let n=2^k. Divide the square into 4, n/2 by n/2 squares.
2. Place the carpet piece at the center, where the carpet piece does not overlap the n/2 by n/2 square which was earlier missing out 1 by 1 square.
3. Solve each of the four n/2 by n/2 boards inductively.
Pseudocode:
Let List l be the triplets list where a triplet t will contain 3 (x,y) coordinates.
Let (x,y) be the initial point which is covered by carpet.
Input: Grid[2^k][2^k]
and Grid[x][y] = -1;
Let n = 2^k
tileRec(int n, int x, int y) :
if(n==2) : //base case
Triplet t;
for (int i=0; i<n; i++)
for (int j=0; j<n; j++)
if (grid[x+i][y+j] == 0)
t.add(x+i,y+j);
l.add(t)
else:
//Find coordinates of hole covered by carpet
Let (a,b) be the hole
for (int i=x; i<x+n; i++)
for (int j=y; j<y+n; j++)
if (grid[i][j] != 0) {
a = i;
b = j;
}
//Hole in upper left quadrant.
if (a < x + n/2 && b < y + n/2) {
tileRec(n/2, x, y);
t.add(x+n/2,y+n/2-1);
t.add(x+n/2,y+n/2);
t.add(x+n/2-1,y+n/2);
l.add(t);
// Now we can make our three other recursive calls.
tileRec(n/2, x, y+n/2);
tileRec(n/2, x+n/2, y);
tileRec(n/2, x+n/2, y+n/2);
}
//Hole in upper right quadrant
else if ((a < x + n/2 && b >= y + n/2)) {
tileRec(n/2, x, y+n/2);
t.add(x+n/2,y+n/2-1);
t.add(x+n/2,y+n/2);
t.add(x+n/2-1,y+n/2-1);
l.add(t);
// Now we can make our three other recursive calls.
tileRec(n/2, x, y);
tileRec(n/2, x+n/2, y);
tileRec(n/2, x+n/2, y+n/2);
}
//Hole in bottom left quadrant
else if (a >= x + n/2 && b < y + n/2) {
tileRec(n/2, x+n/2, y);
t.add(x+n/2-1,y+n/2);
t.add(x+n/2,y+n/2);
t.add(x+n/2-1,y+n/2-1);
l.add(t);
// Now we can make our three other recursive calls.
tileRec(n/2, x, y);
tileRec(n/2, x, y+n/2);
tileRec(n/2, x+n/2, y+n/2);
} else {
tileRec(n/2, x+n/2, y+n/2);
t.add(x+n/2-1,y+n/2);
t.add(x+n/2,y+n/2-1);
t.add(x+n/2-1,y+n/2-1);
l.add(t);
// Now we can make our three other recursive calls.
tileRec(n/2, x+n/2, y);
tileRec(n/2, x, y+n/2);
tileRec(n/2, x, y);
}
(B): We can prove it through mathematical induction.
Basic step: k=1. 2^1 * 2^1=4. There are 4 squares. If one is removed, then three squares can be filled with one carpet piece.
Induction step: We need to prove k+1 should be true.
2^(k+1) * 2^(k+1) = 2.2^k * 2.2^k = 2^k * 2^k * 4
can consider 4 squares of size 2^k and 2^k. Therefore they can be filled.
(C)
Complexity: T(n) = 4T(n/2) + c.
As we are dividing the problem into 4 subparts.
By Master Method:
1. If f(n) = (nc) where c < Logba then T(n) = (nLogba)
2. If f(n) = (nc) where c = Logba then T(n) = (ncLog n)
3.If f(n) = (nc) where c > Logba then T(n) = (f(n))
By solving we will get O(n^2).
Also, There are (n^2 1)/3 tiles to be placed, and placing each tile takes O(1) time. Hence O(n2).
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.