GATE Computer Science (CS) 2018 Shift 1 Solved Paper

Assume that multiplying a matrix ${\mathit{G}}_1$ of dimension $\mathit{p}\times \mathit{q}$ with another matrix ${\mathit{G}}_2$ of dimension $\mathit{q}\times \mathit{r}$ requires scalar multiplications. Computing the product of $\mathit{n}$ matrices ${\mathit{G}}_1{\mathit{G}}_2{\mathit{G}}_3....{\mathit{G}}_{\mathit{n}}$ can be done by parenthesizing in different ways. Define ${\mathit{G}}_{\mathit{i}}{\mathit{G}}_{\mathit{i}+1}$ as an explicitly computed pair for a given parenthesization if they are directly multiplied. For example, in the matrix multiplication chain ${\mathit{G}}_1{\mathit{G}}_2{\mathit{G}}_3{\mathit{G}}_4{\mathit{G}}_5{\mathit{G}}_6$ using parenthesization $\left({\mathit{G}}_1\left({\mathit{G}}_2{\mathit{G}}_3\right)\right)\left({\mathit{G}}_4\left({\mathit{G}}_5{\mathit{G}}_6\right)\right)\cdot {\mathit{G}}_2{\mathit{G}}_3$ and ${\mathit{G}}_5{\mathit{G}}_6$ are the only explicitly computed pairs.
Consider a matrix multiplication chain ${\mathit{F}}_1{\mathit{F}}_2{\mathit{F}}_3{\mathit{F}}_4{\mathit{F}}_5$, where matrices ${\mathit{F}}_1,{\mathit{F}}_2,{\mathit{F}}_3,{\mathit{F}}_4$ and ${\mathit{F}}_5$ are of dimensions $2\times 25,25\times 3,3\times 16,16\times 1$ and $1\times 1000$, respectively. In the parenthesization of ${\mathit{F}}_1{\mathit{F}}_2{\mathit{F}}_3{\mathit{F}}_4{\mathit{F}}_5$ that minimizes the total number of scalar multiplications, the explicitly computed pairs is\/are