Hello Codeforces community!

Codeforces Round #318 (for both divisions) will take place on August, 29 at 19:30 MSK. It is the Thanks-Round devoted to Russian Code Cup. You will be given 5 problems and 2 hours to solve them. Scoring will be announced close to the round. I strongly recommend you to read all problems.

RussianCodeCup is the largest open programming competiton for Russian-speaking participants by Mail.Ru Group. Its history started in 2011. And since the first championship RCC offers great problems and generous prizes. This year finals will be held on September, 19th. Wish good luck to all the finalists! Thank you, RussianCodeCup, for your gift on the 5th anniversary of Codeforces!

I am honoured to be a problem setter for this round. I wouldn't do it alone. I want to thank Zlobober for his great help with problems preparation and MikeMirzayanov (and all people working on Codeforces and Polygon) for this awesome site. It's an amazing place to learn and compete. My big thanks to winger and AlexFetisov for their help with testing a round. And to Delinur for translating statements. As you see, not only a setter creates a round.

It's my first Codeforces round but not my first problems here. You can check out A, C and D from VK Cup 2015 — Round 2. Also you might remember some of my problems in TC rounds. I'm very happy with finally preparing a full round for Codeforces and I hope you will enjoy it. I tried my best to prepare nice and diverse problemset, you will judge it. In all problems you will have to help Limak who is quite unusual bear.

I wish you great fun and no frustrating bugs. Looking forward to seeing you!

UPD: Scoring is 500-1000- 1750 -2000-2500 in div1 and 500-1000-1500-2000- 2750 in div2. Enjoy a round!

UPD: Editorial

UPD: Contest is over. The winners:

Div1:

1. Marcin_smu
2. mnbvmar
3. subscriber
4. LoneFox
5. Shef

Div2:

1. cescmentation_folch (5 problems solved!)
2. fhxb520630 (5 problems solved!)
3. bugCollector
4. Sehnsucht
5. okaduki1

And note from an author. There were some wrong solutions passing. Sorry for that. I tried my best to create strong tests but I failed a bit. Did you like this round? What do you think about problems?

Thanks for participating!

Привет, Codeforces!

22 августа, в субботу, в 19:30 MSK состоится 317 раунд Codeforces.

Раунд подготовили для вас сотрудники компании AimFund: Kostroma, riadwaw, yarrr, gchebanov, ArtDitel, SirShokoladina и zeliboba.

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

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

В первом дивизионе будет разыграно 200 футболок c символикой нашей компании. Прочитать подробнее про нас и наши вакансии можно на сайте aimfund.ru и в анонсе этого раунда.

Этот раунд подготовлен в рамках программы "5 лет CodeForces", как часть нашего подарка сообществу. С этого раунда на CF начинается серия thanks-раундов, которые посвящаются людям и компаниям, пожертвовавшим значительные средства.

Всем удачи и высокого рейтинга!

P.S. Для участников петрозаводских сборов в четверг в 8 вечера будет организован фуршет в Пауланер Бройхаус.

P.P.S. Разбалловка: 1 дивизион 750-1250-1500-2000-2750, 2 дивизион 500-1000-1750-2250-2500

P.P.P.S. Топ-20 участников второго дивизиона также получат футболки.

Разбор

P.P.P.P.S. Друзья, с большим удовольствием сообщаем вам, что мы начинаем отправку наших фирменных футболок их счастливым обладателям по всему миру. Надеемся, что они вам понравятся, и вы будете носить их с удовольствием :)

Добрый день.

Закончилась летняя школа "Сазанка-2015", 13-го августа разъехались последние участники. Я надеюсь, что всем им понравились эти 10 дней на берегу Волги близ Саратова. Многие подходили, жали руку и говорили, что это так. Спасибо )

Пусть завидуют все те, кто не был с нами: за эти дни мы ударно и очень подробно прошлись по основным строковым алгоритмам, устроили чемпионат мира по ЧГК, ходили в сауну с уже классическими для этих сборов арбузами и мороженным, приняли участие в безумном Дне Нептуна. Еще были настолки, забеги в Волгу, песни под гитару и традиционные 20 килограмм шашлыка под занавес.

Но, конечно, главное — это была учебная программа. Мной были прочитаны четыре лекции, каждый день мы осчастливливали участников 5-ти часовыми контестами как тематическими, так и нет (один был 4-х часовым), а на разборах никто не засыпал. Спасибо моему напарнику по организации сборов Илье IlyaLos Лосю за подготовку контестов и проведение разборов.

GCJ will start in less than 24 hours.

Live Stream: https://www.youtube.com/watch?v=rh_EYIu7Ztc

Unfortunately I don't have time to edit this table, but rowdark will participate, and JoeyWheeler won't.

Participants:

Доброго всем времени суток!

13 августа 2015 года в 19:30 MSK состоится очередной раунд Codeforces #316 для участников из второго дивизиона. Традиционно, участники из первого дивизиона могут участвовать в соревновании вне конкурса.

Это мой первый Codeforces раунд. Надеюсь, он вам понравится.

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

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

UPD: Распределение баллов по задачам 500-1000-1500-2000-2500

Желаю всем участникам удачи!

UPD: Всем спасибо за участие!

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

Разбор

Всем доброго времени суток.

Скоро состоится Codeforces Round #315, авторами которого являются студенты УрФУ sivukhin и Um_nik. Это второй наш раунд, первый пришелся на черные дни Codeforces, и мы надеемся, что второй наш раунд не вызовет таких катаклизмов :)

Мы хотим поблагодарить команду Codeforces за эту замечательную платформу и Polygon. Особенно хотим отметить Zlobober за помощь в подготовке задач.

Желаем всем удачи!

UPD1:
Разбалловка.
div2 : 500-1000-1500-2250-2750
div1 : 500-1000-1500-2250-2500
Настоятельно рекомендуем прочитать условия всех задач. Мы постарались подготовить достаточно разнообразные задачи, вполне возможно, что сложные для нас задачи будут простыми для вас.

UPD2:
Разбор

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

div1:
1. KAN
2. Petr
3. enot110
4. tonyjjw
5. Konijntje

div2:
1. Lost
2. loser21
3. fyiwxp221
4. hqpwca
5. LazyWolfLin

Всем спасибо за участие.

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

5 августа 2015 года в 19:00 Мск состоится Codeforces Round #Pi для участников второго дивизиона. Участники первого дивизиона традиционно могут поучаствовать вне конкурса.

Это мой первый раунд на Codeforces. Надеюсь, что задачи вам понравятся и это даст мне стимул для подготовки новых раундов! Желаю всем быстрых Accepted и успешных взломов!

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

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

UPD: Разбалловка: 500-1000-1500-2000-2500-2500.

UPD: Разбор

Закончен VK Cup 2015. Я очень рад, что получился большой интересный Чемпионат с захватывающим Финалом. Такой драматической развязки и неожиданного хода соревнования я не видел очень давно.

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

Если вы понимаете о чем я, и:

• вы прошли в Раунд 3 чемпионата
• или имеете титул "Мастер" (оранжевый цвет) или выше,

то у вас есть замечательная возможность присоединиться к разработке самой большой соцсети Европы (и, ИМХО, лучшей в мире). Обратите внимание, что команда ВКонтакте целиком русскоязычная, а разработка ведется из Санкт-Петербурга.

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

Мы были вынуждены удалить регистрации, сделанные до 00:00, так как регистрационная форма на тот момент не поддерживала регистрацию команд. Пожалуйста, пройдите регистрацию вновь, если ваша регистрация была удалена.

Вчера завершился финал чемпионата VK Cup 2015, о котором вы могли прочитать в предыдущих наших постах. Осталось объявить последнее событие, связанное с прошедшим чемпионатом — онлайн-трансляцию, которая состоится в четверг 30 июля в 19:00 по Москве. К соревнованию допускаются как индивидуальные участники, так и команды из двух человек, которые желают почувствовать себя участниками финала соревнования. Трансляция продлится три часа, задачи будут перемешаны по сравнению с оригинальным порядком. Допускаются участники обоих дивизионом, но мы считаем своим долгом предупредить, что для участников из второго дивизиона набор задач, скорее всего, будет слишком сложным. Этот раунд является рейтинговым раундом Codeforces.

В заключение мы хотели бы поблагодарить всех людей, которые помогли чемпионату состояться. Придумывали и готовили задачи для вас сотрудники ВКонтакте, члены команды Codeforces и другие люди, любезно предложившие свою помощь: PavelKunyavskiy, burunduk3, Dmitry_Egorov, Kurpilyansky, dark_ai, MikeMirzayanov, Zlobober, MaximShipko, kuviman, Nickolas, Errichto, sankear и malcolm. Хочется сказать большое спасибо людям, прорешивавшим наши раунды, и дававшим ценные советы по поводу задач: winger и AlexFetisov. Также, мы благодарим всех работников ВКонтакте, с которыми вместе мы занимались проведением чемпионата: burunduk3, Burunduk2, KOTEHOK и многих других. Спасибо!

Всем удачи на онлайн-трансляции!

UPD: Обратите внимание, что во время раунда команде разрешается пользоваться только одним компьютером. Это значит, что программировать/пользоваться консолью/как-либо иначе продвигаться в решении задач в один момент времени можно только с одного компьютера. Единственное, что разрешается делать с двух компьютеров — это читать условия.

UPD2: Так как это командное соревнование, специально для вашего удобства мы выкладываем запароленный архив с pdf-условиями задач: vkcup2015-mirror-statements.zip. С началом тура мы опубликуем пароль к нему.

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

UPD4: По техническим причинам начало раунда переносится на 19:20 по Москве.

UPD5: Пароль на архив с условиями: vkcup4ever. Удачи!

UPD6: Онлайн-трансляция завершена! Поздравляем победителей:

1. rng_58
2. Zenith: I_love_Hoang_Yen, ngfam_kongu
3. OrOrZZZ!: zld3794955, KFDong
4. Petr team: Petr, ilyakor
5. jcvb_matthew99: matthew99, jcvb

Мой персональный респектам команде Petr team: Petr, ilyakor за единственное решение по задаче Е в трансляции, пользователю rng_58 и команде Excited: YuukaKazami, jqdai0815 за два правильных решения по задаче С.

Также, поздравляем пользователя rng_58, который продемонстрировал, что одиночному пользователю есть что противопоставить командам, состоящим из двух людей!

Рейтинг будет пересчитан в ближайшее время.

UPD7: Разбор!

Начался первый тур IOI2015

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

0:19 Кажется я наконец-то поборол проблемы с сетью, и попытаюсь начать рассказывать о происходящем. На тукущий момет есть баллы по самой простой задаче тура (boxes). Четыре сотни, и много раз по 10. 10 это что-то простое, не очень имеющее отношение к задаче. Первые 100 были за 13 минут у Alex_2oo8.
0:24 45.45 по второй задаче от Maestr0. По системе оценки задачи не особо понятно что это. (Да, балл по этой задаче не целый). 0:27 Несколько по 34 балла, по третьей. Это жадность без струтуры, на 100 нужно добавить какое-то двумерное дерево (условия уже на подходе)
0:31 Число сотен по boxes растет. Больше ничего особо интересного не происходит.
0:33 Первые баллы от российских участников. 100 по boxes от V--o_o--V
0:40 100 по scales от Žiga Željko. Хм. Сотни по двум задачам за 40 минут немного пугают.
0:52 Начали появляться массовые 45.45 и 55.55. Вероятно скоро на первом месте будет 100 55.55 34. А вот дальше начнется самое инетресное. Еще бы из российских ребят кто-нибудь что-нибудь сдал.
1:14 На текущий момент 23 человека полуичли хотя бы 100. Ничего интересного пока не происходит.
1:21 Судя по тому, когда сделаны сабмиты, всплывающие сейчас, очередь тестирования где-то 15 минут. Это как-то грустно.
1:24 У нас сменился лидер. IvL обогнал предыдущего лидера на 0.2 балла!
1:25 Тем временем, у LHiC 100 по boxes, у SpyCheese 71.42 по scales.
1:34 jasonyik выходит на 1 место, получив 100 45.45 34. Через небольшое время к нему присоединился AllCatsAreBeautiful 1:49 V--o_o--V получил 55.55 по scales, jasonyik 71.42 по scales и вышел на первое место. А у меня опять отвалился интернет.
1:50 У budalnik были 2 посылки на 0 по teams. Интересно что бы это значило. Видимо пишет решение больше, чем на 34.
1:53 34 по teams думаю еще долго надо будет ждать от всех 4-ех. Все не любят писать частичные решения в начале. 1:56 Еще одна посылка Коли на 0. Да что же такое. (А еще большое фи, авторам CMS, у которых не все посылки попадают в history)
2:01 SpyCheese сдал boxes на 50. Это решение за квадрат. вроде бы, сделать из него линию не очень сложно.
2:02 Takahiro Masuda сдал teams на 77. Это может быть либо лишний лог в решении, либо просто неоптимально написанное. 2:06 budalnik сдал teams на 34. Решил написать стресс-тест?
2:07 Takahiro Masuda досдал teams на 100. Это серьезная заявка. Тем временем открыты все задачи.
2:08 А SpyCheese сдал boxes на 70. Интересно что это. NlogN вместо линии?
2:14 SpyCheese досдал boxes.
2:15 А Белорусы, Украинцы и Казахи как-то кучкуются около 36 место. 7 подряд.
2:20 Пропала 100 по задаче scales. Кто-нибудь заметил еще проблемы? Интересно, массовое что-то или просто у этого человека что-то странное?
2:24 Барбара Кускова kuskova вырывается на четвертое место, получив 100 по boxes.
2:31 Прошла половина контеста. Через часик ребята начнут посылать частичные решения. Не очень приятно, для наблюдающих за ними.
2:34 Появилась 100 по scales у Hristo Venev. 0 100 34. Кажется для него делать что-то пободное типично.
2:37 budalnik послал scales на 0. Думаю скоро будет что-то более разумное.
2:38 bekzhan29 теперь делит 6 место с 100 55.55 34. 55.55 баллов за scales становятся популярны.
2:41 И снова смена лидера, теперь на первом месте Haghani с солидным отрывом в 43 балла.
2:45 LHiC получил 21 по teams. Это даже похоже на жадность без структуры.
2:46 А budalnik получил 10.35 по scales. Молодец.
2:47 Hristo Venev решил не отпускать Haghani слишком далеко, досдал boxes на 100 и теперь занимает второе место с отставанием в 14.42 балла. 100 100 34.
2:58 LHiC получил 100 по teams. Видимо дописал или добебагал структуру.
3:06 budalnik получили 10 по первой. Я все же надеюсь, что это 100 с багами.
3:09 Интересно, чем занимаются V--o_o--V и SpyCheese? Уже больше часа нет посылок.
3:17 На второе место выходит Nonthakit Chaiwong получив 45.45 по scales. Отставание от первого места меньше трех баллов, а 100 по teams это серьезная заявка на успех.
3:24 budalnik прошел только 3-ий subtask по boxes. Что, простите?
3:38 Как-то уже долго ничего не происходит.
3:45 Кажется опять образовалась очередь. Во всяком случае в табличке всплывают сабмиты 20-и минутной давности.
3:46 LHiC получил 71.42 и вышел на деленое первое место.
3:47 budalnik начал чтоли мерджить посылки по boxes??
3:48 LHiC получил 73.51 по scales. Это даже может быть залогом первого места на туре, но непонятно насколько даст приемущество в сумме. SpyCheese получил 21 по teams. По крайней мере, вероятно у него есть праивльная жадность.
3:50 V--o_o--V получил 71.42 по scales. А получить не 0 по teams?
3:52 Задача scales с переменным успехом выполняет свою роль по разнообразию количества баллов. Достаточно много участников набрали 71.42, 55.55, 45.45. А вот 73.51 набрали только SpyCheese и LHiC. Совпадение? Не думаю.
4:04 У SpyCheese 77 по teams, 34 по teams. А budalnik похоже мерджит boxes. Получил 45.
4:08 Кажется пока что, чтобы хорошо писать этот тур, в сборной России надо быть Мишей.
4:09 budalnik 38.78 по scales. Это уже даже похоже на бронзу!
4:37 Ничего не происходит, мы перемещаемся в место проведения соревнований.
4:46 LHiC 300 зпт умничка тчк
4:47 HYPERHYPERHYPERCUBELOVER 300.
4:52 jqdai0815 300. Кажется что мы все еще получаем сабмиты пятнадцати минутной давности.
11:39 местного времени: в таблице результатов пока что не появились посылки за последние 5 минут, но budalnik как и обещал принес еще 15 баллов на boxes.

Вкратце о задачах.
boxes. Есть 10^7 команд на круге размера 10^9. Надо каждой команде разнести по сувениру. Сдвиг на один в любую сторону занимает секунду. Все сувениры лежат в 0. Разнести все и вернуться в 0 за минимальное время.
scales. Есть 6 монет разного веса. Расположить их по возрастанию веса с помощью как можно меньше запросов "самая легкая/тяжелая/средняя монет из трех", а также "самая легкая из трех, которая тяжелее четвертой, или самая легкая, если таких нет".
teams. Есть N человек. У каждого есть ограничения с двух сторон на размер команды в которой он может участовать. Есть Q дней. В каждый день есть сколько-то задач, для которых нужны команды известного размера. Узнать в какие дни, можно сформировать комнады, а в какие нет.