Привет, Codeforces!

12 октября 2015 года в 12:00 MSK состоится очередной раунд Codeforces #325 для участников из первого и второго дивизионов. Обратите внимание на необычное время начала раунда!

Этот раунд проводится по задачам Регионального этапа всероссийской командной олимпиады школьников по программированию 2015, который пройдет в то же время в городе Саратове. Пожелаем школьным командам удачи на соревновании!

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

Процесс подготовки задач был интересным: мы много раз переделывали условия, переписывали решения, добавляли тесты, изменяли ограничения, даже успели поменять полностью готовую задачу (пришлось останавливать конвейер типографии, который уже печатал условия :-)). Поблагодарим всех кто готовил, помогал готовить задачи, вычитывал условия, писал перекрестные решения: Адилбек adedalic Далабаев, Роман Roms Глазов, Владимир vovuh Петров, Олег Oleg_Smirnov Смирнов, Алексей Perforator Рипинен, Максим Neon Мещеряков, Илья IlyaLos Лось, Виталий gridnevvvit Гриднев, Данил danilka.pro Сагунов, Александр fcspartakm Фролов, Павел HolkinPV Холкин, Игорь Igor_Kudryashov Кудряшов, Елена elena Рогачева, Дмитрий Nerevar Матов, Виталий kuviman Кудасов. Председателем жюри олимпиады является Михаил MikeMirzayanov Мирзаянов (также автором некоторых задач из комплекта). Я же (Эдвард Edvard Давтян) готовил некоторые задачи и координировал работу авторов. Вот такая большая команда авторов получилась (надеюсь я никого не забыл)!

Также, конечно, поблагодарим Максима Ахмедова (Zlobober), Того-Чьё-Имя-Пока-Нельзя-Называть (если не ошибаюсь он/она прямо сейчас пишет дополнительные решения по задачам раунда) за помощь в подготовке задач, Марию Белову (Delinur) за перевод условий на английский язык и снова Михаила Мирзаянова (MikeMirzayanov) за замечательные системы Codeforces и Polygon.

Участникам будет предложено шесть задач и два часа на их решение. Разбалловка будет объявлена незадолго до начала раунда. Всем высокого рейтинга! Good luck and have fun!

P.S.: Также хочется пожелать удачи участникам четвертьфинала чемпионата мира по программированию южного региона, который пройдет в эту среду.

По техническим причинам раунд перенесен на 10 минут

UPD: По задаче Subway roller в наборе тестов присутствовали тесты с поездами длины 1. В данный момент проводится обсуждение того, насколько сильно это повлияло на результаты раунда. Приносим извинения всем участникам, которых затронула эта проблема. В скором времени будет сделано объявление о принятом решении.

UPD2: При подготовке задачи Subway Roller у одного из авторов было ошибочное понимание условия. Из-за этого валидатор допускал существование поездов длины 1, а так же присутствовали тесты с поездами длины 1. Жюри приняло решение, что если участник посылал в течении контеста верное решение, то оно должно быть ему зачтено. Для этого у каждого участника было выбрано первое отправленное решение, проходящее итоговый тестсет (если таковое решение имелось), а остальные решения были пропущены. Так же баллы за все взломы во время соревнования остались без изменения, включая ситуацию, когда взломанное решение считается правильным на новом тестсете (в этом случае взломщик получает свой балл, а решение участника считается полным). Контест будет признан рейтинговым, однако если вы считаете, что данная проблема сильно повлияла на ваш результат, напишите мне в течении 24 часов и мы рассмотрим возможность сделать его нерейтинговым лично для вас.

UPD3: Разбор задач

Привет, Codeforces!

Очередной сезон соревнований по программированию стартовал, и самое время поднять мотивацию многим из вас.

От лица фонда Botan Investment и его президента Виктора Шабурова хочу анонсировать уникальную акцию. Цель акции — поддержать и развить интерес к спортивному программированию в регионах России. Пока Москва и СПб исключены из списка, а студенты и выпускники вузов других городов могут получить приз: 50000 рублей и поездку в Сочи для знакомства с командами стартапов Botan Investment.

Для того, чтобы получить приз, ты должен:

• стать красным (гроссмейстером) на Codeforces и быть им на протяжении трех раундов подряд;
• учиться на 4-м или более курсе университета или быть выпускником вуза РФ;
• быть не старше 30 лет;
• быть готовым приехать в Сочи (разумеется, за наш счет) и очно подтвердить свои навыки на очередном раунде.

Более подробно об акции — на сайте Botan Investment.

Виктор, я думаю, не нуждается в представлении на Codeforces, потому как еще свеж в памяти Looksery Cup 2015.

Если ты уже готов — смело пиши на edu@botaninvestments.com по вопросам организации поездки.

Привет, Codeforces!

6 октября 2015 года в 19:30 MSK состоится очередной раунд Codeforces #324 для участников из второго дивизиона. Традиционно, участники из первого дивизиона приглашаются поучаствовать в соревновании вне конкурса.

Хотелось бы сказать большое спасибо Zlobober (Максиму Ахмедову) за помощь в подготовке задач, Delinur (Марии Беловой) за перевод условий на английский, MikeMirzayanov (Михаилу Мирзаянову) за системы Codeforces и Polygon. Это мой первый раунд на codeforces, и, надеюсь, что не последний.

Участникам будет предложено пять задач и два часа на их решение. Разбалловка будет объявлена позднее.

Все герои задач имеют своих прототипов — моих друзей, знакомых, родных, которым и посвящается этот раунд.

Желаю удачи и высокого рейтинга!

UPD: Разбаловка стандартная 500-1000-1500-2000-2500

UPD2 Раунд завершен, всем спасибо за участие!

Поздравляем победителей!

1). Siunaus

2). aasddf

3). M_H_M

4). lal

5). femsub

Разбор

В этом посте я хочу рассказать в двух словах о том, как пистать формулы на кодфорсесе так, чтобы они выглядели формулами. По сути это краткое введение в начала языка разметки , который и используется на Codeforces. Оно будет полезно тем, кто совсем не знает, как писать формулы и почти любому, у кого нет об этом систематических знаний.

Три важных правила

Самое главное правило: формула заключается в доллары ($), как в скобки.

Ещё одно важное правило: если вы хотите, чтобы некоторая операция была применена к целой группе символов, эту группу надо оформить в блок с помощью фигруных скобок. Например, если написать 2^x+y, получится 2^x + y. Чтобы получить 2^x + y, надо заключить показатель степени в блок: 2^{x+y}

Третье правило — для перфекционистов. Для экономии траффика Codeforces печатает простые формулы, в которых ничего особенного нет, обычным текстом. Иногда это получается не очень красиво C_{x_i+y_i-2}^{x_i-1} = C_{xi + yi - 2}^x_i - 1. Если вы напечатали формулу и вам не понравилось, как Codeforces её интерпретировал, можно в начале формулы добавить команду \relax. Тогда формула будет гарантированно красивой, в ущерб траффику: \relax C_{x_i+y_i-2}^{x_i-1} = .

Арифметические операции.

Сложение и вычитание пишутся обычными знаками + и -. Что касается умножения, то обычно оно в математике обозначается либо просто пустым символом (xy — это произведение чисел x и y). Также есть символ (\cdot). Если же надо перемножить два сложных выражения (), или важны оба сомножителя, а не только величина произведения (в выражениях вида поле ), используется символ  × , который может быть получен командой \times.

С делением всё несколько сложнее. Обычно в математике деление не пишется в одну строчку, однако желание не городить дроби на ровном месте тоже вполне понятно. В таком случае всегда можно написать : или / (x:y, x/y). Если же вы хотите всё же написать дробь, на это есть две похожие команды: \frac и \dfrac. После любой из этих команд надо написать блок числителя и блок знаменателя, например: (\frac{1}{4}). С использованием \frac дроби получаются маленькие, что подходит, в основном, для самых простых дробей. Если вы хотите написать большую серьёзную дробь, вам потребуется \dfrac: (\dfrac{x+y}{x^2+y^2}). В принципе, если числитель или знаменатель односимвольный, можно его не заключать в скобки, например: (\frac14x), но только если числитель не является буквой.

Верхние и нижние индексы.

Если вы хотите написать нижний индекс, вам поможет символ _, а верхний индекс (в основном это бывает показатель степени), то символ ^: (x_i + y_i)² ((x_i+y_i)^2). Так же, как и с дробями, в нижний или верхний индекс можно поместить блок, но если индекс односимвольный, то можно этого не делать.

Разные полезные спецсимволы и советы

Текст — текст (---) — не в формулах, а в тексте. Это тире, а не дефис (не работает, если нет окружающего текста)
(\dots) — среднее многоточие для формул в англоязычных текстах.
(\ldots) — нижнее многоточие для формул в русскоязычных текстах.
∞ (\infty) — символ бесконечности.
(\in) и (\ni) — символы принадлежности к множеству.
 →  (\to) — стрелочка направо, в выражениях типа x_n → 0.
Многие известные математичские функции можно набирать с \, тогда они будут выглядеть, как формулы, а не просто как текст ( = \tg, = \ln, = \lim и так далее)
Если вы хотите, чтобы индексы были сверхи и снизу, а не сверху-справа и снизу-справа, используйте команду \limits:
= \sum_{k = 0}^nx^k
= \sum\limits_{k = 0}^nx^k.
Если вокруг большого выражения маленькие скобки, можно их сделать подходящего размера, написав перед левой скобочкой команду \left, а перед правой — команду \right. Например: = \left( \dfrac{x+y}{x^2+y^2} \right).

Спасибо за внимание!

Всем привет!

Надеюсь все уже успели оправиться от революции цветов и званий и даже, может быть, попробовать написать раунд в новом для себя положении. Последний раунд собрал космическое количество народу: 8000 человек! И, не побоюсь это сказать, с технической точки зрения раунд прошёл без малейших нареканий! Будем считать, что 15-минутный перенос контеста был частью нашего хитрого плана по достижению рекорда :)

Спешим сообщить, что команда Codeforces способна не только подкручивать цвета и формулы, но и постоянно работать над развитием проекта.

Зайдя на страницу с соревнованиями, вы можете теперь видеть список авторов каждого из раундов! Более того, в профиле у человека теперь есть пункт "проблемсеттинг", по которому можно посмотреть на список всех контестов, к подготовке которых человек имел отношение.

Endagorion, например, выглядит так.

Здравствуй, Codeforces!

Меня зовут Данил Сагунов, и когда-то я был красным... Впрочем, поздравляю всех со Второй Революцией!

Рад сообщить, что в эту субботу, 3 октября в 19:30 MSK состоится Codeforces Round #323 для обоих дивизионов. Задачи для вас придумывали и готовили я и Виталий gridnevvvit Гриднев. Это не первый раунд, в котором мы являемся авторами, и я уверен, что не последний.

В подготовке задач нам помогали мои друзья Максим Neon Мещеряков, Владимир vovuh Петров и Роман Roms Глазов, за что отдельное им спасибо. Благодарю Макса Zlobober Ахмедова за координаторскую деятельность, Михаила MikeMirzayanov Мирзаянова за создание и поддержку систем Codeforces и Polygon, благодаря которым проведение раунда стало возможным, и Марию Delinur Белову за перевод условий задач на английский язык.

Спасибо Владиславу winger Исенбаеву и Александру AlexFetisov Фетисову за прорешивание задач раунда!

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

UPD В e-mail рассылке была указана неправильная продолжительность раунда. Соревнование будет длиться 2 часа.

UPD2 Раунд успешно завершен! Благодарим всех за участие.

Поздравляем победителей первого дивизиона:

1. ecnerwala
2. ikatanic
3. uwi
4. PavelKunyavskiy
5. sd0061

И второго дивизиона:

1. wrong_order
2. ahwhlzz
3. kefaa

Мои поздравления fotiIe96, единственному решившему задачу D!

UPD3 Разбор можно найти здесь

Последние месяцы команда Codeforces с тревогой наблюдала за сильной инфляцией рейтинга, вызванной и притоком новых пользователей и несовершенством формул подсчета.

Со временем это привело к значительным перекосам в цветах и званиях. Например, стать красным в 2015-м году стало значительно проще, чем в 2013-м.

Проведя опрос о том как именно следует внедрить смену цветовой шкалы, мы решили не затягивать нововведения и рады анонсировать обновленные цвета и звания!

Коротко основные изменения: новый цвет: сине-зеленый или циан — как и ожидается из названия этот цвет займет своё место между зеленым и синим, теперь участники второго дивизиона будут лучше дифференцированны; сдвиг всех цветов вверх по шкале рейтинга — смотрите таблицу ниже, достигать вершин станет сложнее; легендарный гроссмейстер — новое звание и раскраска для тех, кто достиг заоблачного рейтинга 2900.

Холодные цвета серый, зеленый, сине-зеленый и синий всё еще соответствуют второму дивизиону, а остальные — первому.

Требования к тренерскому доступу остались неизменными — вам необходимо иметь 2200 или 1900 и богатую историю участий, чтобы стать тренером. Теги к задачам и создавать группы могут ставить участники из первого дивизиона.

Таблица ниже иллюстрирует новые значения границ цветов и званий

По состоянию на 1-е октября 2015-го года, учитываются только активные пользователи (кто принимал участие в последние полгода).

О том как изменятся формулы рейтинга (да, они будут открытыми!) я напишу в ближайшее время.

Да! Совсем скоро на Codeforces будет внедрена пачка улучшений касательно рейтинга и цветов. Вторая революция цветов и званий уже близка!

В скором времени вас ждет новый рейтинг с открытыми формулами, новые границы цветов и еще некоторые сюрпризы.

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

В связи с планируемой сменой границ цветов у нас возникла неопределенность, как именно внедрить нововведение. Здесь есть две опции.

Опция первая: только вперед, не оглядываемся назад

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

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

Опция вторая: сохраним историю

При введении новых границ цветов оставим цвета как есть в старых ранклистах, постах и комментариях. Это не сломает комментарии в стиле "поздравляю с красным цветом!" (но так ли они ценны?) Такой подход сохранит достижение "стал красным", то есть такой пунктик в вашей биографии никуда не денется и останется подкреплен документально.

Вероятно, мы можем даже график порезать вертикально моментом будущей революции. Слева оставим старые цвета, а справа будет новая система цветных полосок. Однако это приведет к недопониманию, что же именно теперь на графике нарисовано у новичков, непрофессионалов и нечастых гостей Codeforces.

Итого

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

Пожалуйста, голосуйте только внимательно ознакомившись с опциями. Первые два комментария к посту будут соответствовать возможным опциям. Негативные голоса учитываться не будут, а положительные будут иметь веса 1-2-4-8-16-32 в зависимости от цвета (серый-зеленый-синий-фиолетовый-оранжевый-красный). Голосование секретное, результаты будут 1-го октября вечером.

UPD: Голосование завершено. Мы поздравляем первую опцию с убедительной победой! Она набрала 6394 баллов против 2320 баллов у второй опции. Комментарии для голосования удалены, чтобы не влиять на статистику голосов по комментариям. Ждите нововведений в ближайшее время!

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

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

Прием 1: "Вспомнить всё"

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

Прием 2: "От частного к общему"

Представьте, что вы нашли решение задачи (ура!) Рассмотрите какой-то частный случай задачи. К нему, конечно, может быть применен алгоритм решения задачи. Поэтому, чтобы решить общую задачу вам необходимо решить все ее частные случаи. Попробуйте решить какой-либо частный случай (или несколько) и потом попытайтесь обобщить их до решения основной задачи. Такие частные случаи можно рассматривать как упрощения задачи, то есть рассуждать по принципу: "если я не знаю как решать сложную задачу, попробую-ка я ее упростить и найти решения упрощенной версии".

Популярные примеры упрощений (частных случаев):

• вам сформулирована задача для дерева, рассмотрите ее вариант, когда дерево вырождается в путь;
• в задаче фигурируют веса? рассмотрите вариант, когда все веса равны единице, или произвольному числу или есть только два различных веса (и так далее).

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

Прием 3: "Смелая гипотеза"

Не стесняйтесь делать смелые гипотезы, которые вам кажутся правдоподобными. Далеко не всегда на контестах надо доказывать решения, развивайте внутреннюю интуицию. Сделав гипотезу, попробуйте ее доказать — возможно, это получится или даст понимание как её опровергнуть. Обязательно потестируйте гипотезу на широком наборе тестов, ведь будет очень обидно потратить время на реализацию решения на базе её и опровергнуть только после этого.

Примеры частых гипотез:

• ответ всегда существует;
• количество состояний небольшое.

Прием 4: "Чтобы решать задачу, ты должен думать как задача"

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

Прием 5: "Думаем вместе"

Этот прием применим только в командных контестах. Вдвоем или втроем начинайте по очереди озвучивать какие-то понятные факты про задачу. Например: "если n четное, то ответ всегда 0", "если n простое, то решать надо так" и так далее. Иногда ваши коллеги будут подхватывать идеи и развивать их, так можно и дожать идею решения задачи до конца.

Прием 6: "Подбери метод"

Попробуйте перебрать популярные алгоритмы или методы, которые хоть как-то могут оказаться применимы для задачи. Полезно посмотреть на ограничения по задаче. Зафиксировав метод, попробуйте подумать над решением предположив, что задача решается с применением этого метода. Надо рассуждать как-то так: "Пусть задача решается с помощью разделяй-и-властвуй. Тогда пусть мы рекурсивно решили задачу для левой и правой половине, осталось как-то объединить эти ответы, как бы это сделать..."

Прием 7: "Распечатать-посмотреть"

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

Иногда полезно выводить не только сам ответ, но и какую-то дополнительную информацию, например, способ получения ответа.

Прием 8: "Гуглим"

Этот прием можно применять, только если правила раунда/контеста это разрешают. Если задача на последовательности, то можно поискать ответы (см. прием 7) на сайте https://oeis.org/. Полезно понять формальную модель задачи и гуглить по правильным математическим терминам.

Вопрос к знатокам

А какие общеприменимые приемы используете вы?

Привет, Codeforces!

28 сентября 2015 года в 12:00 MSK состоится очередной раунд Codeforces #322 для участников из второго дивизиона. Традиционно, участники из первого дивизиона приглашаются поучаствовать в соревновании вне конкурса. Обратите внимание на необычное время начала раунда!

Этот раунд проводится по задачам школьного этапа Всероссийской олимпиады школьников по информатике 2015/2016 года г. Саратова. Задачи для вас готовил я и недавно вернувшийся из армии Эдвард Давтян (Edvard).

Хотелось бы сказать большое спасибо Максиму Ахмедову (Zlobober) за помощь в подготовке задач, Марии Беловой (Delinur) за перевод условий на английский, Михаилу Мирзаянову (MikeMirzayanov) за замечательные системы Codeforces и Polygon, а также Владимиру Петрову (vovuh) за прорешивание задач.

Участникам будет предложено шесть задач и два часа на их решение. Разбалловка будет объявлена позднее.

UPD Разбалловка задач 500-1000-1500-2000-3000-3000. Всем удачи!

UPD2 Разбор

UPD3 Поздравляем победителей!

1. Moe
2. for_the_pride
3. SakurakoujiRuna
4. VNOI
5. z123z123d