В январе в грантовой программе фонда Виктора Шабурова Botan Investments приняли участие преподаватели 14 вузов. Больше всего тренировок провели в УрФУ и Саратовском ГУ. В этих же университетах удалось привлечь к тренировкам больше всего студентов — 31 в УрФУ и 15 в Саратовском ГУ. Прием заявок на участие в программе продолжается, мы всегда рады видеть новых участников!

Фонд Botan Investments традиционно выступил одним из спонсоров зимних сборов в Петрозаводске, которые прошли с 29 января по 8 февраля, а также спонсировал участие команды КФУ в этих сборах. Финансовую поддержку также получили студенты ПГНИУ, которые в марте отправятся на сборы по спортивному программированию в Перми.

В нашей группе ВК вышел цикл постов Михаила Рубинчика, посвященных лагерям по программированию для школьников: развитие лагерей для школьников, формат обучения в лагерях, деление школьников на группы, и как живут группы в течение смены.

А сегодня Михаил рассказывает, как связаны наука и олимпиадное программирование.

Этот пост про то, как задачи в ICPC связаны с наукой. Я хочу рассказать, какие научные темы пересекаются с темами олимпиадных задач, и привести пример идеального сотрудничества с научным руководителем. А еще пригласить принять участие в эксперименте. Конечно, научном :)

Про связь науки и олимпиад

Большинство бывших участников ICPC работают в IT-компаниях. Небольшое количество уходит в другие сферы, например, в банки. Очень маленький процент уходит в науку или образование. И наконец, единицы остаются в олимпиадах: организовывают контесты, готовят задачи, тренируют команды. Чем можно заниматься и чем лично я занимаюсь в олимпиадах, я уже писал на CF.

В этом посте я бы хотел поговорить о связи научных и олимпиадных задач. Вот, например, Илья Разенштейн писал в одном из постов, что они не связаны. Из своего опыта могу сказать, что все-таки связаны, по крайней мере та наука, которой занимался я, связана. В школьных и студенческих олимпиадах есть популярные темы, которые хорошо укладываются в форматы задач ICPC/IOI. А есть темы, которые не укладываются в эти форматы или которые пока не стали модными в олимпиадах (например, то, чем занимается Илья).

Если вам действительно нравятся темы, которые вы привыкли видеть в IOI/ICPC, то можно поискать научную работу именно по ним. Например, я изучаю строковые алгоритмы, которые в очень похожем виде есть и в науке, и в олимпиадах. Большую часть задач, решенных с научной целью, я потом давал на контестах. Сложные задачи из моих статей, конечно, никто не мог решить за 5 часов, но те, что попроще, решили многие.

Вот еще примеры тем, которые встречаются и в науке, и в олимпиадах:

- Графы.
- Конечные автоматы.
- Наверняка что-то есть из вычислительной геометрии, но я не так хорошо разбираюсь в этой области.
- Структуры данных. Деревья отрезков, например, никто не изучает, а сбалансированные деревья изучают довольно активно. В частности, Тарьян и Слейтер изучали, как сделать произвольное бинарное сбалансированное дерево персистентным.

Допустим, вам интересно. Но что делать, чтобы попасть в науку? :) Можно разбираться во всём самому, но все-таки будет сложно выжить без научрука, который хорошо знает вашу тему (или хотя бы что-то около). Поэтому я рекомендую узнать обо всех ученых, которые занимаются теми же исследованиями и потенциально могут стать вашим научруком. О том, как проверить, кто настоящий ученый, а кто нет, я написал отдельную статью.

Про идеальное сотрудничество с научруком

Если говорить про моего научрука, то я в диком восторге от нашего сотрудничества. Приведу пример работы над этой статьей.

Я предложил научруку задачу и идею её решения. Он в целом ее одобрил и даже согласился, что решение можно публиковать и в таком виде, но предложил сделать его более красивым: “O(n log ^ 2 n) не так круто, давайте придумаем за O(n log n)”. Я улучшил алгоритм, рассказал о нем научруку, в тот же вечер он доказал, что это O(n log n), и мы начали писать статью. Я описал на русском языке деревья отрезков (знаю эту тему, но не знаю английский :-) ). Остальное на английском написал научрук и затем перевёл мою часть. Научрук выбрал конференцию, на которую можно отправить статью. Когда статью приняли, мы вместе обсудили выступление, я подготовил презентацию, он ее проверил, и я выступил на конференции.

То есть хороший формат взаимодействия с научруком — это когда основу задачи придумываете вы, а он подсказывает важные вещи, находит ошибки, выбирает журналы и конференции. С хорошим научруком вам не нужно думать ни о чем, кроме задачи и решения. Мне пришлось разве что подумать, какие взять билеты, чтобы добраться до конференции в Италии :)

В нашей команде было две роли, но бывает и гораздо больше. В крупных научных группах нормально, что один человек изучает материал из статей, второй проводит эксперименты и формулирует гипотезу, третий доказывает, четвёртый пишет статью, а пятый рисует картинки. Я серьёзно! :) Причём рисовать картинки могут два разных человека: один для китайских конференций, а другой для американских, потому что в некоторых областях наук в разных странах принят разный дизайн.

Про эксперимент

Тем, кому до сих пор кажется, что наука бесконечно далека от ICPC и от вас, предлагаю эксперимент. Есть статья 2016 года, в которой разбирают случаи (кажется, их там 8 штук :)) Во всех случаях, кроме одного, решение за O(n log n). А в оставшемся — за O(n log ^ 2 n). Это означает, что если для последнего случая сделать O(n log n), то и весь алгоритм будет быстрее. Первый шаг эксперимента: прочитать статью, найти тот самый медленный случай и разобраться с алгоритмом. После этого можем созвониться и вместе обсудить решение и способ его улучшить. Вдруг придумаем :) А если не придумаем, можем привлечь кого-то ещё и порешать вместе.

Зачем это лично мне? Помимо популяризации науки среди сообщества спортивных программистов, есть еще одна причина. Из-за очень плотного графика у меня нет времени прочитать эту статью. А задачка интересная, хочется ее порешать. Естественно, все, кто поучаствует в решении, станут соавторами. Даже если вы только перескажете мне статью, а всё придумаю я, мы все равно будем соавторами. А если придумаете без меня, сможете опубликоваться от своего имени. Если интересно поучаствовать, напишите мне в личку в Телеграм: @rumi13.

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

Если есть хороший научрук, то вы просто решаете задачи, а всё остальное за вас сделает он. Если вам интересно попробовать свои силы, я могу сыграть для вас роль научрука/организатора.