# Help with solving this problem

• 11-20-2010
Neox
Help with solving this problem
How would I be able to solve the problem given on this URL?

DWITE - October 2010 - Power Tiles

By the way dwite is a programming contest for middle/highschools, this was from the last contest and we had no clue what to do.

I know how to do the input/output files, and powers of 2. But I don't know how to determine the minimum number of tiles.
• 11-20-2010
MWAAAHAAA
Interesting little problem.

Hint #1: the number of tiles required will be minimum when tiles are chosen with maximum possible area.
• 11-20-2010
Neox
I've thought about that but I don't think it works.

In the example, for a 5 by 6 floor. One 4 by 4, two 2 by 2, and six 1 by 1 tiles are chosen. These add up to 9 tiles.

If I make a program that chooses tiles with the maximum possible area I will get this.

One 4 by 4, 16 out of 30 is filled, 14 possible spaces are left

three 2 by 2, (3 * 4) 12 out of 14, 2 spaces are left

and finally two 1 by 1. Mine will add up to 6 tiles.

These don't match because my tiles won't fit a 5 by 6 floor, however they will have the same area as a 5 by 6 floor.
• 11-20-2010
MWAAAHAAA
Quote:

Originally Posted by Neox
These don't match because my tiles won't fit a 5 by 6 floor, however they will have the same area as a 5 by 6 floor.

Exactly! So we can conclude it is not just a numbers game, but we have to take into account the geometry, right?

So, when we place the 4 x 4 tile on the 5 x 6 floor, we effectively subdivided the original square into a number of distinct regions (1 square occupied 4 x 4 tile, and 1 non-square region). Now the problem has shifted towards how to partition the non-square region, and we are left with the original problem we just solved (recursion/iteration anyone?).
• 11-20-2010
Neox
ugh.. I just can't seem seem to figure out how to partition the non-square region

#
#
#
#
#####
#####

trust me I've tried... I'm getting nowhere
• 11-20-2010
MWAAAHAAA
Quote:

Originally Posted by Neox
ugh.. I just can't seem seem to figure out how to partition the non-square region

#
#
#
#
#####
#####

trust me I've tried... I'm getting nowhere

Instead of thinking of the tile as blotting out a rectangular area of the floor, imagine that the two of the sides of this rectangle, when extended to the boundaries of the floor, actually partition the floor in *four* *rectangular* regions.