Matrix #1
3
2
2
2
2
2
2
1
3292 - Matrissor (From Dhaka 2005-2006)
Moderator: Board moderators
I have read the description of mf's algorithm and understand how his example works.
But I still don't get how it resolves the issue of partitions like ...
()..()..() ().
From what I understand, whenever an interval is divided in two, one should consider whether it is possible to just append the last few matrices to the end of a sequence and evaluate those together.
That is, ()* last one,
or () * last two,
or () * last three
and so on and use the one that requires least amount of matrissors and within the capacity of matrissor.
But it doesn't consider multiple partitioning like the one I mentioned above, or does it?
But I still don't get how it resolves the issue of partitions like ...
()..()..() ().
From what I understand, whenever an interval is divided in two, one should consider whether it is possible to just append the last few matrices to the end of a sequence and evaluate those together.
That is, ()* last one,
or () * last two,
or () * last three
and so on and use the one that requires least amount of matrissors and within the capacity of matrissor.
But it doesn't consider multiple partitioning like the one I mentioned above, or does it?