0

I have sequences of brackets like this [ > ) ]. I have to add brackets to the sequence that result would appear in this way [<> ()] because this is an optimal solution to the sequence. The approach to this problem is matrix chain multiplication and dynamic programming.

Explanation: Sequence of brackets [ > ) ] equates to M1 M2 M3 M4 matrices. How should I match the brackets and matrices dimensions? Matrices multiplication can be done if their inner dimensions are equal. So make one set of dimensions for all cases would be wrong. 

[ - M1(2x3)
] - M2(3x4)
( - M3(4x5)
) - M4(5x6)
< - M5(6x7)
> - M6(7x8)

Then the sequence of brackets we could interpret like this: [ > ) ] = (2x3 * 7x8 * 5x6 * 3x4). Obviously this is a wrong approach.

Please I would appreciate any ideas how to solve this.

Bob
  • 111
  • Please clarify what do you mean under "optimal solution for the sequence". How brackets are connected with some matrices? It is not clear. – sooobus May 20 '16 at 08:51
  • Well we can place them like [<> ()] and like [ ] <> () [ ]. As we can see the second result requires two more brackets to complete the sequence. Than the 2nd solution would be wrong. How brackets are connected with some matrices? Lets imagine a symbol [ is a definition of matrix A1 and < equals to matrix A2..... All this matrices(brackets as we have assumed) have their own dimensions. – Bob May 20 '16 at 09:03
  • @sooobus Also you can check the task link – Bob May 20 '16 at 09:14
  • Utterly incomprehensible. – Gerry Myerson May 20 '16 at 09:36
  • I still have no idea why do you try to use matrices to solve this task. I am almost sure that right answer for the length is just the minimal number of braces to keep balance. And there should exist a greedy way to place these braces (not actually sure about the greedy way, maybe some dynamic programming). – sooobus May 20 '16 at 11:19
  • Anyway, edit your question in order to delete matrices and so on and keep only the task itself and maybe a short comment on your approach. I succeeded in understanding the problem only after reading the task, and it can't be done by most users because it's in Russian. Also you can try asking at cs.stackexchange.com – sooobus May 20 '16 at 11:22
  • Check out this link. Almost the solution, uses dynamic programming http://acm.khpnets.info/w/index.php?title=%D0%94%D0%B8%D0%BD%D0%B0%D0%BC%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%BE%D0%B5_%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5#.D0.A7.D0.B8.D1.81.D0.BB.D0.BE_.D1.81.D0.BF.D0.BE.D1.81.D0.BE.D0.B1.D0.BE.D0.B2_.D0.B2.D0.BE.D1.81.D1.81.D1.82.D0.B0.D0.BD.D0.BE.D0.B2.D0.BB.D0.B5.D0.BD.D0.B8.D1.8F_.D1.81.D0.BA.D0.BE.D0.B1.D0.BE.D0.BA_.D0.B7.D0.B0.D0.BC.D0.B5.D0.BD.D0.BE.D0.B9 – sooobus May 20 '16 at 11:26
  • @soobus I think the link you posted is exactly what I need. Thank you. And you were right my approach to solve the problem is not exactly the same as matrix multiplication problem offers. It can be helpful only at use of concept of matrices. – Bob May 20 '16 at 11:55

0 Answers0