Привет, Codeforces!

19 декабря 2015 года в 18:00 MSK состоится третий учебный раунд Educational Codeforces Round 3 для участников из первого и второго дивизионов. С прошлого учебного раунда прошло немало времени. В основном это связано с тем, что 6 декабря в Санкт-Петербурге состоялся NEERC и многие из вас (в том числе и я) в нём участвовали. Думаю дальше учебные раунды станут более частыми и регулярными.

<Эти два абзаца не менялись с прошлого раза>

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

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

</Эти два абзаца не менялись с прошлого раза>

Подготовкой задач в этот раз занимался не только я (Эдвард Давтян). Во-первых, большое спасибо Алексею Дергунову dalex, который поделился своей задачей, которую он раньше хотел дать на раунд, а она оказалась немного подбояненной. Во-вторых, хочу поблагодарить Александра Фролова fcspartakm RW, Виталия Кудасова kuviman АЁ и Артура Свечникова ikar за помощь в подготовке задач. Придумывать задачи нам помогал MikeMirzayanov. Также большое спасибо Маше Беловой Delinur, которая вычитывала мой RussianEnglish.

На сегодняшнем раунде вам будет предложено шесть задач. Надеюсь они вам понравятся.

Good luck and have fun!

UPD1: Первая часть соревнования завершена, надеюсь всем понравились задачи. Теперь можете ломать соперников :-)

UPD2: Разбор готов.

UPD3: Раунд закончился. Решения протестированы на дополненном наборе тестов. Результаты окончательные.

UPD4: 6725 rows affected :-)

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

Я рад вам сообщить, что в эти выходные пройдет шестнадцатая ВКОШП. В этом году олимпиада будет проходить на пяти площадках: в Санкт-Петербурге в здании Университета ИТМО, Барнауле, Алматы, Ташкенте и Тбилиси. Для участников завтрашний день начнется с регистрации, открытия и продолжится пробным туром.

Основной тур соревнования начнется в 10:00 в воскресенье 13 декабря.

Следите за текстовой трансляцией в твиттере NEERCNews от budalnik, qwerty787788 и subscriber.

Подписывайтесь на наше сообщество в ВКонтакте, там будет много интересной информации.

Смотрите видеотрансляцию от команды ICPCLive, которую будет вести Aksenov239. Во время трансляции к нам в студию придут много интересных людей.

Официальный хештег соревнований: #ВКОШП.

Также завтра состоится зеркало основного тура ВКОШП на платформе Яндекс.Контест. Ссылка появится позже, следите за обновлениями.

UPD: Ссылка на зеркало, начало зеркала в 11:00 по московскому времени.

Текущие результаты соревнования

Удачи участникам соревнования!
Пресс-служба NEERC

With many regionals around the world finished, I think it is time to start collecting teams that are going to World Final this year. Please help me adding information to the tables :)

Europe

Asia

Latin America

Africa & the Middle East

North America

South Pacific

Всем привет!

В среду 9 декабря в 19 MSK будет CF Round #335 (div 1 + div 2) по задачам, сделанным мной и dalex. Идёмте его играть!

Благодарим GlebsHP за помощь в подготовке задач, Delinur за перевод и MikeMirzayanov за сам Codeforces.

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

Всем полных решений и успешных взломов!

UPD. Поздравляем победителей Div. 2:

weiszago

Invisble

nezametdinov

И Div. 1:

jqdai0815

Um_nik

Egor

Разбор: blog/entry/22019.

Всех хочется поздравить с началом зимы.

В эти выходные в стенах Университета ИТМО в Санкт-Петербурге, а также в Барнауле, Ташкенте и Тбилиси пройдет двадцатый юбилейный полуфинал чемпионата мира по программированию ACM ICPC в Северо-восточном европейском регионе (NEERC).

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

На площадке в ИТМО участвует 102 команды, а завтра пройдет открытие и пробный тур продолжительностью 4 часа.

Подписывайтесь на страницу VK, твиттере и аккаунт в Instagram. Там можно будет найти фотографии и интересную информацию. Также у нас появился канал в Telegram, в котором мы хотим вести текстовую трансляцию NEERC 2015.

Если вы не участвуете в полуфинале, вы можете попробовать свои силы на задачах двадцатого NEERC в зеркале, которое пройдет 6 декабря в 11:00 по московскому времени, регистрируйтесь по ссылке.

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

Результаты можно будет найти по ссылке.

Официальный хештег соревнований: #NEERC.

Удачи всем участникам!
Пресс-служба NEERC

UPD: Если вы знаете еще команды, у которых в сумме хотя бы 7000 рейтинга на Codeforces, пишите в комментариях, я проверил только знакомые мне команды, кого-то мог и упустить.

UPD2: Видеотрансляция

Добрый день.

В режиме ранней беты мы запускаем новую фишку Codeforces, которая будет полезна многим активным пользователям сайта. Теперь вы можете создавать, управлять и использовать "списки пользователей".

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

У списка есть название и два относительно секретных ключа — один для его просмотра/использования, а второй для редактирования. Например, вот ключ для просмотра на список со студентами ЦОПП-СГУ на осень 2015-го года: 15c68c2cf878267d59373d1e56be8c9a

Это означает, что на некоторых страницах вы можете использовать дополнительный параметр ?list=ключ, чтобы применить список. Вот пример кусочка экрана по ссылке http://codeforces.com/problemset/page/3?list=15c68c2cf878267d59373d1e56be8c9a:

Ага, на ближайшую тренировку я могу дать задачи 538H - Летняя дихотомия и 538G - Осатаневший робот. Первое число обозначает количество решивших задачу, а второе — количество попытавшихся ее решить. Поиск в таких случаях производится не только по конкретно этой задаче, но по всем возможностям ее использования (сдал задачу в другом дивизионе или мэшапе — информация не потеряется!).

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

В настоящий момент списки можно применить:

• для просмотра архива (показывается дополнительно сколько решили/попробовали)
• для просмотра списка раундов/тренировок (показывается дополнительно сколько решили/попробовали)
• для просмотра результатов раунда (фильтруется списком)

Напоминаю, что функциональность пока в режиме ранней беты — возможны какие-то накладки. Исправим (но после полуфинала).

А в какие еще применения спискам пользователей можете предложить вы?

Consider a well-known problem: given a static array of size n, answer m queries of kind "how many numbers on [l, r] have value less than x". The standard solution is to build a segment tree where in every node we store a sorted vector. To answer a query we do a binary search in every corresponding node, achieving per query time complexity.

There is a method to reduce time complexity to per query, called fractional cascading. Instead of doing binary search in each node we do it only in the root, and then "push" its result to children in O(1).

For years I thought that the second approach is blazingly faster than the first one. And today I've made a test. I implemented both approaches in a pretty straightforward way and tested them on a random data. The results were quite surprising.

Fractional cascading: 760 ms

Top-down implementation: 670 ms

Bottom-up implementation: 520 ms

The first one is , others are ! Time is averaged over several consecutive runs. Test data is generated randomly with n = 100000, m = 200000.

Why doesn't fractional cascading give any improvements? Am I implementing it in an improper way? Anyway, this might be worth taking a look.

Howdy Codeforces!

Come join us for a trip to Bovinia with everyone’s favorite munchkin Kevin Sun (ksun48) and his sidekick Nicky Sun (nsun48)! Codeforces Round #334 (for both divisions) will be taking place on December 1st, at 6:35pm MSK. The problems were written by Alex Wei (yummy), Michael Kural (pi37), and myself, Yang Liu. As proud Americans, we’ve themed all of our statements around the most glorious cow (and its many uses in life).

We are immensely grateful to GlebsHP for his guidance and suggestions, without whom we would not have a balanced problem set. In addition, we would like to thank MikeMirzayanov for creating Codeforces and Polygon, as well as Delinur for translating our problem statements to Russian. Finally, we would like to give a huge shoutout to Daniel Chiu (waterfalls), Kevin Sun (ksun48), Nicky Sun (nsun48), Weihang (Frank) Fan (pobelter), Ray Li (abacadaea), and Girishvar Venkat (numbertheorist17) for testing our problems and providing feedback.

We wish you good luck and hope you enjoy our problems and cow jokes. (We’ve milked our brains quite thoroughly for puns.) Come hop on the next cattlebruiser for Bovinia!

(Per Codeforces tradition, we will announce the score distribution just before the contest.)

UPD 1: Some added thanks to AlexFetisov and winger for also testing our problems.

UPD 2: The scoring will be standard (500-1000-1500-2000-2500) for Div 2 and 500-1000-1500-2000-3000 for Div 1. Good luck and have fun!

UPD 3: System testing is done! Congrats to the winners.

Division 1:

1. subscriber
2. rng_58
3. Zlobober
4. ecnerwala
5. FreeMoneyCity

Division 2:

1. matipau
2. geniucos
3. quasisphere
4. emppu
5. tranquility

UPD 4: The editorial is posted here.

Hope everyone enjoyed the contest! Comments about problem quality, etc. are also appreciated.

Сейчас пишу статью на wiki — конспекты про битовые операции, трюки и прочую битовую магию. Если вы знаете полезные трюки с битами, которые применяются в алгоритмах, а также просто прикольные вещи, то делитесь своими трюками в комментариях. Также приветствуются извращённые решения известных задач. Например: обменять значения переменных, не использую третью переменную с помощью XOR.

Приветствуются комментарии в виде:

• Описание задачи
• Решение задачи в виде кода, по-возможности короткое объяснение для не очевидных трюков.

Пример идеального комментария:
Является ли число степенью двойки?

unsigned int v; // we want to see if v is a power of 2
bool f;         // the result goes here 

f = v && !(v & (v - 1))

Короткое объяснение: Пусть v — это степень двойки (в двоичном представлении 1 единица и k нулей справа), тогда v — 1 в двоичном представлении это число, состоящее из k единиц. Очевидно, что побитовое И чисел
v и v — 1 должно давать в результате 0.

Задача для затравки: Найти младший единичный бит за O(1)

• http://graphics.stanford.edu//bithacks.html
• http://www.gamedev.ru/code/tip/advfloat

Здравствуйте!

Botan Investment, компания Looksery и другие проекты Виктора Шабурова во многом строят разработку, привлекая в качестве инженеров участников олимпиад по программированию. Мы абсолютно уверены в ценности и востребованности всех тех навыков, которые получают участники таких соревнований. Именно поэтому мы разработали образовательную программу для развития спортивного программирования в региональных вузах РФ. Приглашаем преподавателей вузов присоединиться!