Problem 6. The CSP problem (constraint satisfaction problem) is defined as follows. Given a positive integer n, and k constraints of the form (x, y, z), where x, y, z [n] are distinct integers, the problem is to output a permutation = 1, . . . , n of [n] satisfying as many constraints as possible. The permutation satisfies a constraint (x, y, z) if y lies between x and z in the listing 1, . . . , n. (Note: it does not matter if x lies before y and z lies after, or vice versa.) It is known that this problem is NP-hard. Let opt denote the maximum number of constraints that can be satisfied by any permutation for a given instance of the problem. Design a randomized algorithm whose output is a permutation that satisfies at least opt constraints, on average, where > 0 is a constant. Specify the best you can prove, i.e. as close to 1 as possible.