Сегодня написал финал ВП 2020 года
https://codeforces.com/group/6Saz5idq0O/contest/314675
Набрал 20+20+20+1+13=74 балла (призер от 63, побед от 90)
Задачи оказались гораздо интереснее и сложнее
А) простой жадник: если сумма нечетная - выводим все плюсы
иначе ищем первое нечетное число и после него ставим умножение
B) жадник на указателях: сначала сортируем массив, затем жадно собираем для каждого случая сначала максимум элементов, потом минимум
C) довольно интересное дп. Сначала посортил значения и придумал за O(n^3) - dp[i][j] - ответ, где i - текущая позиция, j - откуда пришли (переход - dp[i][j] = max(dp[j][k]+1 для k от 0 до j-1, при условии, что a[j] - a[k] > a[i] - a[j]), написал - получил баллы, понял что идея рабочая (10/20 баллов). Заметим, что это означает, что длина каждого нового прыжка строго меньше предыдущего, а так как высоты башен уже посорчены, мы можем найти бинпоиском последнее подходящее k и взять максимум на отрезке. Это уже работает за O(n^2 * logn), но набирает 16/20 баллов. Еще можно заметить, что при увеличении j, последнее подходящее k уменьшается, поэтому предподсчитаем эти k за n^2. Далее чуть-чуть попихал и получил 20 баллов
D) не придумал, заслал кукарек и получил 1 балл
E) долго думал, потом решил попробовать идею выделения меньших элементов (если существует k подходящих подотрезков, то существует k "центральных" элементов (которые как раз медианы), следовательно ответ это длина отрезка минус удвоенное кол-во элементов, меньших m). Получил 13 баллов, очень удивился. Стал писать merge sort tree, но не успел отдебагать и поэтому только 13 баллов.

Впринципе неплохо, но мог и лучше написать

Сегодня написал финал вп за 2021 год
20+20+20+0+9=69 = призер 3й степени
В общем слил. А в добавок в этому еще и приболел (пока 37.8 температура).
Ну и конечно же половину тура у меня голова болела так, что я тупо смотрел в экран и не мог думать.
Еще полчаса читал условие Ешки, пытался понять что вообще происходит в задаче.
А) простая математика (я писал бинпоиск)
B) простая математика (перебор до корня)
C) довольно сложное (для меня) дп по подотрезкам, долго думал и писал
D) придумал вроде рабочее дп по поддеревьям, но так и не отдебагал (квадрат по сложности)
Е) как выше писал - полчаса тупил не мог понять что вообще происходит, далее придумал решение за O(nm), написал, получил 9 баллов. Как оптимизировать не придумал, но судя по подтаскам, либо дд, либо корневая.

Что могу сказать по задачам финалов ВП. Поначалу (до 2019 включительно) это были относительно простые, но идейные задачи на разные темы. А вот финал за 2020 и 2021 год - это простая математика + динамика + до/корневая. Будет забавно, если на финале 2022 выдадут также первые 2 таски на математику, потом 1 на динамику, потом 1 но что-нибудь и еще одну на до/корневую.

Всем, кто пишет, завтра удачи на высшей пробе по информатике!

Сегодня слил закл ВП. Очень обидно, так как не успел заслать D (скорее всего на фулл). Ну и не придумал простую идею в Eшке на +17.
В целом задачи вроде норм, но слабоваты тесты.
A) математика
B) бинпоиск + 2 указателя
C) перебор (у меня фактически квадрат, но работает за 0.59)
D) сначала заслал лажу за O(n^2*logn), получил 36, потом пытался сортить строки и от порядка искать ближайших, но wa получал (как оказалось некоторые такое на 100 сдали, так что у меня руки кривые). Далее пытался сортить по префиксу и суффиксы и от них искать ближайших, но чуть чуть не успел отладить. Возможно потерял на этом 64 балла
E) гроб. На 22 - квадрат, на 39 - счетчик элементов в мапе

Жалко конечно, но призера кажется возьму. А это хотя бы бви в питерскую вышку (по словам знакомых норм место, но поизучаю получше, но в крайнем случае можно будет проще перевестить в мск вышку, чем из другого вуза)

Интересный факт:
1) финал спбгу по информатике будет 13 февраля в 10:00-15:00
2) 2-й отбор на иоип будет 13 февраля в 14:00-19:00
Я попробую поучаствовать в обоих (да, закончу спбгу на час раньше)

!!!

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

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