Topic

z-rectangl : why this fails

darkspirit2009-05-31 15:57:12

int solve(int X, int Y){
if (X==Y) return 1;
if (X>Y) return solve(X-Y, Y) + 1;
return solve(X, Y-X) + 1;
}

picsel2009-05-31 16:04:27

5 6
Right answer: 5

Nikola942009-05-31 16:08:49

@picsel
no it isn't.

AAAAA
AAAAA
AAAAA
AAAAA
AAAAA
BCDEF

the answer is 6 :)

picsel2009-05-31 16:49:14

AAABB
AAABB
AAACC
DDDCC
DDDFF
DDDFF

Nikola942009-05-31 17:40:54

ups, i'm sorry, you're right, i never looked at it that way :)

darkspirit2009-05-31 19:02:58

I solved it, using dynamic programming, and the fact that when you form the square containing the lower right corner, one of the 2 curs you introduce (for the 2 "internal sides" of it) has to go on until it touches the edges of the big retangle. However, I don't know why this is true. Any reasoning / proof on this?
Thanks

ronioso2009-07-05 05:03:33

I don't have a proof but a counterexample:
11x13. Your algorithm gives 8.
Right answer is: 6
AAAACCCCFFFFF
AAAACCCCFFFFF
AAAACCCCFFFFF
AAAACCCCFFFFF
BBBBBBBDFFFFF
BBBBBBBEEEEEE
BBBBBBBEEEEEE
BBBBBBBEEEEEE
BBBBBBBEEEEEE
BBBBBBBEEEEEE
BBBBBBBEEEEEE