Harshlyn94's blog

By Harshlyn94, history, 5 weeks ago,

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 !

• +9

 » 5 weeks ago, # |   0 You can use the "Contribution to the sum" technique (Have a look into this post)
•  » » 5 weeks ago, # ^ |   0 It's not clear how can i apply this technique to solve the above problem . Can you explain how ?
•  » » » 5 weeks ago, # ^ |   +12 If I'm correct, for each $1 •  » » » » 5 weeks ago, # ^ | -10 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 . •  » » » » » 5 weeks ago, # ^ | +5 I just wrote a bruteforce to ensure that I'm correct. You can check the code below. Spoiler#include double ans = 0; int n,p[100]; int main() { scanf("%d",&n); for (int i = 1; i <= n; ++ i) p[i] = i; do { for (int i = 2; i < n; ++ i) if (p[i] > p[i-1] && p[i] > p[i+1]) ans ++; } while(std::next_permutation(p+1,p+n+1)); for(int i=1;i<=n;++i) ans /= (double)i; printf("%.4f",ans); return 0; } I 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. •  » » » » » » 5 weeks ago, # ^ | -10 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 ? •  » » » » » » » 5 weeks ago, # ^ | 0 I was running it on Custom Tests and I got 1.000. •  » » » » » » » » 5 weeks ago, # ^ | 0 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 •  » » » » » » » » » 5 weeks ago, # ^ | ← Rev. 2 → 0 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)
•  » » » » » » » » » 5 weeks ago, # ^ | ← Rev. 2 →   0 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 .
•  » » » » » » 5 weeks ago, # ^ |   0 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 .