Topcoder Open schedule — http://tco18.topcoder.com/algorithm/schedule/

FIFA World Cup schedule — https://www.fifa.com/worldcup/matches/

Is it possible by any chance to move TCO Round 2B match to some other time? Two hours before or two hours after the game would be perfect.

I would also like to know opinion of the community on whether you consider World Cup opening game big enough event which supersedes other events, such as competitive programming matches.

Hi Codeforces.

I am interested if there's an exhaustive list of programming contests that have onsite finals. While there's a huge number of online contests nowadays, participation in most of them doesn't give any perks except T-shirts and (sometimes) money for top finishers. While onsite contest, even if it only rewards top finishers with the money, is a good reward itself and promotion to the onsite contest is a great motivation.

Of course, everybody is aware of such well-known contests with onsite finals as Topcoder Open, Facebook Hackercup, Google Code Jam. There're also some marathon contests such as Marathon24, Deadline24, Challenge24. But there're more contests than that — for example, Codechef Snackdown (started last year), VK Cup, CROC (only for Russian-speaking participants), Mindcoding (https://mindcoding.ro/).

Therefore I'm wondering if there're some other contests that I'm not aware of. If there's no such list, let's create one! What do you think about this idea?

UPDATE 20/08/2018. Прошло полтора года, а поиск по тэгам до сих пор не работает. Когда же его починят?

Поиск по тэгам сломан уже не первый день.

Примеры: http://mirror.codeforces.com/search?query=tco и http://mirror.codeforces.com/search?query=editorial

Почините, пожалуйста!

Всем привет!

Это agul и caustique, и мы стажеры Microsoft.

Все, наверное, слышали про Ice Bucket Challenge, и мы передаем эту эстафету на Codeforces.

Мы вызываем Petr, tourist и MikeMirzayanov! У вас есть 24 часа, чтобы повторить!

Good afternoon Codeforces!

It's been a while since last topic about football on Codeforces.

ACM ICPC world finals is about to start but what is more important FIFA World Cup has already started! So let's discuss your team preferences and results, make predictions and post funny photos and jokes about football here. I suggest to keep discussion in English so people from all the world can take part in it.

I will start off by posting picture of my national team. Hope we'll make it to play-off stage this year!

Уже не первый день не работают поиск по тэгам (ошибка "Страница временно заблокирована администратором") и "Архив" (ошибка "Codeforces временно недоступен").

Когда это планируют починить?

Ежегодно проводится сразу несколько крупных индивидуальных турниров по программированию с онсайтом, призами и серьезным спонсором. В завершающемся 2013 году такими можно назвать Facebook Hacker Cup, TopCoder Open, Google Code Jam, Russian Code Cup, Яндекс.Алгоритм, Чемпионат КРОК, ABBYY Cup, VK Cup (2012 год). То есть набралось минимум 8 турниров, в которых участвуют тысячи человек.

В то же время среди крупных командных турниров можно вспомнить только два — это чемпионат мира по программированию ACM ICPC и Открытый кубок. Но в обоих случаях есть ограничения — в ACM ICPC могут участвовать только студенческие команды (+ должны проходить по возрасту + лимит попыток + одна команда от вуза на финал), а Открытый кубок в основном популярен только в странах СНГ, да и денежных призов за победу в нем насколько я знаю не дают (по крайней мере, не анонсируют), ну и вдобавок проводится он на задачах разных локальных соревнований (в которых частенько бывают баги, переносы даты начала) и с очень гибким регламентом (недавно обсуждалось, что некоторым командам разрешают писать до или после основного потока, например).

Однако, глянув на таблицы популярных "Тренировок", можно заметить, что их писало очень много команд. То есть функция "Команды" на Codeforces очень даже востребована. На момент написания поста зарегистрировано 4798 команд. Даже если убрать все команды из одного человека, повторяющиеся, распавшиеся, наверняка можно будет набрать несколько сотен (скажем неточно, 100 — 500) команд для участия в турнире.

Было бы здорово организовать чемпионат, схожий с индивидуальными турнирами, только для участия команд, но оставив те же атрибуты — онсайт, футболки, спонсора, четкий регламент, систему раундов "на выбывание" и Codeforces в качестве площадки для соревнования. При этом преимуществом перед имеющимися командными турнирами будет то, что нет ограничения по возрасту, вузу, стране, часовому поясу. И я уверен, что красивый и современный интерфейс Codeforces (в сравнении с тем же ejudge и PCMS, на которых в основном проводятся командные турниры) привлечет множество людей поучаствовать в соревновании.

Сегодня, открыв этот разбор http://mirror.codeforces.com/blog/entry/10018, случайно увидел, что номер поста 10018.

Дай-ка, думаю, посмотрю, а какой пост стал юбилейным, 10000-ым! Каково же было мое разочарование, когда выяснилось, что такого поста нет — а точнее, он скрыт от меня. Что удалось найти, так это самый ранний пост перед 10000 — http://mirror.codeforces.com/blog/entry/9984 А после него — http://mirror.codeforces.com/blog/entry/10003

Получается, кто-то не поленился создать около 20 постов, ради того чтобы застолбить за собой пост номер 10000.

А ну-ка признавайся, кто ты, и верни нам праздник!

Всем привет!

В мире спортивного программирования существует одна разновидность необычных контестов — соревнование на самый короткий код. Я встречал такой официальный конкурс на сборах в Харькове и неофициальные на форумах ТопКодера или например в этой задаче.

Поскольку на Codeforces уже проводились Unknown Language Round, соревнование марафонского типа (как во время VK CUP Round 1, 2) и даже что-то похожее на промышленное программирование (конкурс с парсингом файлов в директории, который использовался при создании визарда для Тренировок), а также был популярен Russian AI Cup, думаю, что новое необычное соревнование будет интересно многим.

Давайте устроим соревнование на короткий код и посмотрим, кто сможет написать решение какой-нибудь длинной в реализации задачи лучше всех!

Кстати говоря, такое соревнование вполне себе имеет отношение к реальной жизни.

Сразу приведу пример — http://pastebin.com/hrSGFbPp Вы думаете, я взял этот кусок с сайта http://govnokod.ru/?

Ничего подобного — такое написал Google. Чтобы самим найти такой кусок кода на JavaScript, приведу пример для Google Chrome: откройте ваш любимый сайт, кликните в любом месте страницы правой кнопкой мыши, выберите "Просмотр кода элемента", в появившемся окне вкладку "Sources", дальше Ctrl+O и выберите файл с каким-нибудь непонятным названием. Там будет такой вот обфусцированный JavaScript.

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

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

Давайте сделаем из этого соревнование?

Сегодня ровно 2 года, как с нами нет Ferlon.

Для тех, кто не в танке — вот его последний пост 3 декабря 2011.

Наверное, все старожилы помнят лучший пост 2011 года, набравший 340 комментариев.

Ферлон сдержал обещание и удалился изо всех социальных сетей и не оставил и следа. Интересно, как сейчас он поживает и каким будет его следующий проект?

349A - Очередь в кино

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

Рассмотрим 3 различных случая.

• Если у посетителя 25 рублей, то сдачу ему давать не нужно.
• Если у посетителя 50 рублей, то мы должны дать ему 25 рублей сдачи.
• Если у посетителя 100 рублей, то мы должны дать ему 75 рублей сдачи. Это можно сделать двумя способами. 75=25+50 и 75=25+25+25. Заметим, что всегда выгодно попробовать сначала первый способ, а потом второй. Это верно потому, что купюры номиналом 25 рублей могут быть использован как для выдачи сдачи на 50 рублей, так и на 100 рублей, а сами купюры номиналом 50 рублей могут использоваться только для выдачи сдачи на 100 рублей.

Таким образом решение – поддерживать количество купюр номиналом 25 и 50 рублей и при выдаче сдачи на 100 рублей действовать жадно – сначала пробовать выдать 25+50 рублей, а иначе 25+25+25 рублей.

349B - Раскраска забора

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

Поскольку чем длиннее число, тем оно больше, нам выгодно написать число наибольшей длины. Для этого выберем цифру, на которую нужно меньше всего краски. Пусть количество краски для написания этой цифры d равно x, а всего у нас есть v литров краски. Тогда мы можем написать число длины .

Таким образом мы выяснили длину числа, пусть она равна len. Запишем промежуточный результат – строку длины len, состоящую из цифр d. У нас в запасе еще осталось v–len·x краски. Чтобы улучшить ответ, будем идти от начала числа и пробовать заменить каждую цифру на максимально возможную. Это верно потому, что числа одинаковой длины сравниваются сначала по старшим разрядам. Среди цифр больше текущей выбираем максимальную среди тех, на которую хватает краски, и обновляем текущее количество краски и ответ.

Если ответ длины 0, то нужно вывести -1.

348A - Мафия

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

Пусть ответ – это x игр. Заметим, что max(a₁, a₂, …, a_n) ≤ x. Тогда i-ый игрок может в x–a_i играх быть ведущим. Если просуммировать по всем игрокам, то получим — это количество игр, в которых игроки согласны быть ведущими. Это число должно быть не меньше x — нашего ответа.

Также следует не забыть требование, что max(a₁, a₂, …, a_n) ≤ x.

348B - Яблоня

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

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

Для каждой вершины посчитаем величину d_i — какое минимальное число (не ноль) в ней должно быть записано, чтобы дерево по-прежнему могло быть сбалансированным. Для листьев d_i = 1, для остальных вершин d_i равен k·lcm(d_j1, d_j2, ..., d_jk), где j₁, j₂, ..., j_k — сыновья вершины i. Также посчитаем величину s_i — сумму в поддереве вершины i. Все это можно сделать за один обход в глубину из корня дерева.

Вторым обходом в глубину мы можем посчитать для каждой вершины максимальное число, которое мы в нее можем записать, так чтобы удовлетворить ограничениям. А именно, пусть дана вершина i и k ее сыновей j₁, j₂, ..., j_k. Тогда если m = min(s_j1, s_j2, ..., s_jk), а — минимальное число, которое мы можем записать в сыновей вершины i, нам выгодно записать в сыновей вершины i числа . Остатки, а именно , добавим к ответу.

348C - Суммы подмножеств

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

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

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

Чтобы эффективно отвечать на запросы, для каждого множества (как легкого, так и тяжелого) посчитаем размеры его пересечения со всеми тяжелыми множествами. Это можно сделать за время и память . Для каждого тяжелого множества создадим булевский массив размера O(n), в i-ой ячейке которого будем хранить, сколько элементов i в этом множестве. Затем для каждого элемента и каждого тяжелого множества будем за O(1) проверять, содержится ли элемент в тяжелом множестве.

Теперь рассмотрим 4 возможных запроса:

• Добавление к легкому множеству. Пройдем по всем числам множества и к каждому добавим нужное значение. Дальше пройдем по всем тяжелым множествам и к каждому добавим (размер пересечения * значение в запросе). Время работы .

• Добавление к тяжелому множеству. Просто увеличим счетчик для данного тяжелого множества на значение в запросе. Время работы O(1).

• Ответ на запрос для легкого множества. Проходим по всем числам, добавляем значения к ответу. Затем проходим по всем тяжелым множествам и добавляем к ответу (добавление для данного тяжелого множества * размер пересечения со множеством в запросе). Время работы .

• Ответ на запрос для тяжелого множества. Берем уже посчитанный ответ, затем проходим по тяжелым множествам и добавляем (добавление для данного тяжелого множества * размер пересечения со множеством в запросе). Время работы .

Итого, если у нас O(n) запросов, то суммарное время работы .

348D - Черепашки

В задаче требовалось найти количество пар непересекающихся путей из левого верхнего в правый нижний угол таблицы. Для этого можно воспользоваться следующей леммой. Спасибо rng_58 за ссылку. А именно, если переформулировать применительно к нашему случаю, то лемма утверждает, что если есть множества начальных A = {a1, a2} и конечных B = {b1, b2} точек, то ответ можно посчитать, как следующий определитель:

Наконец, заметим, что для того, чтобы свести исходную задачу к этой, нам нужно сделать пути, которые не имеют совсем совпадающих точек — в исходной задаче разрешаются пересечения в первой и последней точках пути. Для этого в качестве множеств A и B мы можем взять точки A = {(0, 1), (1, 0)} и B = {(n - 2, m - 1), (n - 1, m - 2)}

348E - Пилигримы

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

Для каждой вершины найдем список наиболее удаленных вершин. Найдем вершины на пересечении путей от текущей вершины до каждой вершины из списка, в которых нет монастырей. Если мы удалим любую из этих вершин, то каждая вершина из списка будет недостижима из текущего монастыря. У каждой вершины из этого пересечения увеличим счетчик на единицу. Тогда ответ на задачу – максимум из счетчиков для всех вершин и количество таких максимумов.

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

Наконец, последний этап решения задачи – решить ее для случая, когда наиболее удаленная вершина или их список находятся необязательно в поддереве текущей вершины. Для решения этой подзадачи используем ту же идею, которая используется при нахождении максимального по длине пути в дереве. Для каждой вершины будем хранить 3 максимума – 3 наиболее удаленные вершины в ее поддереве. Когда мы спускаемся в какое-то поддерево, то передаем заодно и 2 оставшихся максимума. Таким образом, находясь в любой вершине, мы можем решить, существует ли путь не в поддереве (то есть уходящий наверх) такой же или большей длины. Если в поддереве и вне его пути одинаковой длины, то это означает, что для пилигрима из текущего монастыря всегда найдется хотя бы один путь, какой бы город не удалили. Если одна из величин больше, то мы выбираем нужный отрезок в эйлеровом обходе дерева и увеличиваем на нем значение на единицу. Случай, когда есть несколько путей (то есть хотя бы 2) вне поддерева одинаковой максимальной длины, обрабатывается аналогично такому же случаю в поддереве.

Поскольку дерево отрезков может отвечать на запрос за O(logN) времени, а задачу LCA можно эффективно решить методом двоичного подъема за то же время, то затраты времени и памяти равны O(NlogN).

Привет, Codeforces!

Сегодня, 27 сентября в 19:30 МСК, состоится Codeforces Round #202.

Идея раунда зародилась у меня и моих друзей, когда мы стажировались в Facebook этим летом. Возможно, у этого раунда рекордное для Codeforces количество авторов. Авторами задач стали Азизхан Алмахан azizkhan, Михаил Колупаев al13n, Филип Хласек fhlasek, Иван Мандура budabudimir и я, Игорь Демидов caustique.

В подготовке раунда нам помогали Максим Корыстов dark_ai, Александр Федулин Jughead, Ибрагим Исмаилов ibra, Владимир Чалышев cmd и Сергей Скляниченко Sklyack.

Идеи 2 задач мне подали Антон Ермилов ant.ermilov и Дмитрий Краснов navi-spb.

Тестировали раунд Алексей Сафронов yarrr и Алексей Шмелев ashmelev.

Также я хотел бы поблагодарить Геральда Агапова Gerald за помощь в подготовке контеста.

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

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

Желаю удачи и удовольствия от решения задач!

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

Div. 1

1. ilyakor
2. rng_58
3. EnumerativeCombinatorics
4. ftiasch
5. phtniit
6. SillyHook06
7. niyaznigmatul

Div. 2

1. zhk
2. love_kd
3. alex_k
4. arpit11293

Внимание! Появился разбор всех задач на обоих языках!

Всем привет!

Заранее извиняюсь, что топик никак не связан с олимпиадным программированием.

Недавно мой знакомый нашел такой онлайн-курс и я спешу поделиться этой новостью с вами.

http://www.cppgm.org/about.html

Для тех, кто не любит много читать, кратко содержание. Авторы онлайн-курса предлагают создать компилятор C++ своими руками. Платформа выбрана Linux x86_64, а стандарт языка — C++11. По мнению авторов, курс рассчитан на 12-18 месяцев. Общая суть такова — даются задания, их нужно выполнять и выставлять на peer review, если успешно, то дается доступ к следующему заданию.

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

Добрый день.

Судя по расписанию, Codeforces Round #167 запланирован на 13 февраля, 19:30 МСК. Но ведь в тот же день в 16:00 МСК состоится SRM на TopCoder. Два соревнования в один день — не слишком ли много? Кроме того, люди, которые по каким-то причинам не могут участвовать в среду, пропустят не одно довольно редкое соревнование, а сразу два. Может быть, стоит рассмотреть возможность переноса раунда на традиционную пятницу или воскресенье?

Добрый вечер!

Я подумал, что было бы неплохо собрать задачи прошлых лет в одном месте, чтобы можно было удобно их решать для подготовки к предстоящим раундам Facebook Hacker Cup 2013. Поэтому я создал тренировку, где Вы можете решить 9 задач из 1-3 раундов Facebook Hacker Cup 2012. Может быть, это первый и последний контест, где Вы увидите задачу с ограничением по времени 100 секунд, но не волнуйтесь — это случилось потому, что в задаче мультитест, поэтому на самом деле на каждый кейс приходится не больше 5 секунд.

Желаю Вам приятного времяпрепровождения! Удачи!

Добрый день!

Сегодня в 19:30 МСК в Тренировках состоится Новогодний контест. Приглашаю всех поучаствовать.

С наступающим!

Всем привет!

По многочисленным просьбам, у контестов в рамках тренировок СПбГУ теперь появились разборы. Разборы прикреплены рядом с условиями. Пока разборы есть только для самых популярных тренировок № 1, 7, 8 и последних тренировок № 17, 18 на строки и теорию игр. Со временем, разборы появятся у всех тренировок. Пример разбора можно посмотреть по ссылке. Пожалуйста, напишите, что вы хотели бы видеть в разборах кроме того, что там уже есть (информация об алгоритмах, ссылки на теорию и общая идея решения). Если вы хотите, чтобы срочно появился разбор какой-то определенной тренировки, также пишите в комментариях.

Всем привет!

Для тех, кто еще не в курсе. Я и Максим Корыстов (dark_ai) ведем кружок для питерских школьников и выкладываем все тренировки тут, на CodeForces. За 2 месяца уже накопилось 15 тренировок. Список тем широкий — теория графов, строки, структуры данных, блицы с задачами на разные темы. Задачи будут в первую очередь интересны участникам уровня второго дивизиона или всем тем, кто хочет посдавать задачи на стандартные алгоритмы. Приглашаю всех поучаствовать в наших тренировках. Это можно сделать и в режиме соревнования (почти все тренировки начинаются в 20:00 во вторник и в 18:00 в субботу).

Кроме того, сегодня появилась еще одна большая тренировка. Завтра многие пишут OpenCup днем, но тех, кому это соревнование кажется пока сложным, я приглашаю поучаствовать в суперблице. Все задачи стандартные и хорошо известные, они использовались ранее на студенческих тренировках СПбГУ (спасибо за подготовку задач Burunduk1, Burunduk2, KOTEHOK и другим), поэтому все сильные участники ничего не потеряют, а для новичков будет полезный опыт.

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

Все предложения по нашим тренировкам прошу писать в комментах к этому посту.

Добрый вечер!

В тренировках появились полуфиналы последних трех лет — NEERC 2009, 2010, 2011.

Кроме того, регулярно по вторникам и субботам вечером проходят тренировки для питерских школьников среднего уровня подготовки. Приглашаем всех желающих поучаствовать в контестах.

Сегодня начинается Чемпионат Европы по футболу.

Думаю, большинство пользователей CodeForces будут болеть на чемпионате за сборные России

и Украины

Давайте будем поддерживать наши команды вместе!

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

Чтобы всем было хорошо, не стоит создавать много тем, посвященных чемпионату, иначе Alex_KPR и его сторонники расстроятся.

Также объявляется конкурс на лучшую кричалку в поддержку сборных России и Украины. Победителю респект и +100500 ко вкладу!

В обсуждениях приветствуются картинки, видео красивых голов (и красивых болельщиц:)) и море эмоций!

Поехали!

UPD. Приглашаю всех поучаствовать в моем опросе и сделать прогноз на выступление сборной России на чемпионате.

Сегодня в 15:00 состоится SRM 544.

Сегодня в 21:00 мск состоится SRM 535. После матча тут по традиции можно обсудить задачи.

Я решил внести свою лепту и тоже написать про полуфинал.

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

Во время зарождения CodeForces была популярна тема рассказов о себе, о том, кто как попал в спортивное программирование. Вы уже наверняка читали рассказы Олега и Максима, а теперь я немного расскажу о себе.

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

Конечно, я не попал бы на полуфинал, если бы не многие часы подготовки, участие в контестах и поездки на сборы, за что отдельное спасибо нашему тренеру Андрею Лопатину aka KOTEHOK. На сборах я познакомился с ребятами из других городов и некоторых из них я уже успел встретить сегодня, а потому передаю отдельный привет и пожелания успешного выступления командам МАИ, Ярославля, Астрахани, Ижевска и Уфы.

Кроме того, отдельной строкой передаю привет в Барнаул и желаю успешного выступления команде Новосибирск 1, в составе которой выступает Кирилл Василевский aka Ferlon. Я узнал из его блога, что он очень долго шел к попаданию на финал ACM ICPC, и надеюсь, что в этом году его цель будет достигнута.

Завершая свой рассказ, я напоминаю вам, что наша команда называется СПбГУ 4 (caustique, KapJI, dark_ai).

Болейте завтра за красивую игру и пусть победит сильнейший!

Ага, ожидали стандартный шаблон "Здравствуйте, извините за очередную оффтопную тему...". Не тут-то было.