Большое спасибо!

Вам за участие

Привет, Codeforces!

Рады пригласить вас на Codeforces Round 816 (Div. 2), который пройдет в 20.08.2022 17:35 (Московское время). Раунд будет рейтинговым только для второго дивизиона. У вас будет 2 часа на решение 6 задач. Советуем прочитать все задачи.

Раунд полностью подготовлен и составлен учениками ЛКШ Зима (зимняя смена Летней Компьютерной Школы). В течение смены мы придумали для вас интересные и креативные задачи. Вы можете ознакомиться с предыдущими раундами, подготовленными учениками ЛКШ: Codeforces Round 815 (Div. 2), Codeforces Round #694, Codeforces Round #612, Codeforces Round #530

Огромное спасибо

• авторам и разработчикам задач: Васильев daubi Алексей, Денис Kapt Мустафин, Иван __silaedr__ Подворный, Илья ilyakrasnovv Краснов, Евгений pakhomovee Пахомов, Михаил MadProgrammer Зайцев.

• замечательным преподавателям, благодаря которым состоится этот раунд: Павел PavelKunyavskiy Кунявский, Дмитрий cdkrot Саютин, Алеся AlesyaIvanova Иванова, Константин kokokostya Махнев

• Monogon за прекрасную координацию, полезные советы и терпение

• KAN за помощь при разработке задач

• Qwerty1232 за помощь при составлении разбора

• тестерам, за хорошие предложения и важный фидбэк: glebustim, kclee2172, AndreyPavlov, generic_placeholder_name, nor, TheScrasse, qualdoom, AlperenT, FairyWinx, vdv09, NToneE, KseniaShk, prost_sasha, agrayush13, kartikeyasri23, SomethingNew, в особенности mejiamejia

• MikeMirzayanov и geranazavr555 за отличные системы Codeforces и Polygon!

Разбалловка будет опубликована перед началом.

Ждем вас на нашем раунде, а также в ЛКШ!

Удачи, высокого рейтинга и удовольствия от решения задач!

UPD — Разбалловка:

$$$500 - 1000 - 1750 - 2250 - 2750 - 3000$$$

В контесте могут быть интерактивные задачи! Обязательно прочитайте этот пост.

UPD 2 — Доступен разбор!

UPD 3 — Громкие овации победителям!

Официальные участники:

1. william556
2. fursuit
3. huge_waxberry
4. lbwhangbeateveryone
5. Longiseta

Все участники:

1. jiangly
2. kotatsugame
3. hitonanode
4. ksun48
5. Rubikun

Привет, Сodeforces!

Мы очень благодарны Вам за участие в нашем раунде.

Спасибо Qwerty1232 за помощь при написании разбора.

1715A - Хмурогруз

• Решение на С++: 169161824
• Решение на Python: 169161508
• Решение на Kotlin: 169161674

1715B - Красивый массив

• Решение на С++: 169162178
• Решение на Python: 169161968

1715C - Моноблок

• Решение на С++: 169162300

1715D - 2+ стула

• Решение на С++: 169162393

1715E - Долгий путь домой

• Решение на С++: 169162508

1715F - Квадраты на полях

• Решение на С++: 169162576

Привет, codeforces!

Мы приносим свои глубочайшие извинения за слабые претесты в задаче 1642C - Великая последовательность. Но мы надеемся, что вы нашли в этом контесте хотя бы одну задачу, которая вам по душе :)

Спасибо Mangooste за задачу 1641E - Особые позиции!

Решение: 147513897

Видео-разбор на английском от ak2006

Решение: 147513934

Видео-разбор на английском от ak2006

Решение: 147513962

Решение на vector-ах: 147513974

Решение за $$$\mathcal{O}(2n^2)$$$ вставок: 147514019

Решение за $$$\mathcal{O}(n^2)$$$ вставок: 147514028

Решение: 147514055

Решение с set-ом: 147514064

Solution: 147514090

Решение с bitset-ом: 147514108

Решение: 147514167

Solution: 147662463

Привет, Codeforces!

Рады пригласить вас на Codeforces Round 773 (Div. 1) и Codeforces Round 773 (Div. 2), которые пройдут в 23.02.2022 13:10 (Московское время). Обратите внимание на нестандартное время начала! Раунд будет рейтинговым для обоих дивизионов. У вас будет 2 часа на решение 6 задач. Советуем прочитать все задачи.

Задачи основаны на олимпиаде RocketOlymp, и были придуманы и подготовлены __silaedr__, daubi, alegsandyr, ilyakrasnovv и isaf27.

Большое спасибо

• isaf27 за великолепную координацию, ценные советы и терпение

• Renatyss, stepanov.aa, talant, Siberian, kirill.kligunov, arbuzick за помощь при обсуждении и разработке задач

• AlperenT, ArtNext, EvgeniyPonasenkov, FedShat, Qwerty1232, TeaTime, TheEvilBird, ak2006, generic_placeholder_name, philmol, silvvasil, tox1c_kid за качественное тестирование и полезные предложения

• pakhomovee за задачу, которая не вошла в финальный проблемсет

• KAN за его вклад и этот раунд

• MikeMirzayanov за отличные системы Codeforces и Polygon

Участникам олимпиады категорически запрещается участвовать в раундах на Codeforces параллельно.

Удачи, высокого рейтинга и удовольствия от решения задач!

UPD — Разбалловка:

div2: $$$500 - 750 - 1250 - 2000 - 2000 - 2500$$$

div1: $$$500 - 1250 - 1250 - 1750 - 2250 - 3000$$$

UPD — Разбор

Приглашаем учеников 5-9 классов любого уровня на олимпиаду RocketOlymp!

23 февраля пройдет олимпиада RocketOlymp совместно с основанными на ней Codeforces Round #773 (Div. 1) и Codeforces Round #773 (Div. 2). Олимпиада будет проводиться в четыре лиги: 5-6 класс, 7 класс, 8 класс и 9 класс. Начало туров олимпиады запланировано на 23 февраля, 10:30 МСК. Длительность составляет 3, 4, 5 часов для 5-6, 7-8 и 9-ых классов соответственно. Участникам олимпиады категорически запрещается участвовать в раундах на Codeforces параллельно.

Всем участникам будет предложено по 5 задач, каждая из которых оценивается в 100 баллов, но во время тура часть баллов может быть не видна: они будут начислены только после окончания олимпиады.

Участвуя в олимпиаде вы имеете шанс выиграть фирменный мерч RocketClass или занятие.

Основная часть задач была придумана и разработана __silaedr__, daubi, ilyakrasnovv под координацией isaf27. Полный список авторов, разработчиков и тестеров будет опубликован в анонсе раундов.

UPD:

Поздравляем победителей и призеров олимпиады!

Победители за 9 класс:

1. Салыгин salyg1n Егор
2. Бугрышев vdv09 Михаил

Победители за 7-8 классы:

1. Абдуллин bashkort Гимран
2. Семенюк Kihihihi Ярослав

Победители за 5-6 классы:

1. Егоров Дмитрий
2. Евгений Кузнецов

Полные результаты

Дорешивание тура за 9 класс

Мы в telegram

Зарегистрироваться (неактивно)

Частный случай — 1-2-BFS

Постановка задачи: дан взвешенный ориентированный граф, где для любого ребра вес лежит в диапазоне $$$[1;2)$$$. Найти кратчайший путь от заданной вершины (st) до всех вершин.

Решение: заведем для каждого целого числа от $$$0$$$ до $$$2n - 1$$$ очередь вершин (Пусть $$$i$$$-ая очередь это $$$q_i$$$). В $$$i$$$-ой очереди будут лежать все вершины, расстояние до которых $$$\lfloor i \rfloor$$$ (и возможно какие-то вершины с меньшим расстоянием). Чтобы такие насчитать, будем пересчитывать по слоям.

код на c++:

for (int i = 0; i < 2 * n; ++i) {
    for (int v : q[i]) {
        for (pair<int, double> e : g[v]) {
            if (dist[e.first] > dist[v] + e.second) { // dist -- расстояния до вершин от стартовой
                dist[e.first] = dist[v] + e.second;
                q[floor(dist[e.first])].push_back(e.first);
            }
        }
    }
}

Доказательство корректности алгоритма:

База: $$$q_0$$$ и $$$q_1$$$ построены правильно.

Предположение: Для $$$x \ge 1$$$ слои $$$q_0, q_1, ..., q_x$$$ построены правильно, и расстояния до вершин в них посчитаны правильно.

Переход: тогда слой $$$q_{x + 1}$$$ тоже построен правильно, и расстояния до вершин в нем правильные:

Посмотрим на любую вершину v, для которой $$$\lfloor dist_v \rfloor = x + 1$$$. Она точно не могла лежать в предыдущих слоях по предположению, а в слое $$$x + 1$$$ она лежит, так как предыдущая в пути от стартовой до нее точно лежала в слое $$$x - 1$$$ или $$$x$$$. А так как расстояния до всех возможных предыдущих посчитаны правильно, то и до новой вершины среди одной из релаксаций будет посчитано правильное расстояние.

Асимптотика: $$$\mathcal{O}(n + m)$$$, где n — число вершин, а m — число ребер.

Комментарий: очевидно, что как и в случае 1-k bfs тут можно обойтись и 3 слоями, но приведенный выше способ лучше для понимания.

Сведение к A-2A-BFS

Отличие этой задачи в том, что в отличие от предыдущей веса ребер находятся в диапазоне $$$[A; 2A)$$$, где $$$A > 0$$$. Свести к предыдущей очень просто — надо всего лишь поделить все веса на A. Важным замечанием является то, что при вычислениях может возникнуть погрешность, и лучше избегать нецелых чисел, если возможно. То есть если задана предельная точность, то стоит домножить A и все веса на обратное число, а вершины добавлять в очередь с номером dist[v] / A.

Ниже реализация на c++ для случая, где все веса целые.

for (int i = 0; i < 2 * n; ++i) {
    for (int v : q[i]) {
        for (pair<int, int> e : g[v]) {
            if (dist[e.first] > dist[v] + e.second) {
                dist[e.first] = dist[v] + e.second;
                q[dist[e.first] / A].push_back(e.first);
            }
        }
    }
}

Приглашаем учеников 4-8 классов на первую олимпиаду, сделанную школьниками при поддержке мат-инфо классов "Силаэдр". (9 и старше классы могут поучаствовать в неофициальном зачете). Все задачи были подготовлены школьниками.

Будет предоставлено 5 задач и 4 часа на их решение. Задачи будут с частичными баллами и оффлайн-подгруппами (Подобно МОШ 6-9). Олимпиада проводится в двух вариантах: для 4-6 класcов и для 7-8 классов.

По этой ссылке регистрация и вся сопутствующая информация: http://shosh.silaeder.ru

Олимпиада начнется 14.02 в 10:00. Результаты будут доступны в течение дня. По окончании олимпиады вы увидите разборы в формате видео и текста.

Авторы и тестеры олимпиады:

Подворный __silaedr__ Иван, школа Силаэдр, 9 класс

Сильвестров silvvasil Василий, школа Силаэдр, 9 класс

Краснов ilyakrasnovv Илья, Пятьдесят Седьмая школа, 8 класс

Пискарев Qwerty1232 Иван, школа 2086, 8 класс

Хромов ArtNext Артем, школа 1533 ЛИТ, 11 класс

Шатохин FedShat Федор, МОАУ "ФМЛ" города Оренбург, 8 класс

Пустовалов talant Юрий, СУНЦ МГУ, 11 класс

Клигунов kirill.kligunov Кирилл, школа 179, 9 класс