Сергей, спасибо. Ваши статьи я тоже читал.
Кстати, если будете в Моккве и будет желание — заходите к нам в Яндекс, расскажите что-нибудь про свой опыт.
Можете также посмотреть видео о школе: shad.yandex.ru/video/
Скоро опубликуют и второй фильм, он про один из главных курсов школы — алгоритмы и структуры данных поиска — который читает Максим Бабенко.
Справа сверху рядом с кнопками Thumbnail View и List View есть стрелка с выпадающем меню, в котором есть функция Restore all removed thumbnails (да, только сразу все восстановить)
Я обычно отключаю один из них в зависимости от текущего языка, чтобы память не отжирали. Но вроде они и одновременно нормально уживаются. Но одноврременно они и не нужны особо — для C# VA бесполезен при наличии R#. Разве что если в одном solution проекты на разных языках.
А нет информации, когда поддержка extensions будет включена по умолчанию? Dev-версию я-то использую, но вот прописывать во всех ярлыках enable-extensions не хочется, ведь всё равно если кликнуть на ссылку в другом месте, чтобы открылось новое окно хрома, это окно откроется без нужного параметра, правда ведь?
К слову, про редакционное расстояние (оно же растояние Левенштейна). Оно же в основном используется, например, для поиска опечаток, и расчитывается, что это расстояние небольшое. Поэтому можем немного переформулировать задачу — посчитать расстояние, если оно небольшое (не больше k), иначе выдать соответстующий ответ, что расстояние слишком большое (т.е. строки слишком разные). Ясно, что если длины строк отличются больше, чем на k, то и расстояние будет больше k. Отсюда усовершенствование алгоритма — считать можно не все клекти в таблице m*n, а только k-окресность главной диагонали (в остальных клетках значение будет точно больше k). Для этого понадобится O(k*n) времени и столько же памяти (n=max(m,n)), что при разумном условии k << n даёт выигрыш.
Для начала, вероятность выжить всем не 0.6767581376913977, а 1 — 0.6767581376913977 < 0.5. Дело в том, что если считать смерти узников независимыми событиями, то общая вероятность получилась бы 2-30. А такая стратегия делает эти события сильно зависимыми, отчего и получается такой результат.
Итак решение.
(первым алгоритм предложил Sandrique, ближе всего к правильной оценке подобрался 0leGG, но всё-таки не доказал, что алгоритм работает правильно)
Алгоритм такой: каждый узник открывает коробку со своим же номером, смотрит какой ключ там и открывает коробку с номером этого ключа, достаёт новый ключ и открывает коробку с номером нового ключа, и так далее. Если ему в какой-то момент надо будет открыть коробку, которую он уже открывал, это значит, что он уже обошёл весь цикл, и значит (т.к. начинал со своего номера), нашёл и свой ключ.
Доказательство корректности:
Действительно, как правильно заметил0leGG, кто-то из узников умрёт, только если в перестановке ключей в коробках есть цикл длинее 15. Подсчитаем вероятность этого. Для этого найдём количество (и вероятность) перестановок из n элементов (n=30) с циклом длины k (k>n/2=15). Элементы для цикла можно выбрать Cnk способами, составить из них цикл можно (k-1)! способами, остальные элементы можно переставить (n-k)! способами. Всего перестановок n!.. Значит, вероятность таких перестановок равна
Cnk * (k-1)! * (n-k)! / n! = n! / (k! * (n-k)!) * (k-1)! * (n-k)! / n! = 1/k.
Теперь для подсчёта суммарной вероятности надо просуммировать по k от 16 до 30 и (воспользовавшись калькулятором или ещё чем-нибудь) оценить сумму:
1/16 + 1/17 +… + 1/30 < 0.7
Значит, с вероятность больше 30% никто не умрёт.
Равновероятность разбиения графа на компоненты и равновероятность перестановок — разные вещи. Т.е. в вашей модели нельзя будет просто поделить число каких-то определённых разбиений на число всех разбиений.
Кстати, если будете в Моккве и будет желание — заходите к нам в Яндекс, расскажите что-нибудь про свой опыт.
Вообще, про метрики было бы интересно отдельно почитать.
+ в карму
Круто было бы, если бы Вы ещё смогли собрать такой же набор на mincost…
Скоро опубликуют и второй фильм, он про один из главных курсов школы — алгоритмы и структуры данных поиска — который читает Максим Бабенко.
Для начала, вероятность выжить всем не 0.6767581376913977, а 1 — 0.6767581376913977 < 0.5. Дело в том, что если считать смерти узников независимыми событиями, то общая вероятность получилась бы 2-30. А такая стратегия делает эти события сильно зависимыми, отчего и получается такой результат.
(первым алгоритм предложил Sandrique, ближе всего к правильной оценке подобрался 0leGG, но всё-таки не доказал, что алгоритм работает правильно)
Алгоритм такой: каждый узник открывает коробку со своим же номером, смотрит какой ключ там и открывает коробку с номером этого ключа, достаёт новый ключ и открывает коробку с номером нового ключа, и так далее. Если ему в какой-то момент надо будет открыть коробку, которую он уже открывал, это значит, что он уже обошёл весь цикл, и значит (т.к. начинал со своего номера), нашёл и свой ключ.
Доказательство корректности:
Действительно, как правильно заметил 0leGG, кто-то из узников умрёт, только если в перестановке ключей в коробках есть цикл длинее 15. Подсчитаем вероятность этого. Для этого найдём количество (и вероятность) перестановок из n элементов (n=30) с циклом длины k (k>n/2=15). Элементы для цикла можно выбрать Cnk способами, составить из них цикл можно (k-1)! способами, остальные элементы можно переставить (n-k)! способами. Всего перестановок n!.. Значит, вероятность таких перестановок равна
Cnk * (k-1)! * (n-k)! / n! = n! / (k! * (n-k)!) * (k-1)! * (n-k)! / n! = 1/k.
Теперь для подсчёта суммарной вероятности надо просуммировать по k от 16 до 30 и (воспользовавшись калькулятором или ещё чем-нибудь) оценить сумму:
1/16 + 1/17 +… + 1/30 < 0.7
Значит, с вероятность больше 30% никто не умрёт.
Хотя конечно если исправить, перепутать было бы сложнее.