We are given a sequence : [1,2,...N]. Lets consider all the permutations of the above sequence. Now, a good permutation is defined as the one in which there is atleast one pair of numbers such that a[i]+1=a[i+1]. How to count the number of good permutations ? This problem is from some old contest.
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 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 | 165 |
| 2 | maomao90 | 164 |
| 3 | Um_nik | 163 |
| 4 | atcoder_official | 160 |
| 4 | adamant | 160 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 8 | Dominater069 | 154 |
| 8 | nor | 154 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 15.11.2024 16:06:28 (j2).
Десктопная версия, переключиться на мобильную.
При поддержке
can you give the problem link plz
You may try to count sequences that contains $$$12$$$, or $$$23$$$ etc, but you should soon realize that these contain many common sequences and subtracting them is hard. So try finding different approach.
Almost all counting problems that has a "atleast one" in it can be solved by solving the reverse problem and subtracting that from the total number of ways. Here the answer is $$$n!$$$ minus the number of permutations that don't have any $$$p_i +1 = p_{i +1}$$$
The later part can be calculated by a recurrence. Let $$$f_n$$$ be the number of permutation with no $$$[k, k+1]$$$ as sub-string. You can get a valid permutation of $$$n-1$$$ elements and insert $$$n$$$ in any of $$$n - 1$$$ spaces to get a valid permutation of $$$n$$$ elements. Or, you can get a permutation of $$$n-2$$$ elements and insert $$$[n, n-1]$$$ in any of $$$n - 2$$$ spaces to get a valid permutation. So, $$$f_n = (n-1)f_{n-1} + (n-2)f_{n-2}$$$. Final answer is $$$n! - f_n$$$.
I have a doubt : how can we be sure that permutations from (n-1)f_n-1 and (n-2)f_n-2 will not repeat.
example let say we need f_5
Now, one of the possible solution of f_4 be {3, 2, 1, 4}
from this we will have more (n-1) permutations for f_5 , which are:
{3, 2, 1, 5, 4} , {3, 2, 5, 1, 4}, so on..
and let one of the possible solution of f_3 be {3, 2, 1}
than new (n-2) solution for f_5 generated from this would be:
{3, 2, 1, 5, 4}, {3, 2, 5, 4, 1} , so on..
but they are counting the same permutations {3, 2, 1, 5, 4}
Please help if i am wrong.
Yes there will be exactly one overlap for each of the permutation ins $$$f_{n - 2}$$$, that is why I am multiplying with $$$(n-2)$$$ instead of $$$(n-1)$$$, excluding the position where it will overlap.
Try expanding your 'so on..' in the last paragraph. You'll see that there are $$$5-2=3$$$ valid permutations.
Yes, you are right thank you.
But can you please tell, how did you figured out that you will need two terms in recurrence, like why not go with three terms, f(n) = (n-1)f(n-1) + (n-2)f(n-2) + (n-3)f(n-3). I know it sounds funny but i want to know the approach you used
All good permutations belong to a form of the first or the second type.