Here is a problem that I've been given to solve in time $O(n^2|\Sigma|)$.

Given an alphabet $\Sigma$ and the product of every two elements in this alphabet (i.e., an arbitrary mapping $\cdot\colon \Sigma^2 \to \Sigma$), find an algorithm that determines whether we can parenthesize the expression $x_1 \cdot x_2 ֿ\cdot \cdots \cdot x_n$ (where $x_1,\ldots,x_n \in \Sigma$) so that the product equals a given element $x \in \Sigma$.

What I have tried so far is solving it like matrix chain multiplication, but that gives an algorithm running in $O(n^3|\Sigma|^2)$. How can this problem be solved in $O(n^2|\Sigma|)$?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.