Talk:UVa 10970

Apparrently neither the author of the task, nor the author of the original description has the necessary insight :) I added a much easier solution ;) --Misof 08:56, 4 Dec 2005 (EST)

Personally I think using DP to solve this qn is overkill. The solution I derived was n-1+n*(m-1) where n-1 are the cuts needed to cut up to form the columns and (n*m-1) are the cuts need to cut up each columnns into squares.

With further simplification, one get mn-1.

--Roticv 01:49, 5 Dec 2005 (EST)

It might be, but only in retrospect. It took me about 30 seconds to come up with the DP solution, and about another few minutes to code it fro scratch, without any need for proofs or anything, so that's what I did..

Larry 03:44, 5 Dec 2005 (EST)

Heh, "When you have a hammer, every problem looks like a nail." ;)

It is clear that one way of cutting it is to cut into columns and then each into rows (n - 1 + n(m - 1) as Roticv said), but it requires proof that however you cut it, you'll always take mn - 1 steps. But that can be proved without the "observe the invariant" trick that Misof used — if you came up with the idea for the DP, there is nothing more to it — $f(m,n) = \min_{1 \le k \le m-1} (1 + f(k,n) + f(m-k,n)) = \min_{1 \leq k \leq m-1} (1 + kn-1 + (m-k)n-1) = \min_{1 \leq k \leq m-1} (mn-1) = mn-1$ Aboyner 04:45, 5 Dec 2005 (EST)

Technicalities:

- Aboyner's idea of the proof is correct, but if we want it in the article, we should make it more precise, probably drop a hint about mathematical induction.

- While the formula works, it is not correctly constructed. We do not know whether the first cut will be a row cut or a column cut, thus we should loop over all possible rows and then over all possible columns. --Misof 12:42, 5 Dec 2005 (EST)