#1
|
|||
|
|||
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. |
#2
|
|||
|
|||
Re: Excel Deleting Problem
I think it's pretty trivial. I'll be astonished if the answer is not n. It's clear it takes no more than n, so the "hard" part would be showing you can't do it in fewer. I'm pretty sure you can do this inductively easily.
|
#3
|
|||
|
|||
Re: Excel Deleting Problem
Actually, proving it is bound by n as a lower bound is easy. Every cell on the diagonal needs to be deleted, and can only be deleted if you have it in the corner of a deletion. There are n notches, therefore you must do at least n deletions.
Boo. |
#4
|
|||
|
|||
Re: Excel Deleting Problem
Just do a multi-select on all the X's, select delete, and then shift cells left. One deletion.
aloiz |
#5
|
|||
|
|||
Re: Excel Deleting Problem
Uhh, that deletes O's or you aren't explaining yourself very well.
|
#6
|
|||
|
|||
Re: Excel Deleting Problem
Technically, you can do it all in 1 deletion by holding down CTRL and single clicking every cell, then hitting delete..once.
|
|
|