Привет всем!!! Сегодня состоится командная олимпиада на сайте Neerc. Всем удачи!!! будем надеяться, что разбор напишет кто-нибудь.
→ Обратите внимание
До соревнования
Rayan Programming Contest 2024 - Selection (Codeforces Round 989, Div. 1 + Div. 2)
07:01:15
Зарегистрироваться »
Rayan Programming Contest 2024 - Selection (Codeforces Round 989, Div. 1 + Div. 2)
07:01:15
Зарегистрироваться »
*есть доп. регистрация
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3993 |
| 2 | jiangly | 3743 |
| 3 | orzdevinwang | 3707 |
| 4 | Radewoosh | 3627 |
| 5 | jqdai0815 | 3620 |
| 6 | Benq | 3564 |
| 7 | Kevin114514 | 3443 |
| 8 | ksun48 | 3434 |
| 9 | Rewinding | 3397 |
| 10 | Um_nik | 3396 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | atcoder_official | 162 |
| 3 | maomao90 | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 155 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 10 | djm03178 | 152 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 30.11.2024 10:33:45 (h1).
Десктопная версия, переключиться на мобильную.
При поддержке
можешь назвать пост как-нибудь поконкретнее, а то neerc 2012-2013 понятие растяжимое
можете сказать где находятся задачи?
http://neerc.ifmo.ru/school/io/problems.html
вот здесь
У кого нибудь есть условие?
как решать G ?
Подвешиваем дерево за какую-нибудь вершину и обходом в глубину для каждой вершины считаем вес поддерева с корнем в этой вершине. Обнаруживаем, что для каждой вершины знаем длины очередей: очереди со стороны потомков равны весам поддеревьев, соответствующим потомкам, а очередь со стороны предка равна весу дерева минус вес поддерева с корнем в рассматриваемой точке. Проходим по всем вершинам и получаем ответ.
P.s. в контесте не участвовал, решение не сдавал, так что могу ошибаться.
Как решать D?
мы искали поток в сети, где в первом слое — дни, во втором — типы таблеток. в каждый день ведет единичное ребро из истока, и из каждого дня исходят два единичных ребра в соответствующие типы таблеток. из j-того типа таблеток выходит ребро в сток с пропускной способностью cj. утверждается, что если решение есть, ответ — насыщенные ребра между долями.
Там проходил просто Кун. Первая доля — дни, вторая — типы таблеток, размноженные в соответствии с тем, сколько раз этот тип таблеток использовался. Ребра понятно какие. Ну и вначале стоило проверить, что количество использованных таблеток совпадает с количеством дней.
гм. казалось бы, ребер тогда может получиться квадрат от числа вершин. O(VE) не должен был проходить, или я чего-то не осознал?
да нет, по идее это тоже проходит, ведь если хоть раз и первой доли не нашлась удлиняющая цепь — можно брякнуться
В некоторых задачах были неточные условия. Например в задаче G не было понятно что делать с людьми, живущими на той площади, на которой будет построена больница. Также в последней задаче не было сказано в какую сторону делается циклический сдвиг: вправо или влево. Мне кажется, что мое решение не прошло из-за того, что я думал что используется сдвиг налево, а они подразумевали направо.
А какая разница, в какую сторону сдвиг? Там же рассматриваются все сдвиги.
Надо было смотреть Messenger. Там были уточнения по задачам A и G.
А как решалась J?
Найдём в строке наибольшую amax и наименьшую amin букву. Тогда сложность слова = max(amax-s[0],s[0]-amin) + max(amax-s[n-1],s[n-1]-amin). При циклическом сдвиге крайними буквами становятся все пары соседних. Переберём все такие пары в качестве s[0] и s[n-1] и посчитаем среди них минимум — ответ.
P.s. в контесте не участвовал, решение не сдавал, так что могу ошибаться.
нет. надо еще найти, минимальный циклический сдвиг, который будет равен строке — смотрите семпл из примера
Действительно. А как это сделать? Разложить длину строки на простые и просто проверить?
период строки = n — p[n], если n % (n — p[n]) == 0
и n если n % (n — p[n]) != 0, где p[n] — префикс-функиция для n-го элемента
Кто-нибудь сможет залить в тренировки, когда выложат тесты?
можно скачать и протестировать самому, если вы конечно хотите дорешать (а не решать впервые)
да, дорешать. но так же удобнее.
Как решалась H?
Есть мнение, что динамика за квадрат. Будем поддерживать массив dp[N] — наименьшее число пересадок, за которое можно успеть в данный город, av[N] — массив, отмечающий достижимость города до отправки конвоя. Так же будем хранить числа a и t — наименьшее число пересадок и наименьшее время, когда мы можем добраться до спасительного города. Для каждого города i выполняем следующие действия: если город недостижим до отправки конвоя, то пропускаем его. Если же достижим, то обновляем (если надо) a,t, отмечаем все города, в которые мы можем успеть, как достижимые и обновляем в них наименьшее число пересадок как dp[j] = min(dp[j],dp[i]+1). В итоге в a и t получаем ответ.
P.s. в контесте не участвовал, решение не сдавал, так что могу ошибаться.
Тесты выложили, залить в тренировки было бы очень кстати.
можно тесты скачать и протестить, ага
было бы клево, если бы все-таки залили на кодфорсес.
В тренировках — 2012-2013 Цикл интернет-олимпиад. Первая командная олимпиада (22 сентября 2012). Базовый уровень.
Большое спасибо.
может все-таки 3 звезды?
Скорее да, исправил.
кому-нибудь известно, Анастасия Лешина aka Anastasiy — это реальный человек (кто-нибудь из здесь пристуствующих знает ее) или это чей-то фэйк?
Реальный человек. Она раньше математикой занималась довольно серьезно.