Hello community,

I was trying to solve this problem. I could not come up with a solution for the same.

Given an array A of N elements, you have top tell the minimum number of operations to sort the array. An operation is defined as follows:
1. Take two indexes [l, r] in the array.
2. Reverse the array elements (A[l], A[l+1], ..., A[r]).
E.g. : A = [3, 2, 1, 4]
Ans = 1.
Explanation: l = 0, r= 2. Flip [3, 2, 1] ==> A = [1,2,3,4]

Note:

I was trying to solve the easier version of the problem where I can only take a number K (<=N) and reverse the first K elements. This is known as Pancake sorting. I was trying to find the optimal number of reversals in pancake sorting.

Hey,

I was trying to solve this expected value problem. I was thinking of using indicator random variables and linearity of expectation but somehow couldn't arrive at the answer. Please help.

Problem: Given a number N, take any random permutation of numbers R = [1, 2, ..., N]. You need to find the expected number of special points in the resulting permutation. An element R[i] is special if:
1. R[i] = R[i-1] + R[i+1] (for 1 <=i <= N-2)
2. R[i] = 2*R[i+1] (for i==0)
3. R[i] = 2*R[i-1] (for i==N-1)

Return the denominator and numerator of the answer. (Fraction should not be further reducible)