Всем привет! Сегодня в Тюмени завершился всерос по информатике. Я выступал в роли координатора подготовки всероса в прошлом и в этом году. Коллективу жюри было бы интересно выслушать мнения участников и причастных о комплекте задач. Часть отзывов до нас уже дошла из разрозненных источников, но давайте попробуем собрать все в одном месте.
UPD1: Выложил олимпиаду в тренировки. Первый тур, второй тур.
Очень приятно писать конструктивы, особенно в задачах формата IOI, где баллы вместо распределения по подгруппам принимают вид чуть ли не x/100 (где x — от 20 до 40, в зависимости от задачи). Единственная таска, которая искренне понравилась — C1. Из-за захожящих в B2 лаж я не призёр.Спасибо огромное всем причастных, не знаю, когда в прошлый раз я бы получал такой негативный опыт от олимпиады.
Хотелось ещё сказать следующее: ни в одной задаче особо не было идейный подгрупп (по крайней мере для людей, прошедших на закл). Т.е. была невероятная кучность баллов, и место во многом определялось исключительно баллами по B1/B2, которые конструктивы. Для олимпиады, которая для многих даёт право без мороки поступить, сводить её к придумыванию идей в двух задачах — странно (и очень мерзко ощущается).
Хотелось бы в следующем году побольше конструктивов, и бшки усложнить
A1, A2 в целом норм задачи. B1 B2 конструктивы. Один из самых противных типов задач. B2 не сдал, не взял победителя. C1 в целом нормальная задача,но большой скачок сложности после n^3/n^2* log C2 достойная задача D1 тоже большой скачок сложности после 23 баллов. D2 интерактивная задача, жаль было мало времени еепорешать после B2
Ну и в B2 у кого то лажа зашла
Кажется, что консенсус в том, что А1 и А2 простые, Б1 и Б2 на "заметим, что". А дальше набираются частичные баллы разного уровня идейности.
Получается, на сильного призера не нужны ни ХЛД, ни переливайка, ни ДО, ни ordered set
Выглядит, как очень простой Всерос, если решать задачи именно так
Б1, кажется, нормально придумывается, учитывая подгруппы-подсказки, а в Б2 заходят много разных идей разного уровня сложности, хотя бы до одной можно додуматься на туре, следовательно, Бшки несложные
Обе задачи А были очень скучные, как по мне.
Обе Бшки показались очень интересными, я бы сказал лучшими за последние много много лет.
С1 показалось не очень много групной, пускай результаты и говорят обратное, но для меня в этой задаче были 67 баллов либо 100 баллов, остальные группы не понятно как решать.
С2 задачка как задачка
D1 ну понятно что задача оказалось плохой.
D2 в целом найс, но там на группы мало идеи для Д как по мне и много кода.
Конструктивы фигня
Приехал вроде на всеросс по информатике, а решаю задачи по математике... Я могу согласиться с тем, что задачи А должны быть 5-минутками, которые решаются с прочтения, но что творилось в задачах В в этом году это просто ужас imo. Задачи буквально одноразовые, какими и конечно же должны быть конструктивы. Но на всероссе по информатике?... Зачем существуют разные кружки, разные лекции, если в результате весь путь сводится к: придумай идею в 5 строк кода в математической задачке в оба дня. Без спорно, есть подгруппы которые набираются знаниями каких-то алгоритмов (C12 D2). Мое мнение можно расценить как недовольного, потому что я не стал призером, а какие-то люди стали решив АВ в оба дня, да сдав переборы за 2^n стали, поэтому я не доволен, но каждый сам расценит как хочет. Надеюсь, что в будущем задачи на всероссах будут такими же классными как на открытой олимпиаде, где помимо идей надо было применять опыт олимпиадного программиста, а не олимпиадника по математике.
Зато теперь можно говорить, что для призерства всеросса по информатике надо знать как писать код и DFS.
B1 и B2 самые лучшие задачи, обожаю задачи на заметим что просто ван лав спасибо большое за такие прекрасные задачи <3
Также считаю, что конструктивные задачи на всеросе что-то странное. В предыдущих годах их не было в таком виде, к чему многие участники были не готовы. Очень грустно, что алгоритмическая часть спортивного программирования совсем ушла из всероса, и осталась только математика и идея. Совсем отпадает идея кружков Тинькофф и разных лагерей. Еще мне показалось не очень понятным, что многие задачи составляли студенты первого-второго курса университета, часть из которых по профилю математики. Вроде у них не очень много опыта в этом деле и ощущения каким должен быть всерос. Тут мало уметь хорошо решать задачи, нужно еще понимать, как их будут решать участники и будут ли они им интересны для решения.
Теперь мое субъективное мнение по каждой задаче (это может показаться смешным и абсурдным, что будет написано ниже. но я даже не стал призером, поэтому прошу не реагировать резко мое мнение про задачи этого года): A1, A2 — хорошие не сложные задачи B1 — идея и задача прикольная, но было очень неприятно увидеть идейную интерактиву с двойным запуском в позиции B, хотя задача решается и идея не очень сложная (а для C — слишком легкая была бы...) C1 — ну это уже больше похоже на стандартную задачу всероса D1 — кринж полный, непонятно, зачем была вообще сделана и для кого. какая-то матеша и у всех 23 балла B2 — какой-то конструктив :( С2 — прикольно, но не для программистов вещь, математика.. D2 — какое-то жуткое условие, но задача весьма подходящая.
Отвечу пока на первую половину сообщения, про составление задач. Чтобы внести некоторую ясность, расскажу примерную схему, как происходит подготовка задач на всерос (и на другие олимпиады тоже). Сначала координатором проводится так называемый call for problems. Он пишет разным людям в поиске идей задач. Затем, опуская подробности, членами жюри (последние года – скорее координатором) выбирается набор задач, которые мы бы потенциально хотели видеть на олимпиаде. Затем координатор ищет разработчиков для этих задач. Это обычно, но не всегда, как раз студенты первых курсов, потому что у них пока достаточно свободного времени. После подготовки, проводятся прорешки, возможно появляются какие-то улучшения по задачам. И уже очно на всеросе члены жюри окончательно определяются с комплектами задач на два тура. То есть, студенты первых курсов могут поучаствовать в двух местах: в предложении задач и в их подготовке. Но ответственность за выбор задач на туры, за набор подзадач в задачах лежит скорее на координаторе и других членах жюри.
Можешь уточнить, кто из молодых авторов ВсОШ по твоему мнению не имеет большого опыта в олимпиадном программировании и не знает, каким должен быть ВсОШ? Ну и откуда информация, что они учатся по профилю математика?
Во-первых, прошу прощения, если я своим комментарием упрекнул авторов-составителей. (потому что писал на эмоциях после тура).
Но в своем комментарии я явно написал (может, конечно, это не читается), что молодые авторы сильные программисты и умеют хорошо решать задачи, то есть у них есть большой опыт в олимпиадам программировании. Про "каким должен быть ВСоШ", я, действительно, не могу ничего высказывать, но я хотел только отметить, что задачи поменялись с новым коллективом авторов. (и стали ближе к codeforces формату)
Ну по поводу математиков я, действительно, перепутал авторов.
Человек даже не фиол на кф и не призёр всероса:
Составители не знают, что такое всерос и какие принято давать на него задачи.
Я понимаю, что так писать некорректно. И, возможно, я криво написал, потому что я не придавал много значения своему комментарию. Просто хотел отметить (мне хотя бы так показалось), что задачи, составленные этим коллективом авторов, сильно отличаются по сравнению с теми, что были в прошлые года. В этом нет ничего плохого, что-то новое. Ну просто я не был к этому готов. (и не только я. но я понимаю, что это моя проблема).
Просто всерос стал ближе к codeforces раундам по типу задач. Возможно, потому что авторы тренировались на именно на них, когда были школьниками.
Коллектив не менялся, просто координатор выбрал такие задачи ввиду своих вкусов/общего наличия задач, так что бесконечно сомнительное утверждение в любом случае)
Напомню, что половина задач прошлого года от Тихона, а в этом году он официально в жюри)
Ну давай я скажу, что я тоже считаю, что всерос -- не то, что было в этом году, и задачи тоже далеко от формата всероса :)
фан факт чтобы знать(или представлять взглянув на прошлые года) какие задачи нужно давать на всерос не обязательно быть фиолом или призером всероса, че за бред откуда вообще фиол взялся это что-то крутое или что, как минимум есть составители задач на всерос не фиолы и не призеры всероса
Ну вот после комментариев авторов и гроссмейстеров мне стали дизлайкать посты... Прошу, считать мой отзыв чисто личным мнением и не воспринимать его серьезно.
Ашки решаются с прочтения, как и должны, вроде
B1 — "Заметим что". Я не заметил
B2 — там тесты супер слабые, заходят жадные решения(с жадным выкидыванием отрезков, а они не должны), заходят на большой балл решения с +- случайным выкидыванием отрезков и шафлом, пока не получится правильный результат. Сама задача красивая, идейная, к сожалению, с помощью подгрупп эту идею не подсказать(как это было в B1), поэтому идея должна была сама полностью сформироваться, может, поэтому многие считают, что это "заметим что", и объединяют её с B1
C1 — норм задача, подгруппы хорошие
С2 — работа с дп, самая интересная из всех задач
D1 — не решается больше чем на 23 балла
D2 — не вникал в условие
Когда будет дорешка?
Завтра выложим задачи в тренировки на кф
конструктивные идейные задачи А и Б очень хорошее решение, не понятно почему к этому пришли только сейчас. Я считаю что идейные А и Б и более алгоритмические С и Д создают какой-то баланс в турах, это понравилось. По задачам С и Д могу сказать лишь то что они сложноватые, из-за чего балл на победителя такой низкий.
P.S. спасибо платформе codeforces что подготовила меня к конструктивам и я взял победа<3
Хоть я и участвовал в первый раз, задачи мне показались довольно интересные. A решались почти сразу после прочтения, но вот B, в которых, как писали выше "заметим, что", из-за чего решение этих задач сводится не к знанием каких-то алгоритмов, а "повезёт/не повезёт" заметить идею для решения (я, хоть и старался, но не смог). И, как итог, стать призёром можно было, если заметить идеи в B1 и B2 и решить A обоих дней (что, как показывала таблица результатов, было довольно легко). C1 показалась довольно интересной и вполне решаемая, в то время как C2 имхо была много труднее, по сравнению с C1. D1 мне показалась достойной (хотя я даже и близко к решению скорее всего не подошёл), но как по мне, именно такой и должна быть самая трудная задача в туре. К сожалению много времени уделить D2 не удалось, но я думаю она была не хуже D1.
Я 3 раза перечитал D2 и так и не смог написать тупняк. А1 не особо понравилась, А2 прикольная, B1, B2 классные задачи и мне кажется такие должны быть и дальше, в C1, D1 почти нереально было набрать чтото кроме 43 23, C2 классная и можно разные баллы набрать
А в чем именно трудности в D2?
Ведь подгруппы $$$l_i = r_i$$$, $$$c = 0$$$ и перебора требуют только реализации поиска максимального по весу независимого множества. В $$$c = 0$$$ можно вообще даже весь интерактивный формат пропустить.
Возможно я не умею читать, но прочитав задачу на туре, и сейчас, я все еще не могу понять почему при c = 0, решения которые только определяют возможность допустимой эффективности проходят все тесты, выводя, например всегда k = 0, ведь возможно существует план с такой эффективностью но никогда не будет достигаться такое k. Просто в задаче явно не написано что если план не будет проверен то можно выводить любое число, а написано выводить именно k, что по условию должно являться функцией, которая принимает не любые значения
Сколько условия не пиши, всё равно кто-то не поймёт...
На первом этапе вам будут даны значения v1, v2, . . . , vq. Для каждого из них вам необходимо выяснить, существует ли план с эффективностью vi и, если его не существует, вывести для этого запроса −1, а если существует, то неотрицательное целое число ki.
Заметим, что здесь не говорится, что выведенные числа должны быть равны сертификатам. Вас просто просят вывести какие-то числа ki (неотрицательные, если план существует). Нет нигде требования, что выведенные значения ki должны быть равны сертификату какого-то плана.
На втором этапе некоторые планы будут проверены: c раз вам будет дано целое число i (1 ⩽ i ⩽ q). В ответ на такой запрос требуется либо вывести −1, если плана с эффективностью vi не существует, либо предоставить план [a1, a2, . . . , an], сертификат которого равен ki , а эффективность равна vi.
Если вас попросили вывести план, то вы должны вывести такой план, сертификат которого совпадает с ранее выведенным числом.
Поэтому в тех подзадачах, в которых c > 0, необходимо еще на первом этапе подготовиться к проверке, выведя для значений эффективности vi, где искомый план существует, такие значения ki, для которых вы сможете на втором этапе предъявить план с сертификатом, равным ki.
Специально ещё раз оговаривается, что проверка соответствия сертификата плану нужна, только если вас попросили предъявить такой план.
А в чем тогда смысл названия вектора ответов и функцию вычисления ответа одинаковой буквы k если они не связаны?
Процитируйте, пожалуйста, фрагменты условия, которые вы имеете в виду.
Я вообще ничего не понял когда прочитал ее, но думаю проблема скорее во мне, учитывая что ее многие хоть на что-то сдали
где резы можно посмотреть?
https://roi.algocode.ru/
Все уже в курсе, что бшки были чисто идейные. Это нормальная практика, когда для решения задачи на полный балл нужна какая-либо идея. В конструктивных задачах самих по себе ничего плохого нет. Однако баллов за безыдейные подгруппы было очень мало, основные баллы набирались за подгруппы, где уже надо было придумать основную идею полного решения, и это стало проблемой распределения позиций, что если ты набираешь мало баллов по бшкам, то твои шансы оказаться на нормальном месте летят резко вниз. Разница в баллах у людей, которые догадались до чего-то с теми, кто не догадался огромна. Также нельзя сказать, что идея в B1 была такой, что ты сильный — ты решил, ты не очень сильный — ты не решил. Просто посмотрев на табличку первого дня создаётся впечатление, что участников пошафлили. Никогда не поверю в то, что кучу сильных людей, которые уже возможно не первый год показывают хороший уровень можно разоблачить одной идейной задачей. Другой проблемой стало абслютное отсутствие плавно возрастающей сложности подгрупп в C1 и D1. Не должно быть такого, что у разных весовых категорий участников равные баллы по этим задачам. Всерос этого года произвёл впечатление плохого кф раунда.
Ну относительно своей задачи B1 я не считаю, что баллов за безыдейные подгруппы было "очень мало". Я бы даже сказал, что их было "очень много". А именно, подгруппы 1, 2, 3, 5, 6 я считаю подгруппами, которые не имеют отношения к общему решению, и они дают в сумме 47 баллов. Здесь я специально пропустил подгруппу 4 (не знаю, сдал ли её кто-нибудь отдельным кодом), т.к. она придумывалась для тех, кто не поленится разобрать вручную 35 подмножеств из 7 элементов по 3, давайте считать это малореальным. Т.е. практически половина баллов давалась за отсутствие подхода к общему решению, и этот балл 47 был довольно типичным. Балл 54 тоже попадается, т.е. по-видимому, кто-то всё-таки разобрал и подмножества из 7 по 3.
Подгруппы 5 и 6 (там где дерево если мне не изменяет память) придумываются и пишутся сложнее, чем полное решение
Я про B1, а не B2.
А в задаче B2 подгруппы с деревьями, кстати, как раз могли быть наводящими на мысль полного решения.
Ой, не заметил, что про B1 речь) Там с подгруппами всё отлично. Да, верное решение подгруппы n <= 100 дало бы ключ к полному решению с большой вероятностью, но нужно тут тоже ещё придумать нужно этот правильный жадник(а я писал другой, я проиграл). Ну и по коду там намного сложнее, чем фулл
Подгруппа 4 сдавалась алгоритмом Куна, поэтому мне кажется, что это нормальная подгруппа на перебор.
На недвудольном графе?
Конечно же нет, мы можем сделать двудольный граф.
Сделаем две версии каждого набора: для кодировки и для декодировки. Теперь соединим два набора между собой если:
1) В них равное число элементов
2) Нет общих элементов
3) Один для кодировки, другой для декодировки
Получим двудольный граф с маленьким количеством ребер и вершин, в котором найти паросочетание поможет алгоритм Куна.
У нас результаты в делегации (МШП) очень неожиданные лично для меня, если смотреть выступления на других контестах, тренах и сборах. Но дипломы взяли почти все, так что конструктивы как раз оказались спасительными для некоторых (хоть их многие и не любят, я в том числе), жаловаться не буду)
Кажется, всерос сдвинулся в сторону около-математических идей, плохо ли это? Если хочется сохранять уникальность прогерских задач и их отличие от математических, то да.
Где-то (не помню где) писали, что будет возможность дорешивания этого РОИ в тренировках на CF. Если это уже реализовано, кто-нибудь дайте ссылку, пожалуйста. Я сопровождающий, если что, на турах задачи не писал, но очень интересно попробовать B-шки поконструировать.
Раздел "Тренировки" сверху. Ну и в посте написаны прямые ссылки на контесты.
Спасибо, не заметил.
Задача B1 очень понравилась как идейно так и в реализации. Образцовая задача на двойное тестирование. Спасибо автору идеи.
Мой отзыв о ROI 2023 (предыдущие комментарии не читал, возможно, что там написано примерно тоже самое)
A1 и А2 я не могу объективно судить, они кажутся прикольными, но про них наверно стоит спросить тех, кому они доставили хоть какие-то трудности.
Б1 кажется довольно прикольной, но, возможно, в ней подгруппы вообще никак не помогают при решении на 100.
При прочтении Б2 на туре я очень испугался, что не решу ее (хорошо что все обошлось :D), и подумал, что 100% многие затупят на ней и лишатся призеров / победов.
B1, B2 — хорошие задачки. Как по мне, как раз уровня Бшки всеросса. Может быть это не очень круто, что они обе конструктивы, ведь Бшки это ключевые задачи при определении призеров, но мне они понравились.
С1 — очень классная задача. Наверно сложнее чем Сшки на ROI 2022, но если честно, мне больше нравится когда Сшки сложные, и решают их мало человек, а не 40 штук как это было в прошлом году.
С2 — выглядит тоже очень классной, но, пока ее я не дорешивал, полную оценку сказать не могу.
Сшки очень понравились. Классно выбран их уровень сложности, мне не хочется чтобы Сшки решали все, нравится, когда их решают максимум человек 6-7.
Д1 кажется очень прикольной. Жаль что не хватило времени нормально подумать над ней, но на 100 баллов я уверен, что это классная задача. Печально, что по ней у всех примерно один и тот же балл.
Д2 тоже классная, по ней неплохо так можно было набрать баллов, по уровню она наверно примерно как Дшки всеросса 2021 (я пока не дорешивал 2023ий год, может быть, я ошибаюсь).
Суммарно, мне всеросс очень понравился. Мне повезло, что я не застрял на Бшках, жаль людей, которым повезло чуть меньше.
Всем привет!
Как председатель жюри, напишу свое мнение и ответ на некоторые комментарии. Группа разработчиков во главе с Николаем работала достаточно автономно, но окончательные решения принимались жюри во время проведения олимпиады.
Начну с того, что некоторые типы отзывов вызывают у меня недоумение.
Кажется если вы готовились к олимпиаде и плохо подготовились, странно винить жюри. Возможно способ подготовки был выбран неправильный?
Как мне кажется, никаких знаний или типичных приемов олимпиадной математики для решения задач не требовалось. Успех на олимпиадах по математике и информатике действительно бывает связан, многие успешны и в том и в другом, не вижу в этом ничего удивительного.
По поводу сложных структур данных на олимпиадах по информатике. Вообще, мое мнение, что чем для решения меньше нужно конкретных сложных алгоритмов или структур данных — тем лучше, тем качественнее задача. Другой разговор, что такие задачи — большая редкость, придумать крутую оригинальную задачу, где не нужны структуры данных или алгоритмы тяжело. Приходится расширять диапазон для придумывания задач добавлением в "силлабус" олимпиады алгоритмов и структур.
Зачем же их тогда вообще учить алгоритмы и структуры данных? Расширять диапазон задач, которые вы теоретически можете решить + увидеть разные приемы, идеи, в том числе из доказательства корректности, которые вы сможете затем применить или увидеть аналоги. Но "я знаю кучу алгоритмов и структур данных => я буду побеждать на всеросе", как, впрочем, и "для победы на всеросе по информатике достаточно быть крутым математиком" — оба неверных утверждения, как мне кажется.
К счастью, в системе РСОШ много олимпиад для поступления, включая, кстати, мной очень уважаемую, и часто упоминаемую в обсуждении как положительный пример, Открытую олимпиаду по программированию, которая дает БВИ на все уважаемые программы. Так что рассматривать Всерос как олимпиаду для поступления не так критично.
И кстати не согласен, что фактор везения сыграл больше чем обычно. Он всегда есть, даже если сплошные структуры данных на контесте, кто-то ее только что изучил и решил кучу задач на эту тему, а кто-то еще не проходил или проходил давно и забыл.
Теперь мое мнение по поводу задач.
A1, A2 сделали свое дело. Довольно милые задачи для первой позиции, вроде никаких особых подводных камней или ловушек в них не было и свою задачу дать по 100 баллов на туре призерам и победителям, не отвлекая их от решения более сложных задач, а нижней части таблицы дать возможность проявить себя — например, скоростью решения — они выполнили.
B1. На мой взгляд одна из трех лучших задач олимпиады, вместе с C1 и D2. Красивая идея, причем не согласен, что типа "заметим что". Есть два основных подхода к решению, и оба они напрямую связаны с информатикой и получаются в результате активных попыток решить задачу, а не приходят как откровение. Решение "идем слева направо, выдаем первое незанятое число" похоже на работу хеш-таблиц с открытой адресацией, а решение "идем слева направо, выдаем первую пустую позицию, где баланс равен нулю" — на работу со скобочными последовательностями. Я, кстати, довольно долго придумывал решение этой задачи и получил второе решение постепенным "продавливанием" идеи с "если есть число X, передаем X+1, а если оно тоже есть, думаем, что делать".
C1. Отличная сложная задача, вполне в духе международных олимпиад. Единственный ее недостаток, видимо, что стоило ее поставить на позицию D, а не C, она оказалась сложнее, чем жюри исходно считали.
D1. Задача, про которую я соглашусь, что она оказалась не в том месте не в то время. В такой формулировке в этом месте тура по ней оказалось мало возможностей проявить себя, а достаточно глубоко ее раскопать даже у лидеров не было времени из-за идейной B1 и довольно сложной задачи C1. Может быть ее следовало еще поисследовать в поисках хорошей постановки задачи с такой идеей решения.
B2. Здесь основная претензия, что можно было получить верное решение, не доказав его. Действительно, такого лучше избегать, но сама задача, вроде, достаточно простая. Складывается впечатление, что многие испугались пытаться ее решить, кинувшись собирать баллы в довольно техничных подзадачах этой и следующей задачи, и проиграли тем, кто рискнул потратить время, чтобы ее придумать, или написал недоказанное решение. Гениальной идеи, которая щелкает, и задача становится очевидной — не видно, решение получается последовательной раскруткой от "рассмотрим ответ, оставим m/2 отрезков, как бы нам достроить их до n/2, чтобы ответ не изменился" + пониманием доказательства корректности жадного алгоритма построения совместного множества отрезков.
C2. Нормальная задача с большим числом подазадач на разную степень продвижения, да и полное решение в целом доступно на уровне победителя.
D2. Очень хорошая сложная задача на уровне задач межнара, кстати относительно новый формат с идеей сначала запросить много сертификатов, а потом некоторые из них проверить.
Резюмируя, все задачи в отдельности выглядят вполне ОК.
Но не может же миллион
лемминговучастников олимпиады ошибаться, раз многим не понравилось, значит наверное набор в целом был не очень удачным?Тут можно согласиться частично: из-за избыточно сложных C1 и D1 поднялась роль B1/B2, которые подкосили часть участников, которые не смогли/побоялись или в целом не были готовы, что нужно будет придумывать решение. Жюри, кстати, много работало над совершенствованием второго тура, чтобы расширить диапазон сложности, в котором можно проявить себя участникам разного уровня. Поэтому, как мне кажется, набор задач был очень интересным, но немного не сбалансированным на первом туре.
Кстати, на конструктивной ноте: если вы закончили школу и хотите сделать наборы задач олимпиад лучше — присылайте свои идеи задач, в частности мне можно присылать идеи на ВКОШП, СПбКОШП (она же интернет-отбор ВКОШП) и региональный этап Всероса, если я лично вас знаю — сразу пишите, а если нет, будет хорошо, если кто-нибудь вас порекомендует.
По оценке заданий мне, пожалуй, добавить нечего. Меня ещё удивляют замечания, что "конструктивные" задачи (которые B1 и B2) — "одноразовые", что (как я понял) мнение участников выражается в том, что они не нужны и будут сразу же забыты после тура.
Ну так на самом деле большинство задач, которые встречаются на олимпиадах по информатике, именно такие — "одноразовые", потому что, как правило, никаких фундаментальных идей, которые можно было бы потом применить для решения реальных задач, олимпиадные задачи не несут. "Фундаментальной" задачей может быть, например, "отсортируйте данный массив в порядке возрастания", или "найдите путь в графе кратчайшей длины", но в такой формулировке фундаментальные задачи уже не имеют олимпиадной ценности, т.к. хорошо известны.
И вот как раз задачи B1 и B2 из прошедшего тура и будут помнить. Именно потому, что они "идейные". У них простая формулировка и красивая идея решения. И, кстати, уже после тура оказалось, что как раз задача B1 имеет отношение к тому, что называется Box-Ball System, это связано с динамическими системами и клеточными автоматами, см,, например, https://demonstrations.wolfram.com/PeriodicBoxBallSystem .
Также хочу прокомментировать проблему вида "Зачем мы всё это учили в кружках и летних школах?".
Проблема на самом деле не нова. Ещё в 2006 году в ЛКШ была шутка про "Параллель А, где вам расскажут много ненужных алгоритмов". Это, действительно, так — параллель A — это ненужные для всеросса алгоритмы. Для того, чтобы стать призёром всеросса достаточно знать небольшой набор широко известных тем: сортировка, двоичный поиск, простая (одномерная и двумерная) динамика, обход дерева, перебор комбинаторных объектов, простые алгоритмы на графах. Этого вполне достаточно, чтобы набрать достаточное для призёра количество баллов. И жюри старается подбирать задачи, в соответствии с этим принципом.
Но со стороны школьников есть спрос на подготовку к олимпиадам. Школьники говорят — "мы хотим готовиться к олимпиадам". Весь этот набор тем они знают. Особенно после потери ЛКШ монополии на подготовку к олимпиадам, с этим стало совсем тяжело, когда в летнюю школу приезжает школьник после двух других летних школ и говорит — "а, эти темы я знаю, это я уже проходил, хочу что-то другое".
В результате под видом подготовки к олимпиадам приходится грузить школьников алгоритмами, которые, на самом деле, именно с точки зрения подготовки к олимпиадам не нужны. Ну если только речь не идёт о победителях и межнаре, но уж для уровня призёра всеросса точно не нужны. Между тем школьники хотят готовиться, и думают, что прослушивание лекции о каком-то очередном сложном алгоритме и решение нескольких задач на тему этого алгоритма им помогает в подготовке, и потом хотят, чтобы коли они такие замечательные и потратили время на изучение алгоритмов, то должны быть вознаграждены олимпиадой, на которой они продемонстрируют своё знание изученных алгоритмов. Нет, это не так, и так быть не должно, олимпиадные задачи должны быть оригинальными и идейными, а не сводиться к программированию алгоритмов и структур данных.
UPD: Извиняюсь, написал фигню, осознал спустя некоторое время.
Отсутствие корреляции "открытки" и "всеросса" — это не новость. Победитель открытки может остаться участником всеросса. Участник открытки становился потом победителем всеросса. Это было и в прошлые годы, и не один раз. Просто разные олимпиады, с разными задачами, разными подходами, разными авторами.
.
Вы опять скатываетесь в идею "всеросс нужен для тех, кто ботает", то есть присоединяетесь к числу тех, кто пишет "я тут изучал разные алгоритмы, почему же я не взял всеросс?"
Извините, не хотел это цитировать, но в порядке проведения всероссийской олимпиады школьников написано: "Олимпиада проводится в целях выявления и развития у обучающихся творческих способностей и интереса к научной (научно-исследовательской) деятельности, пропаганды научных знаний, отбора лиц, проявивших выдающиеся способности, в составы сборных команд Российской Федерации для участия в международных олимпиадах по общеобразовательным предметам."
Где тут написано, что олимпиада проводится с целью выявления тех, кто ботает? Впрочем, те, "кто ботает", наверное, подпадают под определение тех, кто проявляет интерес к научной (научно-исследовательской) деятельности, но это не единственный критерий. Кроме того, я подозреваю, что большинством из тех, "кто ботает" олимпиады по информатике, движет не интерес к научной деятельности, а иные мотивы. Вряд ли те, кто ботает из интереса к научной деятельности, стали бы писать подобные комментарии.
Окей, спасибо. Буду решать олимпиадные задачи по математике, чтобы я входил в то число "проявивших выдающиеся способности".
Можно было стать призером придумав всего одну Бшку, даже не на фулл, а потом набрав баллы как раз благодаря алгосам и умению кодить на других задачах. В чем проблема так было сделать людям, которые много ботали?
это опять упирается в то, что решил/не решил, то есть диплом практически зависит от двух задач. Разве это правильно?
А ты считаешь, что должно быть так, чтобы не решив ни одной Бшки ты должен был бы стать призером(это, кстати, возможно, если ты посмотришь на табличку)?
Мне не хватило нескольких баллов до призера, хотя я "даже не на фулл" придумал B1(там больше 70 баллов), но мало в B2(очень). Проблема в том, что диплом тупо зависит от бешек
Я вижу много людей, которые не сдали Бшки, но стали призерами, так что если ты сильный олимпиадник, то можешь набрать нормальное количество баллов даже их не придумав по факту. P.S кажется, почти на всех всеросах от Бшек зависит призер ты или нет
.
Что? Если ты придумал хотя бы одну Бшку и набрал халявные баллы, то призером изи стать даже с запасом
.
С таким же успехом можно сказать что и победа можно было взять набрав балл 100 0 100 100 100 0 100 100 только вот сделать это намного сложнее
Пожалуйста, хватить все время искать ошибки в наборе задач. Это ты виноват, ты не был готов, ты решал неправильные задачи при подготовке. И хватит все время принижать заслуги других, ты же не знаешь как они готовились.
Тебе не кажется, что информатика — это раздел математики? И где ты тут вообще нашел задачи, в которых олимпиадная математика должна помочь? Конструктивы — это абсолютно стандартный тип задач, к которому должны быть готовы все участники.
Хватит ныть с фейковых аккаунтов, начни искать проблемы в себе, а не во всех остальных.
Теперь я тоже созрел, чтобы написать небольшой ответ. Основая цель, на которую я ориентировался, была составить интересную и сбалансированную олимпиаду. Мне кажется, что задачи, которые быстро сводятся к стандандартному алгоритму, который затем остается только написать -- не самые интересные задачи. Да, они вполне имеют право на существование, и в том числе бывают на всеросе. Но в этом году я нашел менее стандартные, и более интересные.
Некоторые проблемы в наборе задач определенно были. Я немного промахнулся со сложностью первого тура: слишком большой скачок по сложности в подзадачах C1 и D1 привел к тому, что большое количество участников самого разного уровня набирали там одинаковые баллы. Однако, эту проблему мы исправили во втором туре -- в C2 и D2 огромное количество подзадач, в которых сложность возрастает действительно плавно. Вторая проблема -- комбинация задач B1 и B2. Из-за того, что в C1 и D1 участники разных уровней набирали одинаковый балл, у сильного участника, который не смог решить B1 или B2, оставалось меньше пространства для
маневраотыгрыша баллов. Жаль, что так получилось.У меня не было цели составить олимпиаду из стандартных задач и отранжировать участников по знанию алгоритмов. Моя цель была составить интересный набор задач, чтобы каждый участник нашел в нем для себя что-то новое, и, как я надеюсь, получил удовольствие от решения. В этом плане, моя цель наверняка расходится с целями большинства участников, которые хотели просто получить диплом призера/победителя, чтобы получить поступление в ВУЗ и/или денежную премию. Что ж, если вы хотите поступить в ВУЗ без экзаменов, есть большое количество разных перечневых олимпиад. Если вы хотите померяться силами в честной и равной борьбе, где заранее известны все темы, а задачи максимально стандартны -- вас ждет замечательное мероприятие под названием ЕГЭ. Ну а если вы приехали на всерос, то готовьтесь к чему-то новому (вероятно).
Очень грустно, что давление и стресс из-за больших ставок на всеросе (бви и другие бонусы) отнимают у людей возможности в полной мере насладиться решением интересных задач(
У меня есть мысль, с чем может быть связано массовое недовольство Bшками. Большинство задач по информатике — это задачи про ускорение. Т.е. есть какой-то достаточно простой способ решения, который по времени не проходит и нужно как-то его улучшить. Например, такими были все оставшиеся шесть задач этого всеросса. Причем не всегда для ускорения хватает просто применить какую-то структуру данных или стандартный прием, зачастую требуется хорошенько задачу поисследовать, в том числе математическими методами, как, например, в задаче C1, которая мне на этом всероссе понравилась больше всех. А вот обе Bшки сюжетно другие, там основная сложность придумать вообще хоть что-нибудь, нет этого отправного медленного, но несложного решения. При этом я не утверждаю, что это плохо или что таких задач не должно быть, просто, возможно, именно эта разница людям и не нравится.
Наконец узнал, как можно описать, почему для меня инфа лучше математики
Точно сказано. Принимаясь за задачу по информатике, участник обычно должен иметь понимание о том, как ее решать ХОТЬ КАК ТО. В общем случае. Это может быть не очень точный алгоритм или не очень быстрый, но представление о том, как решать задачу все равно имеется. А дальше стоит проблема превращения решения тупого в решение умное. А когда в задаче не наблюдается никакого решения кроме полного, получается, что участник как слепой котенок (как, кстати, происходит на математике) вынужден тыкаться в разные решения. И пока решение не будет придумано на полный балл, оно лежит в тысяче других задумок по поводу задачи, каждая из которых имеет место быть. Потому что они все равноправно не решают ровно ничего в задаче. Сложно понять, за какую из бесчисленного кол-ва одинаковых соломок нужно зацепиться. А если зацепиться не за ту — кончится время и баллов не прибавится.
Внесу свои пять копеек спустя продолжительное время
Мне не очень ясно возмущение отсутствием каких-то алгоритмов и структур данных. Во-первых, по опыту двух прошлых лет, для того, чтобы взять призера мне не требовалось ничего сложнее базовых алгоритмов, конкретно: дерево отрезков, dfs, Дейкстра(привет, РОИ 2021), бинпоиск, СНМ, эйлеров обход. Ну и формально на РОИ 2021 я писал алгоритм Куна, но для полного решения он не нужен, и вообще это просто тот же самый dfs.
Нагромождение задачи структурами данных не делает её содержательной, скорее наоборот. На РОИ нельзя брать шаблоны, поэтому время на реализацию идеи не должно быть сильно огромным, иначе всё упрется в умение писать один и тот же код в сотый раз.
Мой последний всерос мне понравился(ещё бы), спасибо большое жюри за проделанную работу.
Отдельно по задачам:
A1, A2
Очень простые задачи, видимо авторы сильно боялись повторить казус с A2 прошлого года.
B1
Да, это конструктив, и такая задача вполне могла бы быть на олимпиаде по математике. Однако стоит отметить, что она была ОЧЕНЬ хорошо подготовлена для олимпиады по информатике, а именно было очень много подгрупп на частные случаи, которые потом приводили к полному решению. Возможно, многих людей скосил формат что ты не ускоряешь решение, а что улучшаешь идею, как было отмечено в одном из комментариев выше.
C1
Задача с очень сильным скачком и малым количеством подгрупп. Не самая удачная C, но и не самая неудачная.
D1
Опять же, сильный скачок, полиномиальное решение требует сильного концептуального продвижения в конструкции, с которым никто не справился.
B2
Это тоже конструктив, но в отличие от B1, подгруппы не приводят к решению, а уводят от него. Задача сама по себе неплохая, но как по мне лучше вписывается в ICPC формат или в олимпиаду по математике, нежели, чем в IOI формат.
C2
Задача хороша во всём. Условие для конкретных чисел проверить за полином нельзя(потому что это рюкзак), а сразу для многих можно. Причём она в каком-то смысле обобщает фольклорную задачу про одномерный случай($$$b = 0$$$), за который давали 12 баллов. Достаточно плавно решается, за что спасибо.
D2
Неплохая задача, но у неё было слишком длинное условие и слишком перегруженный формат, из-за чего приходится тратить немало времени на реализацию.
Как то я не очень вовремя, ну и ладно.
Все таки призерство на всеросе не определяется умением решать конкретно конструктивные задачи. Выявление так называемых способностей к информатике это не сдавание задач Б на полный балл. И претензия к задачам заключается в том, что люди не придумавшие получают различие балла такое, что добрать его по другим задачам является задачей слишком сложно. Это связано с тем, что подгруппы раскиданы плохо. на всеросе по сути было 7 задач, по которым выставлялись баллы потому что D1. Из них 2 задачи почти у всех участнкиов были либо сданы на +- 50, либо на 100. Причем глубина задачи была очень небольшая. В задаче В1 требовалось придумать одну методику методом тыка, а потом понять, что ее разворот дает расшифроку. В задаче B2 требовалось кукарекнуть. Таким образом, участники, считавшие, например, что В2 — соедржательная задача ее не решили. Потому что не додумались, что можно пихнуть туда тупой жадник или кукарек. И это было бы не так страшно, если бы существовал другой адекватный подход к решению, набиравший большие баллы. Но к сожалению, ни за частичное продвижение в идее, ни за другие подходы много баллов почти никто не смог получить. Более того, в задаче С1, например, наблюдался резкий скачок сложности. Решение на +- 40 баллов является очевидным для почти любого опытного участника. Его оптимизацию, которую, к слову, надо мучительно пихать награждаются мизером в примерно 10 баллов. Участники очень высокого уровня могли посдавать еще решение за квадрат, но их призерство, кажется, и не рассматривается. По сути за задачу разыгрывалось 10 баллов.
Если подвести итог, то А1А2 сдали все. 0 баллов за каждую за Б1 давалось 53 балла, причем разбалловка была почти 0/53. за С1 давалось 10 баллов. За D1 давалось 0. За B2 давалось непонянтое кол-во баллов, но, кажется, там либо набирается число от 20 до 45, либо 100. С2D2 отличные задачи, претензий нет, но набрать баллы в D2 сложно из-за низкой стоимости подгрупп. Итого получается, что возможностей для отрыва друг от друга у прослойки призеров, но не победов очень невысока. Как то непонятно получается. Плохое распределние баллов и большой их пласт в задачах, которые все считают стремными и стал самым плохим аспектом, кажется.
Я себя считаю вполне сильным участником и, споткнувшись об обе бшки (47 и 40 соответственно) и, в целом, сильно завалив второй тур, получил диплом призера. Но бшки меня вполне конкретно ошеломили и резлуьтат вместе с моральным настроем сильно подкосили.
Мои извинения, если пишу слишком поздно, но лучше поздно, чем никогда.
A1/A2 — легкие задачи, сдавались быстро, считаю что такие и должны быть
C2/D2 — классные задачи, много подгрупп, многие люди набрали разные баллы по этим задачам
B2 — интересная задача на идею, немного неожидаемого формата для B всероса, но в принципе норм.
Вот про B1/C1/D1 я уже не совсем доволен. Посмотрев на таблицу результатов, видно что почти все, кто хотел набрали 43 + 23 баллов по С1/D1, то есть исход первого тура решался просто из-за одной задачи B1, которая в свою очередь была на одну простую идею (до которой многие не дошли). В итоге тем, кто набрал 36-47 баллов по B1, было очень сложно обогнать тех на втором туре, кто набрал 100 баллов по B1. Тем самым первый тур получился немного несбалансированным.
В целом, я остался доволен олимпиадой, может за исключением первого тура. Я, один из немногих, кто не сдав ни B1, ни B2 стал призером, что, мне кажется, говорит о хорошей олимпиаде.