Optimal parenthesization of matrix-chain product

    1. Find an optimal parenthesization of matrix-chain product whose sequence of dimensions is (5, 10, 12, 5, 50, 6) 2. Show how to compute the length of an LCS using only 2 * min (m, n) entries in the c table plus O(1) additional space. Then show how to do this using min (m, n) entries plus O(1) additional space. 3. Sara is trying different ways to form the best team to represent our university in the Gulf Programming Contest. He is trying to find the number of ways he can form a team of 3 students out of S students. After thinking about the problem for a while, he realizes that actually this is a very well-known problem, which has been formulated in mathematics as follow. Find the number of ways r different items can be chosen from a set of n items, where r and n are nonnegative integers and r<=n. Suppose C(n, r) denotes the number of ways r different items can be chosen from a set of n items. Then C(n, r) is given by the following formula: C(n, r)=n!/(r!(n-r)!). Sara implemented a general solution using the above formula but he tested his solution with large value of n and r, it did not work correctly because factorial grows very fast. So he looked for a different solution. He came across the following formula: Otherwise So he implemented a recursive solution based on this formula but then when he tested his solution he found out that it is very slow for large value of n and r. Then he was asked by saif to suggest 1 or 2 problems for the UPC. Therefore, he submitted this problem. However, based on what he did he is advising you to write a non-recursive solution to the above general problem. Input The first line of input contains a single integer M, (1≤M≤1000) which is the number of datasets that follows. Each line of the dataset contains two numbers representing n and r (n≥r). Output For each dataset, you should generate one line of output with the following values: The dataset number as a decimal integer (start counting at one), and the number of way of choosing r out of n. Samples Sample Input Sample Output 3 5 3 7 3 40 20 1 10 2 35 3 137846528820