DL летописец
Наконец то мои руки дошли до первого поста и до первого контеста, завтра утром уже можно будет решать) Я постарался добавить интересных задач, одну даже сам придумал и подготовил)) Разбор будет завтра около полуночи.
Разбор контеста принял ислам. По двум причинам:
1) особо никто не решает
2) 5/6 задач можно нагуглить
Так что к инд туру я только сделаю контест с задачами прошлого года.
Если будет настроение, разберу интересные применения префиксных/суффиксных структур (не суффмасс, а префиксные суммы и подобные штуки)
1) особо никто не решает
2) 5/6 задач можно нагуглить
Так что к инд туру я только сделаю контест с задачами прошлого года.
Если будет настроение, разберу интересные применения префиксных/суффиксных структур (не суффмасс, а префиксные суммы и подобные штуки)
Forwarded from Календарь олимпиад по информатике
Добавлена последняя задача Е в МОШ 10-11. Больше задачи добавляться не будут. Тур длится до 28 февраля включительно.
DL летописец
Разбор контеста принял ислам. По двум причинам: 1) особо никто не решает 2) 5/6 задач можно нагуглить Так что к инд туру я только сделаю контест с задачами прошлого года. Если будет настроение, разберу интересные применения префиксных/суффиксных структур…
Я сделал контест по задачам предыдущего года. Но пока там только 3 задачи вместо 5:
1) последняя - гроб, который тогда даже призеры всероса не сдали на норм балл
2) для 4й довольно сложно сделать норм генератор тестов + инд тур уже завтра
Но пока можно хотя бы попробовать свои силы в трех задачах)
1) последняя - гроб, который тогда даже призеры всероса не сдали на норм балл
2) для 4й довольно сложно сделать норм генератор тестов + инд тур уже завтра
Но пока можно хотя бы попробовать свои силы в трех задачах)
Завтра сразу после туров постараюсь сразу выложить разбор задач (хотя бы некоторых)
👍2
Сегодня писал инд тур олимпиады ИИ НТИ. Матешу я слил (её разбор напишет наш математик). А пока расскажу про инфу.
Всего набрал 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: Если что то непонятно, можете спрашивать (только не ругайте за говнокод пж)
Всего набрал 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: Если что то непонятно, можете спрашивать (только не ругайте за говнокод пж)
Шок!!!
На время открытки я буду жить в одной комнате с Всеволодом Нагибиным!!!
На время открытки я буду жить в одной комнате с Всеволодом Нагибиным!!!
Анонс: завтра/послезавтра (когда выложат результаты) будет пост о том, как я слил ИИ НТИ
Сегодня впервые в жизни поиграл в приставку (какую - хз) в игровой в 1С. Мне понравилось
Еле-еле успел на поезд обратно)))
Яндекс показывал по метро 29 минут ехать, а получилось почти 40, но в итоге добежал за полминуты до отбытия)
Яндекс показывал по метро 29 минут ехать, а получилось почти 40, но в итоге добежал за полминуты до отбытия)
DL летописец
Еле-еле успел на поезд обратно))) Яндекс показывал по метро 29 минут ехать, а получилось почти 40, но в итоге добежал за полминуты до отбытия)
Прибыл на вокзал за 2 минуты до отбытия, бежал наугад (по указателям), решил следовать в сторону 3-4 путей. Мне повезло, мой поезд отходил с 4го пути и я выбежал на платформу прямо к своему вагону))