Ну упасть с ошибкой в этом формате невозможно: запуск программы идет на машине участника, за 6 минут генерируется выходной файл, который и отправляется, и проверяется потом по истечении раунда. Если кто не успел за 6 минут сгенерировать решение по каким-либо причинам, то он теряет возможность отправить его по данной задаче, так что никакой интриги и не было бы, у участника уже во время раунда в турнирной таблице стоял бы 0 за задачу.
Допустим, я гражданин Украины, бакалавр профильной специальности. Если я пройду собеседование и буду жить в питерском общежитии, обучение будет тоже бесплатным?
Превосходная статья, спасибо. (Давно хотел рассказать про суффиксный массив, но всё как-то руки не доходили.) А тут всё даже лучше расписано, чем можно было бы представить :)
Вообще, алгоритм Сандерса, насколько мне известно, применяется редко: у него и константа нехорошая в оценке сложности, и кодировать его не так-то просто на самом деле. Алгоритма за O(N log N) в большинстве случаев вполне хватает. (Собственно, точно как же, как и RMQ алгоритмом Фараха-Колтона-Бендера… хотя его ещё можно кое-где встретить.)
На самом-то деле есть еще суффиксный автомат. По классу решаемых задач он аналогичен суффиксному дереву, а строится гораздо проще Укконненна, тоже за O(N). Опять же, если экономить память и хранить таблицу переходов мапами, то время построения увеличивается… аж до O(N log |Σ|), где Σ — размер алфавита. Серьёзно, даже для китайских иероглифов это капля в море.
Добавлю ещё, что там была потрясающая интрига касательно победителя.
Главный соперник Митричева — Lou Tian Cheng, также известный как ACRush.
Принцип этого соревнования таков, что каждая из трех задач оценивается в 1 очко, и в турнирной таблице выше тот, у кого больше сдано задач, а при равенстве выше тот, у кого сумма времен, потраченных на каждую задачу с начала раунда, ниже. При этом финальная проверка ответов происходит только после того, как раунд закончится.
Так вот, ACRush опережал Митричева на протяжении всего раунда. Митричев сдавал те же задачи, по количеству они всегда были одинаковы — но ACRush сдавал их быстрее, уже и не надеялись на победу Пети. И тут раунд кончается, происходит финальная проверка, и у ACRush падает одна из задач с неправильным ответом, и он оказывается с двумя, и опускается на два места, пропуская вперед Петю с тремя решенными медленнее, но правильно :)
Да, кстати, насчет сюжетов.
О RMQ-цикле я уже понял, а что еще вы планируете (и напишете), чтобы я зря не продумывал наперед?
У меня просто подготовка одной серьезной статьи вроде «Декартового дерева» — с иллюстрациями, исходниками, большим количеством красиво отформатированного текста — занимает довольно продолжительное время, минимум полдня. Не хотелось бы тратить его зря, если материал пересекается :)
Нееее, статью о суффиксном массиве я вынашиваю уже много месяцев, не советую отбирать у меня этот хлеб, это же давно заметная мечта, там столько классного описать-то можно… :)
Насчет декартовых деревьев: там завершать-то оставалось только функциональную реализацию, которая не всем интересна и в принципе к алгоритмистике не относится (разве что пропагандирует персистентные структуры данных, но на это можно и отдельный цикл статей выделить).
Чаще всего просто не нужно (зато break и continue юзается десятками раз в каждом исходнике).
Единственный пресловутый случай, когда мне goto на олимпиаде помогало — это тот самый выход из нескольких циклов.
Извините, был неправ. Надеюсь, в следующем году, когда я закончу бакалаврат, эта возможность останется.
Вообще, алгоритм Сандерса, насколько мне известно, применяется редко: у него и константа нехорошая в оценке сложности, и кодировать его не так-то просто на самом деле. Алгоритма за O(N log N) в большинстве случаев вполне хватает. (Собственно, точно как же, как и RMQ алгоритмом Фараха-Колтона-Бендера… хотя его ещё можно кое-где встретить.)
На самом-то деле есть еще суффиксный автомат. По классу решаемых задач он аналогичен суффиксному дереву, а строится гораздо проще Укконненна, тоже за O(N). Опять же, если экономить память и хранить таблицу переходов мапами, то время построения увеличивается… аж до O(N log |Σ|), где Σ — размер алфавита. Серьёзно, даже для китайских иероглифов это капля в море.
Главный соперник Митричева — Lou Tian Cheng, также известный как ACRush.
Принцип этого соревнования таков, что каждая из трех задач оценивается в 1 очко, и в турнирной таблице выше тот, у кого больше сдано задач, а при равенстве выше тот, у кого сумма времен, потраченных на каждую задачу с начала раунда, ниже. При этом финальная проверка ответов происходит только после того, как раунд закончится.
Так вот, ACRush опережал Митричева на протяжении всего раунда. Митричев сдавал те же задачи, по количеству они всегда были одинаковы — но ACRush сдавал их быстрее, уже и не надеялись на победу Пети. И тут раунд кончается, происходит финальная проверка, и у ACRush падает одна из задач с неправильным ответом, и он оказывается с двумя, и опускается на два места, пропуская вперед Петю с тремя решенными медленнее, но правильно :)
О RMQ-цикле я уже понял, а что еще вы планируете (и напишете), чтобы я зря не продумывал наперед?
У меня просто подготовка одной серьезной статьи вроде «Декартового дерева» — с иллюстрациями, исходниками, большим количеством красиво отформатированного текста — занимает довольно продолжительное время, минимум полдня. Не хотелось бы тратить его зря, если материал пересекается :)
Единственный пресловутый случай, когда мне goto на олимпиаде помогало — это тот самый выход из нескольких циклов.