Уже несколько лет я веду онлайн-курс по программированию, алгоритмам и так далее — algoprog.ru. Теперь у него есть и англоязычная версия:

algoprog.org

Это онлайн-курс, предназначенный для широкого круга студентов, от полных новичков (даже тех, кто не знает ни одного языка программирования) до относительно продвинутых и знающих людей. Курс включает в себя набор тем от основ программирования (на Python) до весьма продвинутых алгоритмов и структур данных. В большинстве тем есь теория и задачи (взятые из informatics.msk.ru или Codeforces).

В отличие от обычных сайтов с архивом задач, во время обучения на algprog вы также получаете обратную связь от меня. Я смотрю ваши решения, засчитываю или игнорирую их, советую, как это можно было бы написать лучше, подсказываю по решениям, которые не проходят тесты, и т.д. Кроме того, для большинства задач есть "хорошие решения", на которые вы можете посмотреть после того, как сами решите задачу, и есть раздел "Найти ошибку", где вы можете попрактиковаться в поиске ошибок в решениях других учеников. И, конечно же, вы всегда можете связаться со мной по любым вопросам, которые возникают в ходе ваших занятий, или по программированию в целом.

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

Я думаю, что курс будет полезен всем пользователям codeforces с рейтингом до 1700-1900 (а может и выше), и я буду рад видеть вас на курсе.

Подробная информация о курсе: https://algoprog.org/material/about

Собственно материалы курса (темы, теория, задачи) доступны всем желающим бесплатно. Если же вы хотите полноценно заниматься на алгопроге, то цена и условия оплаты указаны тут: https://algoprog.org/material/pay

В настоящее время курс английской версии находится в бета-версии, для первых пяти студентов, которые будут заниматься на английском языке (и ловить баги :) ), будет действовать скидка 50% в течение года.

Естественно, русскоязычный курс (algoprog.ru) точно также работает, поэтому я буду рад видеть и русскоязычных учеников.

UPD: Оплата возможна российскими картами, также возможна, хотя иногда и бывают проблемы, оплата не-российскими картами. UPD2: Теперь есть два способа оплаты не-российскими картами, надеюсь, что хотя бы один будет работать.

Обо мне:

Меня зовут Петр Калинин, я старший разработчик в Яндексе. Я бронзовый призер Международной олимпиады по информатике (IOI) 2001 года и золотой призер IOI 2002; в составе команды Нижегородского государственного университета я дважды участвовал в финалах ACM ICPC.

В той или иной форме я преподаю программирование школьникам с тех пор, как окончил школу в 2002 году (в качестве преподавателя в различных летних школах и т.д.); я веду отдельный курс с 2013 года.

Среди студентов алгопрога разных лет (сортировка по рейтингу на алгопроге):

Stefan2417 — https://algoprog.org/user/505865
GandarfGamer — https://algoprog.org/user/315118
EndRay — https://algoprog.org/user/322702
Aleks5d — https://algoprog.org/user/254947
MADKIRUS — https://algoprog.org/user/267400
Riladavin — https://algoprog.org/user/260070
_DAC_ — https://algoprog.org/user/491124

...не говоря еще про моего брата KAN, который в некотором смысле был моим первым учеником еще задолго до появления алгопрога.

на правах рекламы :)

Я уже много лет веду занятия по алгоритмам и связанным темам, и по сути по подготовке к олимпиадам. Начиналось это как занятия для учеников лицея 40 г. Н. Новгорода, далее для желающих школьников Нижнего Новгорода и области, а в последние пару лет я добавил и возможность заочных занятий для всех желающих (даже не только школьников).

Сайт курса:

algoprog.ru

На нем есть последовательность тем от самых простых (для тех, кто вообще не умеет программировать) и до весьма и весьма продвинутых. По каждой теме есть теоретические материалы и задачи (задачи взяты с информатикса).

В отличие от обычных сайтов с архивом задач, занятия на алгопроге подразумевают также общение со мной. Я смотрю ваши решения, засчитываю/игнорирую их, даю советы, как лучше можно что-то написать, подсказываю по ошибкам в неполных решениях и т.д. После того, как вы сдали задачу, у вас открывается возможность посмотреть "хорошие решения", которые по каждой задаче я отбираю вручную. Ну и вы всегда можете мне написать по любым вопросам, возникающим у вас в процессе занятий.

Полная информация про курс: https://algoprog.ru/material/0

Занятия (для тех, кто не является нижегородским школьников) платные: https://algoprog.ru/material/pay

Я надеюсь, что мой курс будет полезен всем пользователям codeforces, кроме совсем уж топа, так что присоединяйтесь :)

P.S. По-видимому, когда-то раньше существовал проект algoprog.kz. Ни я, ни мой курс к нему не имеет отношения; я вообще узнал про algoprog.kz только относительно недавно, когда смотрел на результаты поиска по запросу "algoprog".

При решении задач на хеширование вам очень частно бывает надо уметь за $$$O(1)$$$ вычислять хеш любой подстроки заданной строки. Стандартный подход к таким задачам — давайте посчитаем хеши всех префиксов, а дальше будем с этим что-то делать...

(Это кросс-пост поста из моего блога.)

...Итак, стандартный подход устроен следующим образом. Начнем немного с начала. Определим хеш строки (хеш-функцию) так:

(Все вычисления здесь и ниже подразумеваются по некоторому модулю $$$M$$$.)

Посчитаем хеши всех префиксов:

Массив $$$H[i]$$$ можно насчитать за $$$O(n)$$$ очевидным образом ($$$H[i] = H[i-1] + s_i \cdot p^i$$$, массив степеней $$$p$$$ можно насчитать заранее, будет полезно и в дальнейшем).

Хорошо. Но нам надо знать хеш произвольной подстроки, т.е. $$$h(s[i..j])$$$. Очевидно, чтобы его вычислить, нам понадобятся значения $$$H[i-1]$$$ и $$$H[j]$$$. (Особый случай $$$i=0$$$ мы рассматривать не будем, он простой.) Явно напрашивается записать

но вот проблема — то, что получилось, это не настоящее значение хеш-функции для подстроки $$$s[i..j]$$$, а величина, в $$$p^i$$$ раз больше. В результате использовать полученное число просто так не получится.

* * *

Есть два стандартных способа решить эту проблему. Первый — хорошо, давайте разделим полученное выражение на $$$p^i$$$. Но у нас все вычисления — по модулю $$$M$$$, делить в арифметике по модулю возможно не всегда, и в любом случае не очень просто. В простейшем случае, когда $$$M$$$ простое, и $$$p$$$ (естественно) не делится на $$$M$$$, деление возможно и даже не очень сложно (по малой теореме Ферма надо просто умножить на $$$(p')^i$$$, где $$$p' = p^{M-2}$$$; можно заранее вычислить $$$p'$$$ и все его степени). Но лишний код писать все равно не охота.

Второй способ — хорошо, давайте поймем, что в конечном счете нам само значение $$$h(s[i..j])$$$ не нужно. Как правило, нам надо сравнивать хеши двух подстрок, пусть $$$s[i..j]$$$ и $$$s[i'..j']$$$. Мы можем вычислить значения $$$X=h(s[i..j]) \cdot p^i$$$ и $$$Y = h(s[i'..j']) \cdot p^{i'}$$$. Напрямую их сравнивать бессмысленно, но мы можем домножить их на подходящие степени, т.е. сравнить $$$X\cdot p^{i'}$$$ и $$$Y\cdot p^i$$$. Если эти два числа равны, то хеши соответствующих подстрок тоже равны.

Это довольно просто, но не очень красиво. Вы не вычисляете сам хеш, вы вычисляете только какую-то величину, связанную с хешом. При каждом использовании этого хеша вам придется думать, что и как домножать. Ладно если вы только подстроки сравниваете, а если, например, вам надо сделать какую-нибудь мапу, где хеш подстроки является ключом?

Проблема еще и в том, что вам приходится про это помнить и учитывать это в основной программе. Вы бы, возможно, хотели бы написать функцию hash(i, j), которая вам вернет настоящий хеш подстроки $$$s[i,j]$$$ (или написать class StringWithHash с соответствущим методом), и дальше в основном коде не думать про то, что хеш не той системы. Но нет, так не получится...

* * *

Так, вот, оказывается, можно очень просто решить эту проблему — организовать работу с хешом так, чтобы не требовалось ни деления по модулю, ни домножения. Для этого надо просто посчитать хеши не префиксов, а суффиксов. Удивительно, но такая простая идея относительно малоизвестна.

А именно, посчитаем

Вычислить такой массив за $$$O(n)$$$ тоже очень легко (просто $$$H[i] = H[i+1] \cdot p + s_i$$$, эдакий аналог схемы Горнера, даже проще чем раньше — не нужно вычислять $$$p^i$$$).

И теперь внимание фокус:

И это честный хеш. Полученные значения вам уже не надо ни на что домножать, вы можете их сравнивать, можете использовать как ключ в какой-нибудь мапе, и т.д. Вы можете написать class StringWithHash с таким методом, и потом в основной программе уже просто использовать результат вызова метода.

Заодно получили бонусом, что $$$i=0$$$ — это не особый случай. Особый случай теперь $$$j=n-1$$$, но он обходится легко — делаете $$$H[n] = 0$$$ и не надо писать никаких if'ов.

* * *

На самом деле, можно полностью симметрично отразить ситуацию. Выше мы определяли хеш так, что степени $$$p$$$ в формуле возрастали слева направо — как будто самый младший разряд «числа» — это его самая левая цифра.

Можно определить хеш строки наоборот:

Тогда можно посчитать хеши префиксов: $$$H[i] = h(s[0..i])$$$ и аналогично можно вычислять честный хеш любой подстроки. (Правда, $$$i=0$$$ опять будет особым случаем, но это на самом деле ортогональный вопрос.)

* * *

Выше везде я полагал, что запись $$$s[i..j]$$$ включает как символ $$$i$$$, так и символ $$$j$$$. Можно рассматривать всё, как говорят, на полуинтервалах — символ $$$i$$$ включительно, символ $$$j$$$ невключительно (аналогично тому, как в питоне устроены срезы). Тогда написание хеширования еще несколько упрощается (например, $$$i=0$$$ не будет особым случаем ни при каком подходе). Но это тоже ортогональный вопрос.

* * *

Так что мораль: пишите хеширование без домножения и без деления.

Суть поста вкратце: я считаю, что на олимпиадах, целью которых (хотя бы отчасти) является выявление победителя, задачи должны быть составлены так, чтобы победитель не набрал максбалл — победитель должен скорее набирать процентов 70-80.

[TLDR: заходите на universities.meteor.com, оставляйте там отзывы о своих университетах и читайте отзывы других пользователей.]

На codeforces, да и в других местах, регулярно возникают вопросы "куда поступать", "расскажите про университет" и т.п. Это зачастую выливается в длительное обсуждение, но потом подобные обсуждения теряются в глубинах сайта и оставляют мало полезной информации на будущее. Более того, такие обсуждения, как правило, затрагивают только один университет (в лучшем случае — сравнивают два университета), и обычно покрывают лишь весьма ограниченный список тем из того, что хотят знать абитуриенты.

Чтобы исправить эту проблему, я сделал сайт universities.meteor.com

Так сложилось, что в 2008­-2009 годах я написал несколько довольно объемных текстов на разные темы алгоритмического программирования. Писал я их в то время для некоторой группы нижегородских школьников, но с тех пор некоторые из этих текстов я довольно широко распространял, последнее время явно в них указывая лицензию CC-BY-SA.

Теперь я решил выложить эти тексты на github, чтобы а) сделать их распространение еще более широким, но при этом более упорядоченным; б) чтобы желающим было бы проще исправлять ошибки и опечатки, коих там достаточно.

Итак:

https://github.com/petr-kalinin/progtexts

или, если вам интересуют только pdf, а не LaTeX-исходники, то

https://github.com/petr-kalinin/progtexts/releases/latest

Темы текстов (кружочком помечены те, которые получили довольно широкое распространение):

1. • Перебор с возвратом
2. Сложность алгоритмов, O-нотация
3. Различные мелкие алгоритмические идеи, а также около-программистские замечания
4. • Поиск в глубину
5. • Динамическое программирование

Тексты, конечно, подразумевают некоторый начальный уровень знаний. Если за шкалу «уровней знаний» для удобства принять параллели ЛКШ, то тексты ориентированы примерно на уровень начиная с «чуть старше параллели C» и до параллели A'.

Сразу предупреждаю (disclaimer), основной текст писался 5-6 лет назад, поэтому местами могут быть устаревшие фрагменты. Вообще, там было довольно много упоминаний Borland Pascal, я вроде постарался при подготовке к публикации их все убрать, но, возможно, что-то я пропустил. Кроме того, там могут быть и разные другие проблемы и даже где-нибудь может быть написана полная ерунда — я особенно внимательно тексты давно не перечитывал. Сообщайте о таком.

Если тексты вас заинтересуют, и будут комментарии, замечания, ошибки — пишите или (даже лучше!) предлагайте pull-request'ы.

Лицензия на pdf-ки — CC-BY-SA. На TeX-код пока не знаю, какая лицензия; подскажите, какую лицензию лучше использовать?

Люди, занимающиеся со школьниками, а также школьники, занимающиеся программированием!

Посоветуйте, как стимулировать школьников решать задачи?

Вот я веду занятия у школьников. Они далеко не всегда активно решают задачи из дома. То есть проходим мы с ними новую тему, я даю им задачи — они немного иногда успевают решить из класса, но из дома дорешивают мало.

Можно пытаться придумать какую-нибудь систему поощрений. Ну например выдавать каждую неделю по шоколадке тому школьнику, который решил больше всех задач за эту неделю. Но такой вариант обладает рядом недостатков.

17 августа на 72 году жизни скоропостижно скончался Владимир Денисович Лелюх.

Владимир Денисович многие годы учил школьников Нижегородской области программированию и занимался подготовкой участников олимпиад. Он являлся основателем и бессменным лидером нижегородской школы олимпиадного программирования; он много лет вел занятия со школьниками на базе Нижегородского государственного университета, а также во многих школах Нижнего Новгорода и близлежащих городов; многократно проводил серии занятий в Сарове. Он был одним из немногих преподавателей в России, чьи ученики на протяжении почти 20 лет достигали наивысших успехов в олимпиадах по информатике. Восемь его учеников являлись призерами международных олимпиад по информатике; с 1995 года по настоящее время они 13 раз завоевывали золотые медали (что составляет более четверти всех золотых медалей российских участников за всю историю IOI), 1 раз серебряную и 3 раза бронзовые. Из этих 13 золотых медалей две — это абсолютные первые места, и еще одна — это разделенное абсолютное первое место. Команды ННГУ под его руководством неоднократно участвовали в финалах чемпионата мира по командному программированию ACM.

Владимир Денисович активно участвовал в организации олимпиад по информатике. Он был многократным членом жюри Всероссийских олимпиад школьников по информатике и других олимпиад всероссийского масштаба; по его инициативе и под его руководством с 2005 года проводится Нижегородская городская олимпиада школьников по информатике, где он был бессменным председателем жюри. Владимир Денисович был преподавателем лицея 40 г. Нижнего Новгорода, где вел информатику в «Ф» (физических) классах.

До последних дней Владимир Денисович продолжал заниматься со школьниками; на конец августа он планировал серию интенсивных занятий со школьниками Нижнего Новгорода.

Светлая память!

В. Д. Лелюх и Михаил Баутин, летняя школа «Одаренные дети», лагерь «Лазурный», август 2000 года. (Через пару месяцев Михаил станет абсолютным победителем международной олимпиады школьников по информатике.)

В. Д. Лелюх и Ю. Л. Кетков, закрытие нижегородской областной олимпиады школьников по информатике, февраль 2003

В. Д. Лелюх и Билл Пучер, финал чемпионата мира по командному программированию ACM, март 2003 г., Лос-Анджелес

В. Д. Лелюх ведет занятие своего университетского (воскресного) кружка, ННГУ, ориентировочно 2003 год

В. Д. Лелюх на сборах команд-финалистов чемпионата мира по программированию ACM, январь 2004 г., Петрозаводск

В. Д. Лелюх в летней школе «Одаренные дети», лагерь «Лазурный», июль 2004 г.

В. Д. Лелюх в летней школе «Одаренные дети», лагерь «Лазурный», июль 2004 г.

В. Д. Лелюх в летней школе «Одаренные дети», лагерь «Лазурный», июль 2005 г.

В. Д. Лелюх на закрытии Нижегородской городской олимпиады школьников по информатике, декабрь 2005 г.

В. Д. Лелюх на закрытии Нижегородской городской олимпиады школьников по информатике, январь 2007 г.

В. Д. Лелюх в летней школе «Одаренные дети», лагерь «Лазурный», июль 2007 г.

В. Д. Лелюх на закрытии Нижегородской городской олимпиады школьников по информатике, февраль 2010 г.

Что делать, если вам в программе надо вычислить значение производной некоторой функции, но вам очень не хочется прилагать для этого специальные усилия — т.е. не хочется ни дифференцировать на бумажке, ни забивать ваши формулы в Sage/Wolfram Alpha/Maple/...? Тем более если вы не хотите заново проводить все выкладки, если вдруг окажется, что производную надо брать от другой функции? Естественно, вариант написать (f(x+eps)-f(x))/eps вас по понятным причинам не устраивает тоже.

Вот код, который решает уравнение методом Ньютона. А вот и подробный пост (мой же) с формулами, объясняющий, как это работает и чем это круто.

Я этот способ использовал некоторое время назад (как и сказано на Хабре), когда мне надо было решить систему из двух уравнений методом Ньютона. Потом я спонтанно рассказывал его в ЛКШ.Зима. Потом я обнаружил, что этот прием называется «автоматическое дифференцирование», но, видимо, не очень широко известен. Поэтому подумал, что, пожалуй, стоит про него и написать.

9 февраля (в следующую субботу) с 15:00 до 20:00 на сайте informatics.mccme.ru пройдет интернет-трансляция IX Нижегородской городской олимпиады школьников по информатике. Участвовать могут все желающие, участие полностью неофициальное (т.е. никаких плюшек за результаты не будет, вы участвуете из своего интереса, — но результаты интернет-трансляции подведены будут и вы сможете их даже сравнить с результатам олимпиады в Нижнем Новгороде).

Олимпиада проводится по правилам личных олимпиад (как на региональном этапе) — оценка потестовая, группы тестов отсутствуют, во время тура проводится проверка только на тестах из условия, окончательная проверка проводится offline после окончания тура.

Новость на сайте informatics: http://informatics.mccme.ru/moodle/mod/forum/discuss.php?d=1702.

Спасибо dkirienko за организацию

Нижегородская городская олимпиада — отдельная олимпиада, не входящая ни в систему всероссийских олимпиад, ни в «Перечень олимпиад...» Олимпиада проводится с 2005 года (не считая нижегородских городских олимпиад, проводившихся до 1999 года другими людьми и другой организацией). Авторы задач олимпиады 2013 года:

• I_love_Nastya
• Антон Демидов
• vepifanov
• KAP
• Яна Кашинская
• В.Д. Лелюх
• mmatrosov
• ilyaraz
• AlTimin
• Роман Тимушев
• ashmelev

UPD: участников олимпиады, членов жюри, а также тех, кто почему-либо в курсе задач и/или результатов олимпиады, прошу до окончания трансляции здесь в комментариях не обсуждать ни задачи, ни результаты, ни что-либо еще, что может так или иначе спалить участникам трансляции информацию.

Я так понимаю, что во всех приличных регионах второй тур уже завершился (ну или как минимум должен был завершиться), тут все равно сейчас будет активное обсуждение задач — поэтому я думаю, что следующую историю уже можно запостить и здесь.

...Позавчера утром я сидел на открытии региональной олимпиады в Нижегородской области. Проводив участников решать задачи, я поехал домой. Поскольку с утра я наблюдал некоторые разногласия в вопросах проведения олимпиады между участниками и жюри, я решил все-таки раздобыть “Требования к проведению регионального этапа...” этого года, чтобы вечером, после тура, было что дать почитать жюри. (Сразу отмечу, что я не имею никакого отношения к проведению региональной олимпиады — ни как член местного жюри, ни как разработик задач.)

Чтобы скачать “Требования...”, я, естественно, полез на rosolymp.ru — именно там они были все прошлые годы. Сейчас там я требований не нашел, зато наткнулся на интересную новость. Заголовок новости гласил примерно следующее: “Вниманию жюри региональных этапов олимпиады по информатике!” (здесь и чуть ниже тексты цитирую по памяти, т.к. новость с сайта удалили).

К новости были приложены два файла. Первый назывался circles-check.zip и, конечно, меня сразу заинтересовал. Но второй был doc-файлом, и поэтому я начал изучение новости с него. Как и следовало ожидать, doc-файл был адресовам жюри региональных этапов, и его основная часть состояла из двух пунктов:

1. В условии задачи 2 необходимо заменить ограничение 100 000 на 10 000;
2. Проверяющая программа по задаче 7 содержит неточности; правильная проверяющая программа прилагается.