Excel Deleting Problem
Suppose you have a block of cell's in a "triangle" you want to "delete". You can delete them by selecting a rectangle.
For example:
Here is a triangle of length 6.
XOOOOO
XXOOOO
XXXOOO
XXXXOO
XXXXXO
XXXXXX
And you want to delete the X's.
OOOOO
OOOO
OOO
OO
O
So one deletion could be:
OOOOO
XOOOO
XXOOO
XXXOO
XXXXO
XXXXX, since I can delete a rectangle of cells in the first column. I can delete multiple rows and columns, but must delete an entire rectangle.
So the question:
For a triangle of size n, what is the least number of deletions to get rid of all of the X's?
What is the algorithm for it?
This question may be interesting or extremely trivial, and I don't know the answer either.
|