Всем добрый день.
На прошлой неделе в Санкт-Петербурге начались традиционные учебно-тренировочные сборы школьников перед Всероссийской олимпиадой. Когда-то они выполняли отборочную роль, сейчас это лишь тренировки и учёба вместо школы. В пятницу я решил повторить свою прошлогоднюю лекцию про то, как вести себя на контестах и что может помочь/мешать решать задачи/набирать баллы, кроме знания алгоритмов. Алгоритмы рассказывают везде: и на e-maxx.ru, и в ЛКШ, и на Хабре, и на Codeforces. А вот никакой общедоступной информации на тему "а как организовать себя на контесте" я не видел. Когда я был школьником, разве что иногда кто-нибудь из преподавателей мимолётом замечал, что неплохо бы читать все задачи в первые минуты и писать заглушки когда-нибудь в течение контеста, потому что "напишете заглушки по каждой из шести задач — будет второй диплом на Всеросе".
Вся доступная мне информация собиралась, утрясалась и в прошлом году я решил прочитать лекцию на Петербургских сборах. Мне показалось, что никто не уснул, а информация оказалось полезной и в этом году лекция была повторена с небольшими улучшениями и записью на камеру. Представляю на суд общественности запись лекции и шпаргалку, по которой я читал.
Спасибо, интересно посмотреть. Шпаргалка заинтриговала. Хоть оно вроде бы рассчитано на школьников, но должно пригодиться всем.
Что-то новое, это намного интересней, чем 100500 лекций на тему "как еще можно написать дерево отрезков".
Там есть пара фраз про командные контесты (но действительно пара). В принципе, на эту тему тоже можно что-нибудь соорудить (даже коллективное): взять и собрать все грабли, на которые кто-то наступал. Например:
.
Это другое. Такое у нас тоже активно используется: скажем, Дима с Пашей решают, а я вбиваю циклы, вообще не зная, зачем и почему это происходит.
Я говорю именно про парное программирование: когда чтобы каждую написать следующую строчку, два человека должны прийти к консенсусу.
Блин, может, это немножко не в тему, но первый вариант у меня вызывает ностальгическое ржание:). Последние года два время от времени попадались задачи, в которой некоторая часть кода была чисто на творческую работу на листочке, и пишущий человек зачастую не понимал, почему я настоятельно требую обрабатывать такой случай и забить на другой. Тогда кодер(обычно Паша Холкин) говорил: "Ты понимаешь, что я это пишу, но за код я абсолютно не отвечаю?" В итоге получалось, что задача посылалась, а как она работает, по сути знал только я(а иногда даже я не знал). Учитывая, что я не самый внимательный человек на планете, посылки таких задач всегда были рискованными. Но, к счастью, зачастую проходили, чем вызывали продолжительный смех, особенно когда другие саратовские команды не могли ее сдать.
А если по теме говорить — то такой стиль написания действительно бывает полезен, но нужно знать, когда и как. Вариант "Кодить в одиночку" в большинстве случаев сильно экономит ресурсы(особенно ресурсы на обдумывание следующих задач), но, как уже говорилось, сидящий за компом человек может "зависнуть". Второй же вариант, как мне кажется, нужно подключать, когда уже известно, какую задачу писать следующей и как.
.
Увы — я только недавно начал что-то такое вести. Есть случаи, которые мы очень хорошо запомнили и сделали выводы. Не записаны, но стараемся помнить.
Конечно, такая схема тоже ненадёжна. Хотя вот на финале у нас в Team Notebook был небольшой checklist на тему "что делать, если задача не сдаётся". То ли забыли, то ли не помог — точно не помню :(
Вот эти шесть правил, которые я сразу вспомнил, мы на контестах постоянно используем. Например, если в середине кто-то один прочитал, другой придумал решение, а меня попросили написать, то я всегда сначала читаю условие, чтобы поддерживать инвариант 1.
+1 к первому пункту. Даже очень сильные команды иногда про него забывают и из-за этого сливают важные контесты.
Нашёл относительно древнюю презентацию на английском на тему командной работы и каких-то прочих мелочей. Автор, если не ошибаюсь — Андрей Лопатин (KOTEHOK)
Ну все, теперь осталось только команду найти)
А если серьезно — спасибо) Никаких шокирующих тайн там не увидел, но перечитать полезно. И несколько интересных моментов, вроде ошибки деления на 0 — для себя открыл)
Я видел несколько статей и заметок по поводу командных стратегий, например, всем известная Как стать чемпионом мира по программированию — но все они довольно древние.
Кажется, пора заводить сборник всем известных ссылок и очевидных вещей.
Спасибо! Можно ли посмотреть где-нибудь другие лекции со сборов? Думаю, многим бы они пригодились.
Увы, это пока единственная записанная лекция, насколько я знаю. Я еще точно планирую в эту пятницу записать свою вторую лекцию на тему "как не бояться и сдавать сложные и техничные задачи и полезные фишки языков C/C++/C++11". Появится так же: где-то в начале следующей недели.
Можно узнать что-нибудь о судьбе этой записи?
Да. Она, в принципе, получилась. Но там есть много мест, которые надо обязательно править, иначе получится некорректная информация (например, в одном месте я совершенно нагло заявил, что move-конструкторы хоть когда-то автоматически генерируеются, что, разумеется, неправда, иначе бы это не было обратно совместимо). Я про неё в какой-то момент забыл, на неделе займусь редактированием и наложением субтитров с комментариями.
Казалось бы
1) C++11 действительно не обратно совместим
2) move-конструктор таки генерируется(aka Implicit declaration), если нет кастомного copy/move конструктора
Буду рад, если разубедишь)
Можно узнать что-нибудь о судьбе этой записи?
Исторически отредактировать и выложилось не сложилось, а выкладывать сильно не особо материал мне не хочется.
На самом деле, основная идея написания техник очень проста: дробим задачу на огромное количество задач поменьше и не такие страшные, пишем и отлаживаем их одну за одной, изолируем друг от друга в классах (тогда заодно можно будет писать юнит-тесты или заменять одну подзадачу на её "тупую реализацию" в целях отладки), добавляем тонны
assertов (например "сошлось умное решение с тупым на тех же входных данных" — если всё написано через классы и методы, а не глобальные переменные, то это совсем просто).В частности, стоит разделять задачи даже в ущерб производительности (за исключением ситуации "точно надо очень сильно вгонять, а время есть только на одно решение, времени переписывать не будет никогда"). Например, если есть построение графа, dfs, а потом — heavy-light, то все промежуточные структуры стоит строить явно: так будет намного проще отлаживать (потому что каждая часть кода выполняет ровно один стандартный алгоритм) и понимать происходящее (потому что программа точно соответствует словесному описанию решению и можно рисовать промежуточные состояния).
Разделение удивительно хорошо работает. Даже если не работает с первой попытки, то несколько отладочных выводов промежуточных результатов помогает: выполняем размышление на тесте руками, выводим структуры, построенные программой, ищем первое отличие. Даже если ошибка на самом деле раньше первого отличия, ничего страшного: найдём какую-то (не вызванную некорректными входными данными — мы же их вывели и проверили глазами, а части кода изолированы), исправим, повторить итерацию.
Вообще говоря, по-моему была бы неплохой идея прикрепить это видео (и ещё другие если они будут) к сайту emaxx. Особенно учитывая то что вроде его обещали пообновлять в связи с переездом
"заставили протереть пианино" — это травма детства?) Не, на самом деле круто, и мало кто берется на тему поведения на контесте рассказывать (и мало кто может), обычно только руками разводят, что, дескать, кто как решает это только гены определяют (xd). И впрямь ведь есть вещи, поддающиеся контролю, и очень хорошо что кто-то рассказал, как у него это получается. Мне вот лично с другой стороны тренировка увиделась, т.е. что это не просто чуть менее унылый режим сбора плюсов, что действительно имеется необходимость проверить свои правила. Да и много чего там было сказано нового, все же человек явно больше на контесты поездил.
Еще одно — была идея, как можно начать иначе подходить к решению, внести по ходу просмотра не мог) Можно переписать условие, сохраняя баланс формальности/понятности, как это у себя в блоге делает Petr. Пример из последнего, вот это он записал как you were given a set of cells on the infinite grid, and were asked to find another set of cells that has the same number of cells in each row and in each column as the original set, but has the smallest possible intersection with the original set. Были там и более показательные примеры, но идея в том, что, как правило, выбор способа решения производится скорее по впечатлению, чем по продиктованной необходимости (это тоже только с некоторыми оговорками можно утверждать). А так условие предстает в виде, который можно назвать "изначальный". Но это тоже еще надо уметь так сформулировать.
Нет, нужен был относительно необычный предмет, чтобы слушатели не засыпали и хоть что-нибудь запомнили.
А я уж подумал что хоть у кого-то пианино дома было. А вообще да, трудновато запоминать, когда часто о гипотетических вещах разговор заходит.
У меня и сейчас есть, даже в музыкальной школе на третьем курсе в соответствующем классе учусь. Но протирать скорее не заставляют :)
С собой его туда не носишь?) А я вот дома буду скоро, синтезатор протру и обратно в шкаф) Единственное что я вынес из занятий на нем, так это что важно, чтобы музыкальные вкусы пианиста совпадали со вкусами соседей) Ну и что в первую голову надо учить две вещи — марш мендельсона и мурку, голодным тогда не останешься)
Нет, не ношу и втихую подсмеиваюсь над гитаристами.
А еще это лечится нормальной звукоизоляцией. Ну или занятиями на левой педали.
Хе, ты что, если хотя бы медяк на повесишь на веревочку, считай не гитарист. Играть можно чуть позже поучиться, успеется. Ну а звукоизоляция что то на ум не приходит нормальная, ковры на стенах нынче не в моде, хотя на потолках уже где-то видел.
Кто-нибудь скиньте шпаргалку. Ссылка не работает.
Ссылка работает. New link
yeputons ссылка на конспект опять не работает, не могли бы Вы еще раз выложить, пожалуйста.
Спасибо большое, сегодня-завтра должна появиться. Если не появится — пинганите меня ещё раз.
Какое английское слово используется как "заглушка"?
Можно попробовать "stub".
спустя 10 лет все равно актуально