Привет, Codeforces!
Закончился первый тур олимпиады. Надеюсь, что скоро участники поделятся своими впечатлениями от задач и результами. В этом году впервые Codeforces участвовал в проведении этой олимпиады — 12 регионов принимали участие на нашей платформе. Есть кто из участвующих? Как впечатления? Кажется, всё работало без сбоев. Очередей не было.
Дорешивать задачи можно в Тренировках по ссылке 2018-2019 Всероссийская олимпиада школьников по информатике, региональный этап, 1 тур.
UPD: Закончен второй тур. По ссылке Тренировках можно дорешивать и задачи 2-го тура: 2018-2019 Всероссийская олимпиада школьников по информатике, региональный этап, 2 тур.
ИМХО слишком большой скачок в сложности между B (которая была, на взгляд многих, ненамного сложнее / проще А) и C. Опять же, мой первый регион, поэтому не могу компетентно сравнить с заданиями прошлых лет (т.к. не сидел и не думал над ними так же долго и внимательно)
Не знаю, как у других, но на яндекс.контесте вердикт в среднем минут 10-15 надо было ждать. Кстати, общий монитор когда можно будет глянуть?
Стоит отметить, что Яндекс работал гораздо лучше, чем в прошлом году
Никто просто решить ничего не мог
На codeforces все было нормально.
А какие регионы участвовали на Codeforces? И по какому принципу можно было попасть в их число?
Организаторы в регионах заполняли форму с предподчтениями.
Как написали? (у меня 254)
(246) кто знает как в целом регионы написали?
Ссылочка
с проглотом ... не разгибаясь
254
ТАКОЙ КРУТОЙ!!!! БОЖЕ, ХОЧУ ОТ ТЕБЯ ДЕТЕЙ
У меня 60 балов и одни разочарования, когда можно будет посмотреть код к задачам?
я вообще о**ел от жизни после того как не смог решить эту легкотню... 94..
А как на КФ была организована сдача частичных решений?
Полагаю, как тут, например. Да и в посте ссылка на дорешивание
codeforces работал отлично) Спасибо Майку. Теперь не надо было ждать вердикт по часу как раньше. Но вот сам контест ...
Контест, как бы это сказать не из приятных. Что за бред творился в двух последних задачах. Такой чуство, что Гайнулина попросили придумать рандомное задачу, которую никто бы не решил. Так же мне не понятно, где изичные группы в Д, хотя бы баллов на 5, перебор, что бы можно было написать, но нет вместо этого придумывайте динамику. Most werseted contest in my life!
перебор в 4ой группе на 8 баллов
D на 8 баллов примерно перебор, самая тупая двумерная динамика;
С на 31 балл за O(NM) или O(NM logN) придумывались легко, первые две группы ифаешь и получаешь 46
Спасибо майку мирзоянову за хорошую площадку) Что касается впечатлений о задачах. П — параша. 2 Задачи на математику и 2 на хард хард информатику. Не было ничего норм решаевомого. У меня очень горело. Готовился к бинпоиску, графам, геоме, но пришел и стал есть говно. Хорошо, что хоть на сборы по математике ходил
Готовился к задачам, которые будут связанны с аниме тематикой. Смотрел берсерка, харуху, повторял наруто и читал коносуба. А в результате понял условие задачи D только с 3 прочитывания. Ну что сказать, обосрался пополной. Все еще надеюсь, что на 2 день будут задачи по аниме. Спасибо майку за площадку) все работало отлично. По моему условия проведения улучшаются, а вот качество задач превращаются в битву наруто с пейном.
Ну хз, вторая решалась и бинарником, четвёртая на 28 — комба, и на 38, видимо, тоже. Хотя сначала написал дп на D
УУУФФ У МЕНЯ АГРЕССИЯ И ЗУБЫ СКРИПЯТ
Всё работало прекрасно, без сбоев. Не то, что яндекс контест в прошлом году. Но,... Что это за задачи??? Какого фига 2 математики и 2 гроба? Почему задачи такие ужасные? И откуда вы вообще такую D откопали? Капец, у нас народ набивал около 250 и далее просто застрявал во всём этом дерьмище. Страшно представить, что будет во второй день. Пару задач на многомерную динамику? Всё задачи на графы? Сплошная геометрия? Что ещё придумают авторы региона, чтобы мы не набрали больше 300/800 баллов?
Всероссийская олимпиада по информатике никогда не была похожей на другие соревнования по программированию и особенно сильно не похожа на соревнования по типу Codeforces. Там всегда было много математики и "гробов" — сложных задач/групп тестов, рассчитанных на то, что их решит очень малый процент участников. То, что большинство участников в регионах набирает 250 — более чем нормально, особенно если понимать, что это не олимпиада для веселья и тренировок — это отбор на очень серьёзный заключительный этап с громадным конкурсом на место.
Посмотрел на задачи, вполне себе в духе всеросса. Можешь ныть сколько угодно, с таким настроем успехов в олимпиадах (и по жизни) ты явно не добьёшься.
Про "многомерную динамику" и графы просто смешно. Если тебе задачи кажутся сложными только потому, что в ней участвует динамика, то всеросс — не твой уровень, и ты вполне справедливо пролетаешь. Советую не плакаться об этом, а учиться решать такие задачи.
qqqq
Они немного завысили слодность тура, но в целом все 4 были решаемые. Это доказывается тем, что Лифарь за час и 8 минут закрылся на 400. Я совсем не согласен, что 3 не пишется на 100, ты более или менее просто придумываешь жадник за квадрат , ну а дальше придумать как его за nlogn писатьне трудно. Если Вы идете на региональный этап и не умеете писать ни ДО ни Фенвика, а это все что было нужно, ну это Ваши проблемы. Это одна из тем, которые дают на С/Д региона, это нормально. Если бы Вы решали туры подготовки к региону от организаторов, открытые всем без исключений, Вы бы это знали
"Если бы Вы решали туры подготовки к региону от организаторов, открытые всем без исключений" — это ты о чем?
Не найдется ссылочки на эти туры ?
Думаю, имеются в виду московские сборы к региону. https://olympiads.ru/moscow/2018-19/vsosh/region_training.shtml Но они уже закончились, дорешки кажется нет.
А ты почти угадал — задача на 2д дп есть, две задачи на графы есть
А нету сводной таблицы участников из всех регионов?
Ну или отдельных по регионам?
+
Посмотри Вк в группе "Сортируй", там есть опросник по баллам + табличка регион — класс — баллы — впечатления. Остается понадеяться на добросовестность и оперативность участников РЭ.
Ну технокубок тоже всеросс, да?)))
F
Скорее открытка
Может кто поделиться решением С на 100?
Заметим, что когда мы убираем пропуск, то нам логично убрать его так, чтоьы все пропуска до него были ло него, заменим номера пропусков на номера их в порядке их дальнейшего доставания, теперь за логарифм нужно класть пропуск в место, после которого нет элементов больше него, это можно сделать неявным декартовым деревом
Учитывая, что авторское решение работает примерно в 2 раза быстрее моего, советую пройти мимо) А еще я в целом очень плохо объясняю задачи(9((( Тем не менее, я ее сдал на 100 прямо на туре, так что, если интересно, вот:
Давай заведем очередь, в нее запихаем данную перестановку. Заведем сет — в нем мы будем хранить пары (время, номер пропуска) чисел, дойдя до которых мы не будем должны их скипать (то есть во втором массиве будет индекс++). Изначально сет пуст. Под временем я подразумеваю ближайший справа индекс во втором массиве, на котором мы используем пропуск. Также за "текущее время" будем считать текущий индекс во втором массиве. Еще для каждого "текущего времени" посчитаем nxt[i] — следущее время, для элемента, который нужно поставить в момент i.
Собственно, теперь к самому решению. На каждой итерации мы берем либо первый элемент из очереди, либо из сета. Заметим, что к очереди мы обращаемся только когда сет пустой, либо когда время первого пропуска в сете не равно текущему времени (потому как после того, как мы по разу использовали все билеты, то их не потребуется больше скипать).
Если мы достали элемент из очереди, тогда могут быть такие случаи:
1) Пропуск скипать не надо. Тогда в сет кладем (nxt[t], number),где t и numb — это время и номер текущего пропуска.
2) Пропуск надо скипнуть. Тогда в сет кладем (t, number).
Если мы достали пару из сета, то тогда выполняем первый пункт для очереди, ведь билеты из сета мы не скипаем)
Осталось восстановить ответ. Для этого нам надо уметь делать 2 вещи: для каждого пропуска в момент, когда мы его используем, знать, какое количество пропусков из очереди мы обработали между его предыдущим использованием и текущим моментом (это, пожалуй, самая сложная часть решения с точки зрения понимания), а также знать количество пропусков в сете с меньшим временем. Сначала первый пункт. Пусть мы используем пропуск. На данный момент мы уже вытащили из очереди k1 элементов. Когда будет доставать этот пропуск в следущий раз — мы обработаем уже t2 элементов. Тогда к ТЕКУЩЕМУ вхождению билета в ответ надо добавить t2 — t1. С точки зрения реализации это делается очень просто: для каждого билета запоминаем его последнее вхождение ответ, и когда достаем билет в очередной раз, то обновляем предыдущее вхождение.
Почему это работает? Если перед пропуском мы обработали какие-то элементы из очереди, то в стопке из условия нам было бы выгодно положить пропуск после этих элементов, чтобы не делать лишних скипов.
Ну а с сетом вообще просто — заводим Дерево Фенвика на значениях, в которой единица в элементе означает, что такое время в сете есть. Тогда количество билетов в сете с меньшим временем — просто сумма на префиксе)
Обнаружил интересную багу — если открывать задачи по одному с главной страницы или со страницы монитора, то они все будут иметь номер 'A'.
Ну и зачем минусовать это? Это реально баг и так не должно было быть.
Ну, что, как вам Б. Ели запихнул ее на 100. Еще один "прекрасный" контест в копилку
Задача обычная, только в последней группе тестов не знаешь вердикт. Это конечно мусор, час дебагал тупой RE.
Да хватит блин плакать. Готовиться надо лучше. С сегодняшнего контеста три задачи реально были обычные, сдаваемые. Я понимаю бомбит пердак, но надо взять себя в руки и следующий год еще больше, лучше и серьезнее тренироваться.
Что не так? На плюсах нормально всё зашло без упихона.
там вердик не выдает, но насколько я понимаю там было RE из за того что много памяти занял, просто вместо 2х массивов на dp у меня было 4.Если бы на последних тестах был виден результат было бы норм, а так не понятно, толи Ml Tl WA RE лол
Лучше бы дали геому...
Геома мало кому нравится, и на свежих регионах ее почти нет
Так мне геома тоже не нравится)
Я на самом деле был бы не прочь порешать геому (с моим вкладом можно такое писать)
Думал хуже чем первый день ничего не будет... Авторы постарались :D
.
.
уже выложили
Скидывайте в эту ветку результаты регионов Питер — https://neerc.ifmo.ru/school/spb/regional-2019/standings-regional-2019-spb.html Татарстан — https://pcms.university.innopolis.ru/standingsHHAYSYTJJSHDJHSYYGGDYSG236273/
Лен. Область: https://neerc.ifmo.ru/school/spb/regional-2019/standings-regional-2019-lo.html
Крым — http://ejudge.cfuv.ru
https://olimpiada.ru/reg_results
Иркутск
Владивосток, Камчатка, Хабаровск — тур 1, тур 2
Красноярский край
Челябинск: https://ipc.susu.ru/40280-3.html
Пензенская область: http://irrpo.pnzreg.ru/konkursy/meropriyatiya/olimpiady/itogi-vsosh-/2018-2019/%D0%98%D0%BD%D1%84%D0%BE%D1%80%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B0.PDF
Все результаты, собранный в одну табличку.
http://imc.codnn.ru/assets/documents/vosh_region/informatyka_9.pdf
http://imc.codnn.ru/assets/documents/vosh_region/informatyka_10.pdf
http://imc.codnn.ru/assets/documents/vosh_region/informatyka_11.pdf
Нижегородская область
http://vosh.tilda.ws — Башкортостан
http://olymp.beluno.ru/images/olymp2019/Itog%20prot%20inf%202019.pdf — Белгород
http://www.viro33.ru/a%20href=«index.php?option=com_content&view=article&id=1761»%3E — Владимир
http://welcome.vstu.ru/Прием%202019/Строкатова/Информатика%202019%20итог.pdf — Волгоградская
http://олимпиада.образованиеврн.рф/wp-content/uploads/18/itog_reg/Информатика%20и%20ИКТ/Результаты%20РЭ%20ВсОШ%20по%20информатике%20и%20ИКТ.pdf — Воронежская
http://evrika41.ru/olimpic/olimpresult/254-201819-god.html — Камчатка
http://cdoosh-k.ru/index.php/meropriyatiya/vserossijskaya-olimpiada-shkolnikov/regionalnyj-etap/215-2018-2019-uchebnyj-god/887-regionalnyj-etap-informatika-i-ikt — Кострома
http://olimpiada48.ru — Липецк
http://imc.codnn.ru/vserossijskaya-olimpiada-shkolnikov/#regionStage — Нижегородская
http://irrpo.pnzreg.ru/konkursy/meropriyatiya/olimpiady/itogi-vsosh-/2018-2019/Информатика.PDF — Пензенская
http://genius.pskovedu.ru/?project_id=10381&pagenum=32634 — Псковская
https://vsosh.rtyva.ru/index.php/home/2-uncategorised/94-rezultaty-regionalnogo-etapa-2019 — Тыва
https://cpod.ippk.ru/vserossiiskaja-olimpiada-shkolnikov/regionalnyi-yetap/protokoly-zasedanii-zhyuri-regionalnogo-yetapa-vsosh-2018-19.html — Хабаровский
http://olymp.iro86.ru/index.php/home/2018-01-22-04-25-52/304-2019-01-17-12-07-22 — Ханты-Мансийск
Калининградская область: https://olymp.baltinform.ru/p.documents_v5.php?subjects_id=5&years_id=2019
Московская область — https://mosregolymp.mipt.ru/etc/final-results.pdf
Москва — https://www.olympiads.ru/moscow/
.
тут есть решения всех https://neerc.ifmo.ru/school/archive/2018-2019.html#region
Не лучшее решение, скажу сразу, но 100 заходит У нас будет динамика dp[i][j][2] — количество способов набрать суммарно i очков на тренировки при том что в последний день нагрузка будет j, 0 — означает, что до этого дня у нас было больше j , а 1 меньше. Теперь база динамики dp[k][k][0] = 1 dp[k][k][1] = 1 важный момент тут по сути 1 вариант считается 2 раза, и что бы он нам не испортил ответ напишем костыли if(n == k) ответ 1 Теперь, переходы. if(c>j) dp[i][j][0] += dp[i-j][c][1], if(c<j) dp[i][j][1] += dp[i-j][c][0] , c — сколько прибавили на i-j тут мы смотрим сколько существует способов набрать сумму i-j и для этого перебираем все варианты того как могли предти в i-j, вот эта сумма и есть ответ для i j так как мы к этой сумме прибавим j Теперь как считаем перебираем i суммы , внутри него j как мы туда пришли и с для подсчета dp Теперь где ответ, это сумма на всех значений на i. Но это работает за n^3.Поэтому попытаемся улучшить алгоритм , во первых заметим что мы считаем последовательные суммы на i-j что бы это несколько раз не пересчитывать пишем префиксные суммы База для префиксов pr[k][k...n][0] = 1 pr[k][k...n][1] = 1 Переходы dp[i][j][0] = pr[i-j][n][1] — pr[i-j][j][1], dp[i][j][1] = pr[i-j][j-1][0],
pr[i][j][1] = dp[i][j][1] + pr[i][j-1][1] pr[i][j][0] = dp[i][j][0] + pr[i][j-1][0] ВСЕ работает за n^2 но памяти 4*n^2, давайте улучшим память. Заметим что теперь при переходах мы не обращаемся к старым dp то есть нас интересует значения dp только с i, хорошо тогда просто будем поддерживать dp[j][2] dp[j][0] = pr[i-j][n][1] — pr[i-j][j][1], dp[j][1] = pr[i-j][j-1][0],
pr[i][j][1] = dp[j][1] + pr[i][j-1][1] pr[i][j][0] = dp[j][0] + pr[i][j-1][0] база и обход теже ответ ans = pr[n][n][0] + pr[n][n][1], И НЕ ЗАБУДЬТЕ ВСЕ ОПЕРАЦИИ ПРОИЗВОДИТЬ ПО МОДОЛЮ 1е9+7 иначе переполнится, все это заходит на 100 на с++, совет сделать массив pr глобальным, у меня из за этого RE ,было на макс тестах сначала) Удачи в решении
пока писал уже разбор выложили, кек
Такое же решение, но зашло за 4*n^2 памяти, long long не нужен.
I hope wery0 has 400 points on the second round. I am really worried about his coming on the final
.
254+246=500, if you really worried about my result.
Oh, you are so cool. I think its enough. I think you will go to ioi
Кто сколько смог набрать на втором? 264
400 :?
Что за машина. Ты как к региону готовился, какие аниме смотрел?
RWBY. Только тсс, не пали
Как думаете со скольки проход для 10 класса?
Ну, резов Москвы не видел (хотя хотелось бы), но, кажется, примерно 500, так как в этом году посложнее регион был.
Результаты регионов, которые писали на Codeforces:
Некоторые участники писали первый тур из Сириуса, а второй — из своего региона. Такое пока не обработано, чуть позже правильно объединю результаты.
Все результаты, собранные в одну табличку.
Кому интересно пованговать проходные и т.п. — полные таблицы регионов прошлых лет- 2017-2018, 2016-2017
Посчитал статистику по языкам программирования в разных регионах. Собрал данные из 73 регионов.
Проходные баллы на заключительный этап: 445 — 481 — 505 https://olimpiada.ru/news/14998
Задача С первого дня, такая же как и тут https://acm.timus.ru/problem.aspx?space=1&num=2080