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 !
→ Обратите внимание
До соревнования
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
05:34:52
Зарегистрироваться »
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
05:34:52
Зарегистрироваться »
*есть доп. регистрация
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 23.11.2024 12:00:08 (j1).
Десктопная версия, переключиться на мобильную.
При поддержке
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.
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.
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.me/contest/1156/problem/E Solution Link :https://codeforces.me/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)