Lesson 3

Optional Problems.

1. (20 points) A derangement is a permutation \(p\) of \([n]\) such that \(p[i] \neq i\) for all \(i\). Design an algorithm to find the \(k\)-th lexicographically ordered derangement of size \(n\) in time \(O(n^{2})\).
2. (20 points) Describe an algorithm that, for a given sequence of \(n\) positive integers, checks if it is possible to partition these numbers into three parts with equal sums in \(O(ns^{2})\) time, where \(s\) is the sum of these numbers.
3. (20 points) Given a string \(S\) of length \(n\), determine the total number of its palindromic subsequences. You are required to solve this problem within \(O(n^{2})\) time complexity and \(O(n)\) space complexity.
4. (20 points) Given two strings, \(s\) and \(t\), over the lowercase Latin alphabet, you are required to delete zero or more characters from each of them. The goal is to obtain two identical strings. The resulting common string must have the maximum possible length. For instance, if the given sequences are \(acbaaba\) and \(bcacb\), the longest common subsequences have a length of 3. Examples of such subsequences include \(acb\), \(bab\), and \(cab\). Your task is to find the specific longest common subsequence that comes first in lexicographical order in time \(O(|s| \cdot |t|)\).
5. (30 points) Assume that one needs to compute the dynamic programming values for all \(1 \le i \le j \le n\), which are defined by the following recurrence relation: \[\operatorname{dp}(i, j) = C(i, j) + \min_{i \le k < j}\{\operatorname{dp}(i, k) + \operatorname{dp}(k+1, j)\}.\] The base case is given by \(\operatorname{dp}(i, i) = 0\).

   The cost function \(C(i, j)\) satisfies two important properties for any integers \(a \le b \le c \le d\):

   • (Monotonicity)  \(C(b, c) \le C(a, d)\);
   
   
   • (QI)  \(C(a, c) + C(b, d) \le C(a, d) + C(b, c)\).

   A standard algorithm to solve this problem involves three nested loops, resulting in a time complexity of \(O(n^{3})\). Show that this dynamic programming can be calculated in time \(O(n^{2})\).

   Hint:

   The core idea behind the optimization is to reduce the search space. Let's define \(\operatorname{opt}(i, j)\) as the smallest index \(k\) in the range \([i, j-1]\) that minimizes the expression for \(\operatorname{dp}(i, j)\): \[\operatorname{opt}(i, j) = \arg\min_{i \le k < j}\{\operatorname{dp}(i, k) + \operatorname{dp}(k+1, j)\}.\] It can be proven that if the cost function \(C(i, j)\) satisfies the quadrangle inequality and is monotone, then the optimal split points themselves exhibit a monotonic property: \[\operatorname{opt}(i, j-1) \le \operatorname{opt}(i, j) \le \operatorname{opt}(i+1, j).\]