Hi everyone ! Can anyone knows the expected number of elements p[i] with the following property in a permutation of size N ? Property: p[i-1] < p[i] > p[i+1] i.e., it is the local maxima in the permutation ? Note : Please do mention the mathematical proof if possible !

You can use the "Contribution to the sum" technique (Have a look into this post)

It's not clear how can i apply this technique to solve the above problem . Can you explain how ?

If I'm correct, for each $$$1<i<n$$$ , the possibility that it is the biggest one among $$$p_{i-1},p_i,p_{i+1}$$$ is $$$\frac{1}{3}$$$, so the answer is $$$\frac{n-2}{3}$$$

How all the events for 1 < i < n can be independent and we adding here simply , since if p[i] is max then why the p[i + 1] is max will carry 1/3 probability ? What my rough guess is it should be O(log(N)) cause let the max element is in the middle and then the next smaller element will be possibly found in N/2 elements to the left or the right and then the next smaller element will be possibly found in N/4 elements to the left or the right and so on ... i.e., if we simulate from N to 3 then we can have something like the above ? P.S. Note that it's my guess .

I just wrote a bruteforce to ensure that I'm correct. You can check the code below.

SpoilerI think you just didn't understand the "contribution to the sum" idea. We don't care if they are independent or not, we are calculating the sum of contribution that the $$$i$$$-th index added to the answer among all permutations.

If we put n = 5 here in your code then i am getting around 0.6667 . How can the formula (n-2)/3 which is around 1 here is equivalent ?

I was running it on Custom Tests and I got 1.000.

yeah right it's 1.000 . But still it's unreal that how can then my submission passes in the Problem Link:https://codeforces.com/contest/1156/problem/E Solution Link :https://codeforces.com/submissions/Harshlyn94

`for (int j = i - 1 ; j >= 0 && a[j] < cur; j--)`

`for (int j = i + 1 ; j < n && a[j] < cur ; j++)`

This actually runs in $$$O(n \log n)$$$ on random permutations. (It is equal to the sum of subtree-size of the cartesian tree of the permutation)

So the test cases might be weak in the sense no test case have number equal to the expected number of such triplets . Do you not think what you told above is not holding close in here ? Moreover I have been unaware of the Cartesian tree of permutation . I have to read that as well .

I also didn't think that you understand my span of the i'th biggest index idea in my rough guess i.e, the span of the biggest number is N and the span of the next bigger number is around N/2 and the next N/4 and so on ... And it is sure that they will be maximum in their span .