!!!

гениальный раунд от владимира новикова, все пишем ребята https://codeforces.com/blog/entry/99776

Важно (если пишите СПбГУ по инфе)!

Для тех, кто пишет СПбГУ, хотелось бы напомнить, что по регламенту вы должны пойти тестирование на сайте https://talant.spbu.ru до 10 утра 12 февраля. Логин и пароль нужно использовать с отборочного (такой же, какой вы использовали при входе в тестирующую систему)

Уже через 2 недели будет инд тур по НТИ ИИ (расписание https://ntcontest.ru/participants/schedule/#final-stage-schools), А я как бы хотел выкладывать всякие полезные посты по олпроге. Так как часто хотелось бы видеть посты (на 90% скопированные откуда-нибудь) и контесты на соответствующие темы?

Всем, кто пишет СПбГУ, удачи !

Сегодня я слил СПбГУ по инфе
100+100+100+60+58+0 = 418 / 600
Первые 3 часа жестко тупил, сдал только Ашку и Eшку на 58 (там вообще халявно)
Потом вроде собрался, заметил, что в D надо посчитать просто (n+1)! по простому модулю, написал за линию (оказывается можно было пользоваться справочниками, если они скачаны заранее, но я этого не знал, а так бы скачал себе peltorator book и emaxx, нашел бы код для факториала за sqrt(n) и сдал бы)
Далее стал думать на конструктивом в С. Долго думал, всякую лажу писал. В итоге зашло такое:
если нулей больше чем единиц - заменяем все на ?
если единиц больше (или равно нулям) - первые n/2 единиц заменяем на ?
Далее стал смотреть 3-х страничное условие Bшки.
Тоже долго тупил, но в конечном итоге сдал. Достаточно было заметить, что если идти с конца, то после любого переворота все часы будут в нулевом состоянии - тогда просто переворачиваем, если i+1 раз часы просигналили
Еще пытался в Ешке что то вроде корневой придумать, но так и не придумал.
Жалко конечно что слил (побед спбгу мог бы дать мне бви на ПИ ВШЭ, не ПМИ конечно, но тоже неплохо, но с такими баллами шансов на победителя нет)

Я кстати возможно не буду писать всесиб 🤡, так как в моем регионе нет площадок (ехать далеко до ближайшей) + там сразу после этого финал НТО ИИ, а мне нужно получше подготовиться.

UPD: я кстати обновил свой календарик (закреп) - добавил ИОИП, добавил даты открытки

Наконец то мои руки дошли до первого поста и до первого контеста, завтра утром уже можно будет решать)
Я постарался добавить интересных задач, одну даже сам придумал и подготовил))
Разбор будет завтра около полуночи.

Анонс: далее будет пост про структуры данных, а именно базовое ДО и префсуммы. Потом еще будет немного про графы и, наконец, 1-2 прошлогодних инд тура.

Давно постов не было...


Короче сегодня поговорим о теории вероятности, а также об одном популярном виде задач на теорию вероятности(и геометрию, хехехе)

Сразу замечу, что существует два вида событий(в данном контексте - исходов) относительно друг друга - зависимые и независимые. Зависимые перемножаем, независимые складываем. Выпадение определенного числа на кубике - независимое от других чисел событие, и сумма всех независимых событий равна единице. При броске двух кубиков выпадение одинаковых чисел - совокупность шести независимых событий: на обоих числах выпали одинаковые числа. Каждое такое событие состоит из двух зависимых событий: на первом кубике выпало X и на втором кубике выпало X. Тогда вероятность того, что выпадет две единицы равна (1/6)*(1/6)=1/36, вероятности выпадения двух двоек, троек и т.д., так же равна 1/36 для каждого числа. Тогда вероятность события "выпали одинаковые числа" равна 6*(1/36)=1/6 (Ага, это происходит довольно часто!)

Для начала такая задача: на планете Плюк среди жителей принята цветовая дифференциация штанов, и на один из пиров были приглашены N Плюкчан: двое в желтых штанах и N-2 в фиолетовых штанах. Какова вероятность того, что носители желтых штанов будут сидеть рядом за круглым столом?

Решение:
Посадим одного носителя желтых штанов за стол, теперь осталось __N-1__ позиция, на которую можно усадить второго носителя. Заметим, что существует ровно две позиции, соседних с позицией первого, вероятность того, что он окажется с одной из сторон - 1/(N-1), а поскольку позиций две - вероятность того, что они будут соседями равна 2 x (1/(N-1))=2/(N-1)

Задача два: в модном вузе MGIMO на кафедре политологии, в новой, модной уменьшенной аудитории, находиться ровно один вытянутый стол, за которым сидят N студентов, среди N студентов всегда найдется двое студентов с голубыми волосами, и студентам (как всегда) слишком лень слушать лекцию, и один из студентов решил посчитать вероятность того, что двое голубоволосых студентов сядут рядом. К несчастью он гуманитарий, и у него ничего не вышло. Помогите студенту найти эту вероятность.

Решение:
Заметим, что если убрать из выбора для первого студента два крайних места, то будут работать рассуждения прошлой задачи, поместив на любое из этих N-2 мест первого студента, второй может занять любое из N-1 оставшихся места, среди них только два подходят ему, соответственно вероятность того, что он будет соседом равна 2/(N-1).
Но, так как мы выбрали определенные места для первого студента, эта вероятность правильна только лишь если первый занял эти места, а вероятность такого события составляет (N-2)/N, соответственно вероятность соседства равна {(N-2)/N} x {2/(N-1)}

Рассчитаем вероятность соседства для случаев когда первый занял крайнее место, вероятноcть этого составляет 2/N. Теперь второму можно сесть только с одной стороны, а значит вероятность равна 1/(N-1). Поскольку это последовательные события - перемножим вероятности, получим (2/N) * {1/(N-1)}

Теперь найдем суммарную вероятность наших двух независимых событий: [{(N-2)/N} x {2/(N-1)}] + [(2/N) * {1/(N-1)}]=... (читатели сами могут сократить данное выражение и получить красивую формулу)

И наконец рассмотрим задачу с геометрией: В тире на стене закреплен квадратный лист со стороной 2 метра, в середине которого нарисована окружность радиусом 1 метр, Вася играет с другом в игру, они один раз стрелают в середину мишени, Васе для победы нужно, что бы пуля попала в круг, а Пете для победы нужно попадание в квадрат, но не в круг. К несчастью пистолет - игрушечный, и место попадания пули СОВЕРШЕННО не зависит от навыков стрелка и цели, которую он определил, однако она всегда попадает в лист. Помогите Васе и Пете найти вероятность выграть в этой игре.

Решение

Заметим, что с нашим случайным пистолетом - вероятность попадания пули внутрь курга равна отношению ВСЕХ возможных точек внутри окружности ко ВСЕМ точкам листа. К счастью, совокупность всех точек можно определить как площадь фигуры (внезапно оказалось, что если взять мельчайшую точку, то их поместиться количество, прямо пропорциональное площади).

Тогда вероятность попасть в круг равна S(круга)/S(листа)=(1м^2 x 3.14159...)/(2м^2)=pi/4
Вероятность же попасть в лист, согласно условию, равна единице, пуля всегда попадает в него. Тогда вероятность победы Васи равна pi/4, а вероятность победы Пети равна 1-pi/4.
Это число можно найти двумя путями, можно заметить, что площадь всего квадрата равна 4, а площадь круга pi, тогда площадь квадрата без круга равна 4-pi, а площадь всего листа 4, соотвественно вероятность равна (4-pi)/4 = 1-(pi/4).
Другой путь - понять, что выигрыш Пети - есть проигрыш Васи и наоборот, соотвественно суммарная вероятность победы Васи и победы Пети равна единице. Теперь просто вычитаем из 1 вероятность победы Васи (pi/4) и получаем вероятность победы Пети 1-(pi/4)

P.S. Существует метод приближенного поиска площади какой-либо фигуры, для которой мы можем для случайной точки (например по расстоянию от центра) определить, попала ли она в искомую фигуру, или нет. Через определенное количество итераций мы можем определить площадь искомой фигуры как отношение попавших точек ко всем использованным, умноженное на площадь фигуры, в которую мы поместили искомую и "бросали" в нее точки. (Метод Монте-Карло)

На МОШе появилась новая задача!

Разбор контеста принял ислам. По двум причинам:
1) особо никто не решает
2) 5/6 задач можно нагуглить
Так что к инд туру я только сделаю контест с задачами прошлого года.

Если будет настроение, разберу интересные применения префиксных/суффиксных структур (не суффмасс, а префиксные суммы и подобные штуки)

Добавлена последняя задача Е в МОШ 10-11. Больше задачи добавляться не будут. Тур длится до 28 февраля включительно.

Я сделал контест по задачам предыдущего года. Но пока там только 3 задачи вместо 5:
1) последняя - гроб, который тогда даже призеры всероса не сдали на норм балл
2) для 4й довольно сложно сделать норм генератор тестов + инд тур уже завтра
Но пока можно хотя бы попробовать свои силы в трех задачах)

Завтра сразу после туров постараюсь сразу выложить разбор задач (хотя бы некоторых)

Сегодня писал инд тур олимпиады ИИ НТИ. Матешу я слил (её разбор напишет наш математик). А пока расскажу про инфу.
Всего набрал 10+15+20+25+0 баллов (из 10+15+20+25+30)
Теперь по задачам:
1) Простая задачка - для каждого человека храним время прихода и максимизируем ответ
2) Была дана перестановка n и граф на n вершинах. Надо было найти кол-во подотрезков, в которых ни 1 вершина не соединена с другой. Решалось просто: для каждого значения в перестановке ищем самую позднюю по порядку вершину (но которая раньше её), с которой она соединена. Теперь жадник с указателем на правую границу - пока left[r] < i мы делаем r++;
3) Надо было найти вероятность что при добавлении ребра в дерево образуется цикл четной длины (но нельзя добавлять кратное ребро).
Сначала я решил написать квадрат - тл, ожидаемо. Стал думать и считать пути каждой четности для каждого поддерева. Затем для каждой вершины легко определить сколько через неё проходит путей нечетной длины (а именно такие нам и нужны для цикла четной длины). 1) кол-во нечетных путей в данную вершину (то есть пути из этой вершины) + пути ЧЕРЕЗ эту вершину. То есть после обработки очередного ребенка мы к ответу прибавляем ch[v] * (ch[u] + 1) + nch[v] * nch[u]. Таким образом мы подсчитаем все пути
4) Я пихал что то вроде перс ДО 🤡. Сначала сортил массив в обратном порядке, затем запускал жадник.
пункт 1: мы можем взять вершину этого цвета если её цвет еще не брали
пункт 2: мы можем взять вершину этого цвета и этого веса, если есть другие цвета с этим весом
пункт 3: мы можем взять эту вершину, если существует вершина другого цвета, вес которой меньше минимального имеющего веса текущего цвета.
Первые 2 случая легко заифать. 3й сложнее. Для этого будем динамически строить ДО на цветах. Для этого заранее заведем массив уже взятых вершин. Теперь с помощью бинпоиск ищем левый и правый индекс интересных нам шаров (которые подходят по весу)
Далее на этом отрезке смотрим есть ли цвет не равный текущему: то есть либо 2+ цвета либо 1 не равный цвет. Отсюда кстати небольшая оптимизация: при добавлении новой вершины если в ДО на этом отрезке уже 2 или более цветов - то можно не добавлять

5) Не сдал

Прикладываю коды

UPD: Если что то непонятно, можете спрашивать (только не ругайте за говнокод пж)