3292 - Matrissor (From Dhaka 2005-2006)

Do you want to discuss about these problems? Go now!
Users are shared (no need to re-register).

Moderator: Board moderators

Rostislav
New poster
Posts: 21
Joined: Sun Oct 05, 2003 11:19 am
Location: Bulgaria, Shoumen
Contact:

Post by Rostislav » Sat Nov 26, 2005 8:53 pm

Matrix #1
3
2
2
2
2
2
2
1

Solaris
Learning poster
Posts: 99
Joined: Sun Apr 06, 2003 5:53 am
Location: Dhaka, Bangladesh
Contact:

Post by Solaris » Sun Nov 27, 2005 8:21 am

thanks Rosti for your quick reply ... my code matches your output too... but still WA ... I am out of idea now :(
Where's the "Any" key?

User avatar
shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

Post by shamim » Mon Nov 28, 2005 7:39 am

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?

aminallam
New poster
Posts: 39
Joined: Thu Dec 08, 2005 12:51 pm
Location: Suez, Egypt.

Post by aminallam » Thu Dec 08, 2005 1:18 pm

I agree with you. Although I have known the algorithm to make it work, I do not know why it works. I thought of a lot of time.
I would like that someone who understands this problem well to explain it to us. (Why it works, and what is the way of thinking that leads to this solution).
Thanks a lot.

Post Reply

Return to “ACM ICPC Archive Board”