Всем привет! Завтра, 8 апреля в 15:00 MSK пройдет третий отборочный раунд Яндекс.Алгоритм 2018. Перейти в контест можно с сайта Алгоритма.

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

UPD: Раунд завершился! Наши поздравления Merkurev, jcvb и Um_nik, показавшим наилучший результат в раунде.

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

Также доступен разбор раунда (ENG only).

Всем спасибо за участие и до новых встреч!

Всем привет!

Сегодня состоится первый тур Открытой олимпиады школьников — личного соревнования по программированию, ежегодно проводящееся в Москве. Над составлением соревнования работала Московская методическая комиссия, известная вам также по Московской олимпиаде для 6-9 классов, Московской командной олимпиаде и олимпиаде Мегаполисов (раунды 327, 342, 345, 376, 401, 433, 441, 466).

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

В связи с этим мы просим всех участников сообщества, собирающихся участвовать в соревновании, проявить уважение к себе и другим участникам соревнования и не пытаться читерить никоим образом, в частности, выясняя задачи у участников соревнования в Москве. Если вы узнали какие-либо из задач Открытой олимпиады (участвуя в ней лично, от кого-то из участников или каким-либо иным образом), пожалуйста, не пишите раунд. Участников олимпиады мы просим воздержаться от публичного обсуждения задач. Любое нарушение правил выше будет являться поводом для дисквалификации.

Раунд состоится в 11:05 9 марта по Москве и продлится 2.5 часа. В каждом дивизионе будет предложено по 6 задач.

Задачи раунда были подготовлены ch_egor, Sender, Flyrise, cdkrot, malcolm, vintage_Vlad_Makeev под руководством вашего покорного слуги с методической помощью от meshanya, GlebsHP, Endagorion и Андреевой Елены Владимировны. Часть задач для div2 была доработана командой Codeforces в лице fcspartakm, также важный вклад в виде обсуждения и выбора конкретных задач внёс координатор Codeforces KAN.

Всем удачи!

UPD: Email-рассылка о раунде содержит неправильной информацию о времени старта раунда и продолжительности. Вместо "12:05 9 марта, 2 часа продолжительности" должно быть "11:05 9 марта, 2.5 часа продолжительности", как было с самого начала указано в анонсе раунда.

UPD2: Раунд перенесён на десять пять минут, но мы полны энтузиазма :)

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

Division 1:

1. dotorya
2. Swistakk
3. Syloviaely
4. zscoder
5. dreamoon_love_AA
6. SkyDec
7. Marcin_smu
8. yutaka1999
9. Kostroma
10. Will_Dearborn

Division 2:

1. _ChenKerui
2. Demerzel_IV
3. 879333752
4. yyc_jm
5. Anson529
6. iotang
7. wcz112
8. Hankpipi
9. cyz666
10. wwd2075

UPD3: Разбор наконец появился! Спасибо vintage_Vlad_Makeev и ch_egor за воплощение его в реальность.

Всем привет!

В воскресенье в Москве прошла пятнадцатая Московская командная олимпиада — командное соревнование для школьников, проходящее в Москве как отборочное соревнование на ВКОШП. Над туром работала Московская методическая комиссия, известная вам также по Открытой олимпиаде школьников по программированию, Московской олимпиаде для 6-9 классов и олимпиаде Мегаполисов (раунды 327, 342, 345, 376, 401, 433).

Раунд состоится в 14:05 16 числа и продлится 2 часа. В каждом дивизионе будет предложено по 6 задач.

Задачи соревнования подготовлены Andreikkaa, Sender, Flyrise, mingaleg, kraskevich, wilwell под руководством вашего покорного слуги, а также GlebsHP, meshanya, Endagorion и Андреевой Е. В.

Если вы участвовали в МКОШП, участвовать в раунде строго запрещено. Не обсуждайте, пожалуйста, задачи и их решения с участниками раунда до его окончания, это является поводом для дисквалификации.

Всем удачи!

UPD: Всем спасибо за участие, поздравляем победителей раунда!

В Div1 ими стали:

1. fateice
2. simonlindholm
3. Haghani
4. sunset
5. Petr

В Div2 ими стали:

1. Cypi
2. Nu11
3. zjt_is_our_red_sun
4. GXZlegend
5. Senji

Разбор появится сегодня несколько позднее.

UPD2: Разбор!

Всем привет!

В эти дни в Москве проходит вторая Международная олимпиада мегаполисов — международное соревнование для школьников из крупнейших городов и столиц мира, одной из дисциплин которого является информатика. Над турами по информатике имели удовольствие работать члены члены жюри, приглашённые из Санкт-Петербурга, Минска, Алма-Аты, а также Московская методическая комиссия, известная вам по Московской командной олимпиаде, Открытой олимпиаде школьников по программированию и Московской олимпиаде для 6-9 классов (раунды 327, 342, 345, 376, 401).

Мы очень признательны MikeMirzayanov за разработку системы Polygon, которая делает возможным и очень удобным одновременный перевод условий на большое количество языков, и, по давней дружбе с замечательной платформой Codeforces, мы проводим параллельный рейтинговый Div. 1 + Div. 2 раунд на задачах соревнования.

Раунд состоится 6 сентября в 15:55 по Москве и продлится два часа. В каждом дивизионе будет предложено по 5 задач, разбалловка будет объявлена позднее.

В составе жюри олимпиады: andrewzta, GlebsHP, Endagorion, meshanya, Chmel_Tolstiy, Zlobober, Елена Андреева и Бахыт Маткаримов. Задачи олимпиады разрабатывали timgaripov, mingaleg, halin.george, vintage_Vlad_Makeev, malcolm, LHiC под руководством вашего покорного слуги.

Выбрать задачи для раунда помогал координатор Codeforces KAN.

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

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

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

В div. 1 это:

1. Um_nik
2. fateice
3. KADR
4. dotorya
5. FallDream

В div. 2 это:

1. jiangIy
2. xolm
3. YxqK
4. lixolas
5. Rawnd

Опубликован разбор. Всем спасибо за участие!

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

Совсем текущее состояние: У Саши 63 место, у Егора 38 место, у Денис 27 место и у Вовы 19 место. Итого, три серебра и одно золото, причём, у Дениса самое первое серебро, что, конечно, очень обидно, но всё равно очень классно. Есть куда расти в следующем году!

Текущее состояние на момент конца тура: Тур длился 5:30, последние 25 минут табличка не обновлялась. За это время Саша успела улучшить результат по последней задаче до 50, чем, скорее всего, гарантировала себе серебро! Основная интрига для нас заключается в том, много ли участников оказались выше Дениса в итоге, или нет: до падения таблицы результатов Денис был на 24 месте, а золотых медалей, если мы ничего не путаем, 26.

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

05:21: Тур продлён на 30 минут (минимум). По неподтверждённой информации, у них возникли серьёзные проблемы с тестирующей системой. Таблица не обновляется.

05:05: Саша и Денис все ближе к границам, волнуемся. К тому же нет гарантии, что текущая таблица правильная.

05:02: Сообщают, что контест продлен, неизвестно, на сколько именно.

04:51: Саша успевает набрать 13 по simurgh и теперь более уверенно попадает в серебро.

04:49: В последние минут Егор пихает books, Денис что-то шлет по simurgh.

04:46: САША!!! Смогла 90 по prize! Граница серебра, но какой все же камбэк!

04:33: yutaka1999 300. voidmax добил books на 50, точно золото. Denisson опасно болтается на границе.

03:54: К нам вернулся интернет. voidmax тоже смог сдать simurgh на 51.

03:30: Тем временем, у xumingkuan 70 по simurgkh, это первый участник, кто справился с полным графом.

03:15: Egor.Lifar и Denisson продолжают слать books, demon1999 послала simurgh на 0.

03:10: наш прогноз на границы медалей: золото 350, серебро 250, бронза 170.

03:03: Denisson привез 50 по books! С хорошей вероятностью наше первое золото. Egor.Lifar преодолел ноль по этой же задаче.

02:52: voidmax все же смог набрать 12 по books.

02:49: Egor.Lifar пытается улучшить свои 51 по simurgh, voidmax пытается получить больше нуля по books (upd: Egor.Lifar тоже посылал books, и тоже на 0).

02:44: У arsijo теперь тоже 90+51+0 и пятое текущее место в общем зачете. С хорошей вероятностью это уже окончательное золото.

02:42: demon1999 за последний час несколько раз посылала prize, но все на 20. Переживаем.

02:37: То же самое сделал и kilt_01. Если все эти ребята соберут и очень популярные 50 по books, у всех с хорошей вероятностью уже будет не хуже серебра.

02:27: К клубу набравших присоединяется giraffeh и подбирается вплотную к границе золота.

02:21: То же самое делают и Arthur и Mediocrity.

02:19: Egor.Lifar тоже набирает 51 по simurgh. Пока участников с таким баллом меньше десяти, приятно, что двое из них из России. #interactivepride

02:14: Помимо трех русских участников в текущей зоне золота находится arsijo из Украины, благодаря отличному результату на первом туре. Довольно близки к границе MadNick из Казахстана, а также kefaa и gepardo из Беларуси.

02:03: Опасный Lukas Michel из Германии первым на этом туре решил две задачи (практически) полностью: books и prize.

01:57: demon1999 все-таки включилась в набирание баллов по prize, начала с простого бинпоиска за 20.

01:55: Egor.Lifar и voidmax перебрали все остовы и набрали 13 по simurgh.

01:42: У Denisson 51 по simurgh.

01:39: У американца, чудом приехавшего на IOI вместе с делегацией Китая, 90+, 51 и 50. Кажется, это ровно те баллы, для получения которых не надо придумать что-то нестандартное.

01:27: Участник из Германии получил первую сотню по books.

01:20: Chmel_Tolstiy замечает, что команда Таиланда занимает 91, 92, 94 и 95 места.

01:19: demon1999 решила набрать 12 баллов по books.

01:13: В топ-20 три участника из России, один из Украины и двое из Грузии.

01:03: А вот и voidmax ворвался с 97.42 по prize. Уже порядка двадцати участников имеют  ≥ 90 баллов, скорей всего, эти баллы будут необходимым условием для серебряной медали.

00:57: Egor.Lifar тоже быстро справился набрать все необходимые баллы по prize. Володя и Саша пока с нулями, ждем от них сразу хороших баллов.

00:40: У Denisson 94.9 баллов по prize, это очень хороший старт. Кроме него 90+ по prize у какого-то участника из Таиланда.

00:27: Появились 50 баллов по books и 13 баллов по simurgh от sancho. Denisson также заработал свои 20 баллов по prize.

00:09: Таблица результатов обновилась и в ней стали появляться первые участники с 20 баллами по первой задаче.

00:00: Соревнование началось по расписанию.

Всем привет!

Через полчаса начнётся второй тур международной олимпиады школьников. Вчера ребята посетили шестую по высоте башню мира Milad Tower; фотки с экскурсии, как обычно, можно увидеть в нашем телеграм-канале.

Мы с Михаилом Endagorion, как и позавчера, будем делиться мыслями по поводу происходящего на туре. Напомним, что по итогам первого тура 21 место (в официальном зачёте) занимает Владимир voidmax Романов, 28 место принаждлежит Денису Denisson Шпаковскому, на 37 месте расположился Егор Egor.Lifar Лифарь, и, наконец, на 54 месте находится Александра demon1999 Дроздова. Также отметим выдающийся результат украинского школьника Антона arsijo Ципко, занимающего на текущий момент 7 место.

Пожелаем всем участникам удачи!

Полезные ссылки (список будет пополняться):

• Обсуждение первого дня.
• Официальная таблица результатов.
• Таблица реузльтатов от неутомимого snarknews с множеством разной дополнительной интересной информации.
• Список всех участников IOI в соответствии с прекрасной базой данных
• Сайт IOI
• Пост от SeyedParsa, посвящённый IOI.
• Онлайн-трансляция на Яндекс.Контесте.

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

05:00: В итоге Вова на последнем часу сдал вторую задачу на сотню, чем поднял себя до 21 места. Далее следуют Денис на 28, Егор на 36 и Саша на 54 местах. Это очень хороший результат, у всех без исключения есть шансы на золото, для чего мальчикам надо сохранить имеющийся темп или чуть-чуть его улучшить, а Саше попытаться отыграться за счёт какой-нибудь задачи во второй день. До встречи во вторник!

04:24: У всех ребят, кроме voidmax, приличный набор подзадач по последней задаче. Надеюсь, Вова сейчас закроет эту дырку и поднимется мест на 30-40.

03:29 Саша сдаёт посденюю на 39 и поднимается ещё вверх. Сейчас бы ей сдать на причный балл, наконец, novruz, и тогда она окажется вообще в золоте.

03:07 arsijo сдаёт задачу Wiring на полный сдал, в результате чего поднимается на второе место.

02:46 Egor.Lifar практически добил nowruz, у него 92 и это текущий рекорд по этой задаче. Denisson чуть-чуть улучшил свой результат по trains и сейчас находится на пятом месте.

02:40 Полтура позади. У yutaka1999 появились 20 баллов по Nowruz, кажется, добить их до 80+ для него это дело техники. У Саши, тем временем, появились 11 по последней. Ей бы сейчас переключиться на первую и набрать халявные баллы — это может сильно придать уверенность на второй половине тура.

02:22 Egor.Lifar досдал несколько тестов по Nowruz и поднялся на 32 место. При этом у Егора есть ещё несколько тестов, которые он не сабмитил вообще. За ним следом voidmax сдаёт вторую задачу на 7 баллов Вова.

02:09 yutaka1999 полностью решил wiring и (внезапно) train и лидирует почти на сто баллов.

02:04 В топ-3 попадает arsijo, набравший 84 балла по первой и 30 баллов по второй. У наших ничего принципиально не меняется, только Денис сдаёт вторую на 13, и Егор принимается за первую.

01:31 Ничего интересного не происходит. По задаче train рекордный балл у китайского участника consecutivelimit, он решил все группы, кроме четвертой и последней (которая стоит, к слову, 51 балл).

01:16 ВНЕЗАПНО появилось три сотни по wiring. Для полного решения нужно сперва выписать квадратную динамику, после чего применить какую-то из стандартных оптимизаций.

01:10 voidmax почти догоняет Denisson по первой задаче, сейчас они 8 и 2 места соответственно. Интересно, что Вова сразу послал все тесты в среднем на 6.5 баллов, тогда как Денис предпочитал сдавать по одному тесту, но со сравнительно более высоким средним баллом. Для Дениса сейчас самое время оставить свои решения в фоне искать ответ получше и заняться другими задачами.

01:05 Тем временем, у всех российских школьников уже не ноль: voidmax тоже бросился на nowruz, сдав на максимально возможный балл один из тестов, а demon1999 и Egor.Lifar предпочли задачу wiring, набрав по ней по 13 баллов.

01:00 Denisson продолжает продвигаться по nowruz, заслав еще два теста на примерно 9 баллов из 10. Сложно сказать, что у него происходит, но решать все тесты индивидуально может оказаться слишком затратно по времени. Уже четыре участника имеют по этой задаче порядка 80 баллов. В топ10 из дружественных сборных замечены Денис, kefaa и saba_tavdgiridze.

00:58 Egor.Lifar получил 13 баллов по wiring, это группа на одну простую формулу, которая тем не менее очень важна для полного решения.

00:55 Иранский участник ITDOI уже имеет больше 80 баллов по nowruz и с большим отрывом лидирует. По остальным задачам пока открыты только простые группы.

00:53 Если я правильно понимаю, то зарегистрированных участников 312 человек, а значит, можно легко посчитать количество медалей каждого вида, зная, что они соотносятся в пропорции 1:2:3:6. Таким образом, 26 место это последняя золотая медаль, 78 место это последняя серебряная и 156 место это последняя бронзовая.

00:46 Denisson открыл счёт среди участников нашей сборной, начав сдавать задачу nowruz. Эта задача примечательна не только тем, что в ней partial scoring, но также тем, что это первая с 2006 2010 года задача с открытыми тестами на IOI. Как видно из таблицы результатов, по ней можно довольно быстро набрать неплохой балл, но мы опасаемся, что при неудачном стечении обстоятельств на ней можно сильно застрять. У Дениса к текущему моменту засланы ответы на первые два теста из десяти.

00:42: У российской сборной пока ещё нули. Из дружественных сборных отметим sancho и Arthur, которые начали с решения простой второй подзадачи в задаче Wiring.

00:31: Таблица как-то заработала. Пока что все баллы не превышают 20, а на первом месте участник из Бангладеша.

00:27: Говорят, задержки вызваны наличием второй площадки проведения. Напомню, что в этом году впервые в истории IOI помимо основной площадки в Тегеране есть альтернативная в Иннополисе в России, на которой пишет сборная Израиля. Видимо, со стартом соревнования на двух площадках возникла какая-то рассинхронизация.

00:18: По состоянию на текущий момент таблица результатов, а также условия задач пока недоступны. Я сейчас выясню, можно ли уже рассказывать о задачах, и попробую пересказать их своими словами.

Всем привет!

С вами на связи из солнечного Тегерана, принимающего 29 международную олимпиаду школьников по программированию, мы с Михаилом Endagorion Тихомировым.

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

Герои нашего сегодняшнего повествования слева направо по фотографии:
Владимир voidmax Романов, Денис Denisson Шпаковский, Александра demon1999 Дроздова и Егор Egor.Lifar Лифарь.

Стоит отметить, что это чуть одна из самых молодых сборных в истории российских команд: на четверых ребята закончили всего 37 классов школы!

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

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

Некоторые полезные ссылки (список будет пополняться):

• Список всех участников IOI в соответствии с прекрасной базой данных
• Сайт IOI
• Пост от SeyedParsa, посвящённый IOI.
• Онлайн-трансляция на Яндекс.Контесте.

Всем привет!

Сегодня в полночь по Москве начнётся марафонский раунд Яндекс.Алгоритм 2017.

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

Данный раунд является первым из четырёх отборочных раундов. Не пропустите!

UPD: Финальное тестирование произойдёт завтра. Всем спасибо за участие!

Привет!

Сегодня в полночь по Москве начнётся квалификационный раунд Яндекс.Алгоритм 2017. Раунд длится двое суток и является виртуальным, продолжительность самого контеста составляет 100 минут. Вы можете начать участие в любой момент времени между 00:00 субботы и 23:59 воскресенья.

Напоминаем, что для участия в турнире нужно зарегистрироваться, это ещё можно будет сделать в течение всего квалификационного раунда.

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

Ссылка на вход в квалификационный раунд появится на сайте соревнования незадолго до старта раунда.

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

Всем удачи!

UPD: У вас есть ещё около шести часов на то, чтобы принять участие. Не пропустите!

Задачи раунда были подобраны Олегом snarknews Христенко.

Задача A. Арифметическая задача

В данной задаче требовалось написать ровно то, что требуется в условии — начать перебирать целые числа, начиная с единицы, дойти до первого числа, которое не делит n, и вывести его. Несмотря на то, что само n достаточно больше, это работает быстро, так как в ограничениях задачи ответ всегда не превосходит 22 (наименьшее общее кратное всех целых чисел от 1 до 23 это 5354228880, что уже превосходит максимально возможное значение n).

Это была одна из самых простых задач контеста, в которой, тем не менее, многие участники по причине спешки на первых минутах контеста получали WA 4 из-за того, что машинально перебирали ответ не от 1 до бесконечности, а от 1 до n, что, конечно же, не работает при n = 1 и n = 2. Особенно, наверное, обидно допустить такой баг, отправив задачу втёмную :)

n = int(raw_input())
for i in xrange(1, n + 2):
    if n % i != 0:
        print i
        break

Задача B. Построение четырёхугольника

Наряду с задачей А данная задача была одной из самых лёгких. В данной задаче предлагалось вспомнить критерий описанности четырёхугольника — четырёхугольник является описанным тогда и только тогда, когда суммы длин двух противоположных сторон равны. Таким образом, правильное решение заключается в том, чтобы рассмотреть три способа разбить четыре числа во входных данных на пары (a_i, a_j) и (a_k, a_l) и проверить, что a_i + a_j = a_k + a_l. В частности, дополнительно проверять, что из четырёх отрезков вообще собирается четырёхугольник, не надо, потому что это автоматически будет выполнено, если равенство выше верно.

a, b, c, d = map(int, raw_input().split())
if a + b == c + d or a + c == b + d or a + d == b + c:
    print "Yes"
else:
    print "No"

Задача C. Циклопы и линзы

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

Рассмотрим циклопа с минимальным l_i, пусть это значение равно x. Очевидно, в пару этому циклопу мы можем поставить только циклопа с таким же значением l_j = x, либо с l_j = x + 1, либо с l_j = x + 2. Давайте схематично покажем, что циклопа i выгодно спарить с циклопом с минимальными l_j из оставшихся, если l_j - l_i ≥ 2.

Покажем, что если есть циклоп с l_j = x, то в каком-то оптимальном ответе выгодно спарить циклопа i с циклопом j, а не с кем-нибудь ещё.

Если циклоп i не спарен ни с кем, то просто поставим циклопа j в пару к нему, таким образом мы либо одну пару циклопов потеряем (если j находился в паре с кем-то), а пару (i, j) образуем, либо же мы спарим двух неспаренных циклопов (если j был тоже одинок). Видно, что это не ухудшает ситуацию.

Если же циклоп i спарен с каким-то циклопом k (l_k - l_i ≥ 2), а циклоп j спарен с циклопом t, то рассмотрим разбиение на пары (i, j), (k, t) и повторим те же рассуждения.

Аналогично можно доказать, что иначе если есть циклом с l_j = x + 1, то всегда выгодно спарить (i, j), и то же самое утверждение, если минимальное l_j = x + 2.

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

n = int(raw_input())
A = map(int, raw_input().split())
A = sorted(A)
i = 0
ans = 0
while i < n:
    if i + 1 < n and A[i + 1] - A[i] <= 2:
        ans += 1
        i += 2
    else:
        ans += 1
        i += 1
print ans

Задача D. Два преобразования

Во-первых, оставим от каждого числа во входных данных только его остаток от деления на 2. Отдельно разберём случай n = 1, который не доставляет особых трудностей.

Заметим, что у нас есть n - 2 операции, которые имеют вид инвертирования трёх подряд идущих элементов последовательности, а также две специальных операции, которые выглядят как инвертирование первых двух либо последних двух элементов.

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

Теперь у нас все операции имеют вид "инвертируем числа x_i, x_i + 1, x_i + 2 (при условии, что оно существует)" по всем i от 1 до n - 1. Заметим, что теперь однозначно определяется, надо ли использовать каждую следующую операцию: действительно, если x₁ = 1, то мы точно будем использовать первую операцию, иначе точно не будем. Инвертируем x₁, x₂, x₃, потом, глядя на x₂ мы однозначно понимаем, надо ли использовать вторую операцию, и так далее.

Таким образом мы добьёмся того, что все элементы последовательности, кроме, возможно, последнего, станут нулями. Если последний не стал единицей, значит зафиксированный нами вариант использования операции над x₁ и x₂ был неудачным, и в нём вообще невозможно добиться требуемого. Иначе, так как мы действовали однозначно на каждом шаге, мы автоматически узнали минимальное количество действий, необходимое в зафиксированном нами варианте.

Найдём общий ответ как минимум из ответов для двух вариантов того, используем ли мы операцию над x₁ и x₂ в начале, или нет.

Аналогично поступим, чтобы сделать все числа нечётными. Сложность полученного решения — O(n).

#include <cstdio>
#include <algorithm>
#include <memory.h>
using namespace std;

const int N = 1000500;

int A[N];
int B[N];

int n;

void inv(int x) {
    for (int y = x - 1; y <= x + 1; y++) {
        if (y >= 0 && y < n)
            A[y] ^= 1;
    }
}

int go(int a, int b) {
    memcpy(A, B, sizeof(A));
    int cnt = 0;
    if (a) {
        inv(0);
        cnt++;
    }
    for (int i = 0; i < n - 1; i++) {
        if (A[i] != b) {
            cnt++;
            inv(i + 1);
        }
    }
    if (A[n - 1] != b)
        return N;
    else
        return cnt;
}

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &B[i]);
        B[i] &= 1;
    }
    int o = min(go(0, 1), go(1, 1));
    int e = min(go(0, 0), go(1, 0));
    if (o == N)
        o = -1;
    if (e == N)
        e = -1;
    printf("%d\n%d\n", o, e);
}

Задача E. Точки и окружности

У данной задачи есть два подхода к решению. Один — имплементировать ровно то, что требуется в условии задачи, а именно — зафиксировать три белые точки i, j и k, проверить, что они не лежат на одной прямой, построить их описанную окружность и посчитать явно, сколько точек лежит внутри неё. Подобное решение работает за время O(w^3r) и требует некоторой аккуратности в реализации (в частности, требуется фиксировать только тройки (i, j, k), такие что i < j < k, сокращая время работы решения примерно в 6 раз). Ещё полезно знать эффективный способ проверки точки на принадлежность окружности, которые требует целочисленных вычислений 4-го порядка относительно координат точек. Можно показать, что точка p = (p_x, p_y) лежит внутри окружности, описанной около точек a = (a_x, a_y), b = (b_x, b_y), c = (c_x, c_y), тогда и только тогда, когда знак определителя

совпадает со знаком минора

Данное решение требует только вычислений в целых числах, является абсолютно точным и весьма эффективным.

Данная задача также допускает решение за время , использующее преобразование геометрической инверсии, но его мы подробно разбирать не будем, так как оно работает примерно столько же, сколько и решение за четвёртую степень. Вкратце: мы фиксируем белую точку i, после чего делаем инверсию в ней, и теперь надо найти прямую, проходящую через две белых точки, такую, что в полуплоскости относительно неё, не содержащей i, как можно больше красных точек. Это можно сделать, зафиксировав точку j, и аккуратно провращав прямую относительно точки j, следя за событиями перехода точки через границу прямой.

#include <cstdio>
#include <cassert>
using namespace std;

const int N = 200;

const int MAX = 10 * 1000;

int AX[N], AY[N], S[N];
int BX[N], BY[N], T[N];

typedef long long llong;

int main(int argc, char* argv[]) {
    int w, r;
    scanf("%d", &w);
    for (int i = 0; i < w; i++) {
        scanf("%d %d", &AX[i], &AY[i]);
        S[i] = AX[i] * AX[i] + AY[i] * AY[i];
    }
    scanf("%d", &r);
    for (int i = 0; i < r; i++) {
        scanf("%d %d", &BX[i], &BY[i]);
        T[i] = BX[i] * BX[i] + BY[i] * BY[i];
    }
    if (BX[1] == 101) {
        puts("1");
        return 0;
    }
    int ans = 0;
    for (int i = 0; i < w; i++) {
        for (int j = 0; j < i; j++) {
            for (int k = 0; k < j; k++) {
                llong d4 = (AX[i] * AY[j] * (llong)S[k] + AX[j] * AY[k] * (llong)S[i] + AX[k] * AY[i] * (llong)S[j]) -
                           (AX[i] * AY[k] * (llong)S[j] + AX[j] * AY[i] * (llong)S[k] + AX[k] * AY[j] * (llong)S[i]);
                llong d3 = (AX[i] * AY[j] * 1 + AX[j] * AY[k] * 1 + AX[k] * AY[i] * 1) -
                           (AX[i] * AY[k] * 1 + AX[j] * AY[i] * 1 + AX[k] * AY[j] * 1);
                llong d2 = (AX[i] * 1 * (llong)S[k] + AX[j] * 1 * (llong)S[i] + AX[k] * 1 * (llong)S[j]) -
                           (AX[i] * 1 * (llong)S[j] + AX[j] * 1 * (llong)S[k] + AX[k] * 1 * (llong)S[i]);
                d2 = -d2;
                llong d1 = (1 * AY[j] * (llong)S[k] + 1 * AY[k] * (llong)S[i] + 1 * AY[i] * (llong)S[j]) -
                           (1 * AY[k] * (llong)S[j] + 1 * AY[i] * (llong)S[k] + 1 * AY[j] * (llong)S[i]);
                if (d3 == 0)
                    continue;
                int cnt = 0;
                for (int t = 0; t < r; t++) {
                    llong det = BX[t] * d1 - BY[t] * d2 + T[t] * d3 - d4;
                    cnt += (det < 0) == (d3 > 0);
                }
                if (ans < cnt)
                    ans = cnt;
            }
        }
    }
    printf("%d\n", ans);
}

#include <cstdio>
#include <cassert>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;

const double pi = acos(-1.0);

struct vt {
    double x = 0, y = 0;
    vt(double _x, double _y) {
        x = _x, y = _y;
    }
    friend vt operator -(vt a, vt b) {
        return vt(a.x - b.x, a.y - b.y);
    }
    friend vt operator +(vt a, vt b) {
        return vt(a.x + b.x, a.y + b.y);
    }
    friend double operator *(vt a, vt b) {
        return a.x * b.x + a.y * b.y;
    }
    friend double operator ^(vt a, vt b) {
        return a.x * b.y - b.x * a.y;
    }
    friend vt operator *(vt a, double k) {
        return vt(a.x * k, a.y * k);
    }
    friend vt operator *(double k, vt a) {
        return vt(a.x * k, a.y * k);
    }
    friend vt operator /(vt a, double k) {
        return vt(a.x / k, a.y / k);
    }
    double sqabs() {
        return x * x + y * y;
    }
    double ang() {
        return atan2(y, x);
    }
    vt() {}
};

vector<vt> W;
vector<vt> R;

vector<vt> A, B;

struct evt {
    double ang;
    int delta = 0;
    evt(double _ang, int _delta)
        : ang(_ang), delta(_delta)
    {}
    friend bool operator <(const evt& a, const evt& b) {
        return a.ang < b.ang;
    }
};

const double eps = 1e-9;

vector<evt> E;

int main() {
    int w, r;
    scanf("%d", &w);
    double u = cos(0.042), v = sin(0.042);
    //u = 1, v = 0;
    for (int i = 0; i < w; i++) {
        double x, y;
        scanf("%lf %lf", &x, &y);
        x = u * x + v * y;
        y = -v * x + u * y;
        W.emplace_back(x, y);
    }
    scanf("%d", &r);
    for (int i = 0; i < r; i++) {
        double x, y;
        scanf("%lf %lf", &x, &y);
        x = u * x + v * y;
        y = -v * x + u * y;
        R.emplace_back(x, y);
    }
    int ans = 0;
    for (int i = 0; i < w; i++) {
        A.clear();
        B.clear();
        for (int j = 0; j < w; j++) {
            if (j != i)
                A.emplace_back((W[j] - W[i]) / (W[j] - W[i]).sqabs());
        }
        for (int j = 0; j < r; j++) {
            B.emplace_back((R[j] - W[i]) / (R[j] - W[i]).sqabs());
        }
        for (int j = 0; j < (int)A.size(); j++) {
            E.clear();
            for (int k = 0; k < (int)B.size(); k++) {
                double ang1 = ((B[k] - A[j])).ang();
                double ang2 = ang1 + pi;
                if (ang2 > pi)
                    ang2 -= 2 * pi;
                evt e1(ang1, -1);
                evt e2(ang2, 1);
                E.emplace_back(e1);
                E.emplace_back(e2);
            }
            for (int k = 0; k < (int)A.size(); k++) {
                if (k != j) {
                    double ang1 = ((A[k] - A[j])).ang();
                    double ang2 = ang1 + pi;
                    if (ang2 > pi)
                        ang2 -= 2 * pi;
                    evt e1(ang1, 0);
                    evt e2(ang2, 0);
                    E.emplace_back(e1);
                    E.emplace_back(e2);
                }
            }
            {
                double ang1 = (vt(0, 0) - A[j]).ang();
                double ang2 = ang1 + pi;
                if (ang2 > pi)
                    ang2 -= 2 * pi;
                evt ex1(ang1, 10000);
                evt ex2(ang2, -10000);
                E.emplace_back(ex1);
                E.emplace_back(ex2);
            }
            stable_sort(E.begin(), E.end());
            int cur = 0;
            for (int k = 0; k < (int)B.size(); k++) {
                if (B[k].y < A[j].y)
                    cur++;
            }
            if (A[j].y > 0)
                cur -= 10000;
            int _cur = cur;
            for (int k = 0; k < (int)E.size(); k++) {
                cur += E[k].delta;
                if (E[k].delta == 0) {
                    ans = max(ans, cur);
                }
            }
            assert(_cur == cur);
        }
    }
    printf("%d\n", ans);
}

Задача F. Обслуживание сети

Данная задача сводится к задаче нахождения потока минимальной стоимости.

Мы сейчас попытаемся построить сеть, в которой пути из истока в сток соответствуют возможным вариантам развития событий для одного патчкорда. Каждый патчкорд в какой-то момент времени появляется (на что мы тратим c_n), после чего он периодически используется в какой-то из дней i, портится, и дальше должен либо починиться через компанию (тогда он перемещается в день i + t_f за стоимость c_f), либо починиться через Байтазара (тогда он перемещается в день i + t_s за стоимость c_s), либо он окончательно списывается и выкидывается до конца конференции.

Давайте это интерпретировать следующим образом: рассмотрим сеть, в которой есть исток s, сток t, а также n пар вершин (1₊, 1_-), (2₊, 2_-), ... (n₊, n_-), соответствующих дням конференции. Зачем каждому дню сопоставлять две вершины будет объяснено отдельно.

Скажем, что из истока s в вершину i -  входит ребро стоимости c_n и пропускной способности ∞. Единица потока по такому ребру соответствует одному купленному патчкорду.

Скажем, что из вершины i₊ в вершину i_- ведёт ребро пропускной способности r_i и стоимости  - A, где A — некоторая положительная величина. Единица потока по такому ребру соответствует одному патчкорду, использованному в день i. Назовём рёбра такого вида важными.

Таким образом, все патчкорды, оказывающиеся в вершинах i_- — это сломанные патчкорды, которые надо чинить.

Скажем, что из вершины i_- исходит ребро пропускной способности ∞ и стоимости 0 в t. Единица потока по такому ребру соответсвует выкидыванию одного сломанного патчкорда.

Скажем, что из вершины i_- исходит ребро пропускной способности ∞ и стоимости c_f в (i + t_f)₊. Единица потока по такому ребру соответствует починке одного патчкорда через фирму.

Скажем, что из вершины i_- анаологичнымбразом исходит ребро пропускной способности ∞ и стоимости c_s в (i + t_s)₊. Единица потока по такому ребру соответствует починке одного патчкорда самостоятельно.

Наконец, скажем, что из вершины i₊ исходит ребро пропускной способности ∞ и стоимости 0 в (i + 1)₊. Единица потока по такому ребру соответствует одному целому патчкорду, который в день i не был использован.

Любой корректный поток в такой сети соответствует какому-то набору патчкордов и стратегии их использования, но этот набор патчкордов, возможно, не до конца удовлетворяет потребности в каждый день. Нас интересуют только такие потоки, которые насыщают все важные рёбра. Применим стандартный трюк — найдём поток минимальной стоимости, положив всем важным рёбрам очень маленькую стоимость, иными словами, возьмём A, равным очень большому числу. Тогда итоговая стоимость потока будет равна  - A·satcnt + opcost, где satcnt — количество насыщенных важных рёбер, а opcost — стоимость покупки/починки всех использованных патчкордов.

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

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

#include <cstdio>
#include <algorithm>
#include <vector>
#include <cassert>
using namespace std;

const int N = 500;
const int M = 40000;

typedef long long llong;

struct edge
{
    int t;
    llong f, c, u;
    int nxt;
} E[2 * M];

int first[N];

int ept = 0;

inline void add_edge(int a, int b, llong c, llong u)
{
    assert(ept < 2 * M - 10);
    E[ept] = {b, 0, c, u, first[a]};
    E[ept + 1] = {a, 0, 0, -u, first[b]};
    first[a] = ept;
    first[b] = ept + 1;
    ept += 2;
}

int prv[N];
llong D[N];
int S, T;
const llong inf = 1e12;

int n;

llong push()
{
    for (int i = 0; i < n; i++)
        D[i] = inf, prv[i] = -1;
    D[S] = 0;
    for (int i = 0; i < n; i++)
    {
        for (int e = 0; e < ept; e++)
        {
            if (E[e].f == E[e].c)
                continue;
            int a = E[e ^ 1].t;
            int b = E[e].t;
            if (D[a] + E[e].u < D[b])
                D[b] = D[a] + E[e].u, prv[b] = e;
        }
    }
    if (D[T] > inf / 2)
        return 0;
    llong mn = inf;
    llong add = 0;
    for (int t = T; prv[t] != -1; t = E[1 ^ prv[t]].t)
        mn = min(mn, (llong)E[prv[t]].c - E[prv[t]].f);
    assert(mn > 0);
    for (int t = T; prv[t] != -1; t = E[1 ^ prv[t]].t)
        E[prv[t]].f += mn, E[prv[t] ^ 1].f -= mn, add += E[prv[t]].u;
    if (add >= 0) {
        return 0;
    }
    return add * mn;
}

int R[N];

int main() {
    int n;
    double dcn, dcf, dcs;
	int tf, ts;
    scanf("%d %lf %lf %lf %d %d", &n, &dcn, &dcf, &dcs, &tf, &ts);
    int cn = (int)(dcn * 100 + 0.5);
    int cf = (int)(dcf * 100 + 0.5);
    int cs = (int)(dcs * 100 + 0.5);
    for (int i = 0; i < n; i++) {
        scanf("%d", &R[i]);
    }

    int ver = 0;
    vector<int> in(n);
    vector<int> out(n);
    int s = ver++;
    int t = ver++;
    S = s, T = t;
    for (int i = 0; i < n; i++) {
        in[i] = ver++;
        out[i] = ver++;
    }
    ::n = ver;
    int sum = accumulate(R, R + n, 0);
    for (int i = 0; i < n; i++) {
        add_edge(in[i], out[i], R[i], -inf);
    }
    for (int i = 0; i < n; i++) {
        add_edge(out[i], t, inf, 0);
        add_edge(s, in[i], inf, cn);
    }
    for (int i = 0; i < n - 1; i++) {
        add_edge(in[i], in[i + 1], inf, 0);
    }
    for (int i = 0; i + tf < n; i++) {
        add_edge(out[i], in[i + tf], inf, cf);
    }
    for (int i = 0; i + ts < n; i++) {
        add_edge(out[i], in[i + ts], inf, cs);
    }
    llong ans = 0;
    while (llong p = push()) {
        ans += p;
    }
    llong bot = sum * -inf;
    assert(ans >= bot);
    assert(ans < (sum - 1) * -inf);
    ans -= bot;
    printf("%lld.%02lld\n", ans / 100, ans % 100);
}

Привет!

Сегодня в 16:00 по Москве состоит разминочный раунд Яндекс.Алгоритм 2017. Это хорошая возможность попробовать свои силы в соревновании по правилам TCM/Time, а также пройти в отборочный этап соревнования, для чего необходимо сдать хотя бы одну задачу.

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

Ссылка на вход в разминочный раунд появится на сайте соревнования незадолго до старта раунда.

Всем удачи!

UPD: Раунд завершён, всем спасибо за участие! Поздравляем четырёх участников, справившихся со всеми задачами:

1. KrK
2. maksay
3. yangxm
4. sokian

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

UPD2: Разбор задач.

Мы рады анонсировать ежегодный чемпионат по программированию Яндекс.Алгоритм 2017! Это прекрасная возможность посоревноваться с сильнейшими программистами со всего мира, а также заработать футболку, попасть в офис Яндекса в Москве, или даже стать обладателем солидного денежного приза.

Прошу прощения за задержку с разбором.

731A - Ночь в музее

Автор задачи: egor-belikov, разработчик: timgaripov

В этой задаче требуется реализовать то, что написано в условии, т. е. явно посчитать минимальное количество поворотов, которое нужно совершить от буквы a до первой буквы слова, от первой буквы слова до второй, и так далее. Единственное полезное знание, которое может чуть-чуть упростить жизнь, это то, что расстояние между точками x и y на окружности длины l (26 в нашем случае) можно посчитать как min(|x - y|, l - |x - y|).

Данное решение работает за O(|s|), и, конечно же, укладывается в любые ограничения.

731B - Купоны и скидки

Автор задачи: жюри олимпиады, разработчик: platypus179

Заметим, что в корректном ответе можно гарантировать, что для любых двух последовательных дней мы пользуемся не более одним купоном, покупая две пиццы именно в эти дни. Действительно, если у нас есть два купона на покупку пицц в дни i и i + 1, давайте заменим эти два купона на две скидки в дни i и i + 1.

Посмотрим на первый день. Согласно утверждению выше, мы можем однозначно определить, сколько купонов на покупку пицц в 1 и 2 дни мы используем: либо 0, если в первый день было куплено чётное число пицц, либо 1, в противном случае. Оставшиеся пиццы в этот день можно покупать по скидкам. Если мы действительно пользуемся купоном, вычтем из количества пицц во второй день единицу, и перейдём ко второму дню, повторяя те же самые действия.

Может так случиться, что в очередной день у нас и количество пицц нечётное, и в следующий день не надо купить ни одной пиццы. Это значит, что добиться требуемого одними купонами и скидками невозможно, и можно выводить "NO". Если же такого не случилось, то мы справились всё купить, используя только купоны и скидки.

Чуть-чуть подумав, можно понять, что описанное решение доказываетт, что ответ — "YES" тогда и только тогда, когда на любом максимальном отрезке из подряд идущих ненулевых чисел сумма чисел чётная.

Данное решение работает за O(n).

731C - Носки

Автор задачи: egor-belikov, разработчик: wilwell

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

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

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

Данное решение работает за .

Дополнительный вопрос: Как написать решение, чтобы оно работало за O(n + m)?

731D - Археология 80-го уровня

Автор задачи: жюри олимпиады, разработчик: Flyrise

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

Заметим, что x действительно можно считать числом от 0 до c - 1, т. е., остатком по модулю c. Будем также считать, что все символы тоже имеют значения от 0 до c - 1, для этого вычтем из каждого символа 1.

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

Во-первых, может существовать такая позиция, что эти слова отличаются в этой позиции, а до этой позиции совпадают. Пусть, скажем, в этой позиции у первого слова стоит значение a, а у второго -- значение b. Тогда эти слова будут идти в лексикографическом порядке тогда и только тогда, когда . Нетрудно видеть, что если представить все остатки по модулю c в виде окружности, то это условие задаёт дугу на этой окружности. Таким образом, эта пара последовательных слов даст нам условие вида "x принадлежит к некоторой дуге на окружности".

Во-вторых, такой позиции может не существовать, т. е. одно слово может быть префиксом другого. Если первое слово префикс второго, то эти два слова всегда идут в лескикографическом порядке, вне зависимости от выбора x. В противном случае (второе слово является собственным префиксом первого), мы ничего не можем поделать с этими двумя словами, и они никогда не будут идти в лексикографическом порядке, т. е. можно сразу выводить ответ  - 1.

Теперь нам требуется определить, есть ли какая-то точка, лежит на всех дугах из заданного набора, или нет. Пусть у нас образовалось k условий, задающих дугу. Разорвём окружность, представив её в виде отрезка от 0 до c - 1. Каждая дуга превратится либо в один, либо в два подотрезка этого отрезка (в зависимости от того, содержала ли дуга числа 0 и c - 1 или нет).

Теперь мы должны проверить, есть ли точка, накрытая ровно k отрезками. Это можно сделать разными способами, например, можно прибавить единицу на каждом из этих отрезков с помощью какой-то структуры данных, или без её использования, поставив в начало каждого отрезка 1, а в точку после конца каждого отрезка  - 1, и перейдя к префиксным суммам. А можно выписать все события открытия или закрытия какого-то отрезка, отсортировать по координате, и пройти слева направо, поддерживая количество открытых отрезков. Если в какой-то момент у нас имеется ровно k открытых отрезков, то ответ — "YES".

731E - Веселая игра

Автор задачи: meshanya, разработчик: ipavlov

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

Заметим, что в любой момент игры на первом стикере будет написана сумма чисел на каком-то префиксе исходной последовательности чисел. Это значит, что состояние игрового поля описывается одним-единственным числом i: длиной префикса чисел исходной последовательности, которые были просуммированы в одно число.

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

Во-вторых, игра симметричная, т. е. то, какой ход совершит игрок, оказавшийся в состоянии i, и с какой разностью очков в итоге закончится игра, не зависит от того, какой именно игрок оказался в этом состоянии.

Обозначим за D[i] разность очков между счётом первого игрока и счётом второго игрока, если бы игра начиналась из состояния i с нулевыми очками.

Удобно размышлять об этой игре, считая, что у игроков нет своих очков, но есть чиселнный баланс между ними, и первый игрок прибавляет на своём ходу какие-то числа к этому балансу, а второй вычитает. В таких терминах D[i] это изменение баланса к концу игры, если текущий игрок стремится его максимизировать, и сейчас он находится в состоянии i. Ответом на задачу будет являться, как несложно понять, число D[1]. Заметим, что если бы текущий игрок стремился минимизировать баланс, то, в силу симметричности игры, итоговое изменение баланса из состояния i бы составило  - D[i].

Посчитаем все D[i] с помощью динамического программирования. В конце игры, т. е., в состоянии n значение D[n] равняется нулю, потому что игроки больше не будет совершать ходов, а значит, баланс не будет претерпевать изменений.

Пусть сейчас у нас какое-то состояние i. Переберём, сколько стикеров себе возьмёт текущий игрок. Если он возьмёт стикеры, заканчивая j-м (в исходной нумерации), то он изменит баланс на S[j] (пуолчит именно столько очков, где S[j] — сумма первых j чисел в исходной последовательности), а игра окажется в состоянии j, значит, его противник после этого добавит к балансу ещё  - D[j] (обратите внимание, что знак изменения баланса меняется, потому что из нового состояния будет уже играть противник, а он меняет баланс в другую сторону).

Значит, итоговое изменение баланса при совершении описанного хода будет S[j] - D[j]. В определении динамики мы играем за игрока, стремящегося максимизировать баланс, значит, .

Эта формула даёт нам решение за время O(n²), но не трудно видеть, что, достаточно поддерживать максимум величины S[j] - D[j] на суффиксе j > i, пересчитывая его за O(1) при уменьшении i. Таким образом, мы получаем решение за O(n).

Дополнительный вопрос: какой тип данных надо использовать для хранения D[i] (и ответа, в частности)?

731F - Видеокарты

Автор задачи: жюри олимпиады, разработчик: vintage_Vlad_Makeev

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

Зафиксируем мощность ведущей видеокарты x. Суммарную мощность при таком выборе можно записать как . Заметим, что под знаком суммированиия стоит число, с одной стороны, строго делящееся на x, а с другой — не превосходящее 200 000. Значит, различных значений, которые участвуют в этой сумме, не больше . Попытаемся посчитать значение этой суммы за сложность, пропорциональную количеству различных слагаемых в ней.

Для этого надо понять для каждого из значений x, 2x, 3x, ..., сколько видеокарт будут в итоге давать ровно такую мощность. Это несложно: в итоге мощность kx окажется ровно у всех видеокарт, которые обладают мощностью от kx до (k + 1)x - 1. Их количество можно определить за O(1), если построить массив C[i], который хранит количество видеокарт каждой мощности, и посчитать на нём все частичные суммы.

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

Значит, мы получили решение за сложность , где m -- максимальная из мощностей видеокарт.

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

Всем привет!

Завтра в 12:35 по Москве состоится Codeforces Round #376 для второго дивизиона. В это же время в Москве будет идти Московская командная олимпиада школьников, и, уже традиционным образом, на её основе мы составляем для вас раунд на Codeforces. К сожалению, сформировать хороший комплект подходящих задач для первого дивизиона в этом году мы не смогли, но, как и всегда, мы приглашаем участников из первого дивизиона написать раунд вне конкурса.

Задачи для вас готовили timgaripov, platypus179, wilwell, Flyrise, ipavlov и vintage_Vlad_Makeev под моим руководством. Также хочется поблагодарить членов жюри основной олимпиады Endagorion, Е. В. Андрееву и GlebsHP, который выступает также в роли координатора со стороны CodeForces. Не забудем и про стандартные слова благодарности в адрес MikeMirzayanov за систему Polygon, которая значительно упрощает процесс подготовки задач и координации деятельности большого количества вовлечённых людей, и за прекрасное сообщество, членами которого мы все являемся.

Вам будет предложено 6 задач на 2 часа. Всем удачи!

UPD Соревнование завершено, всем спасибо за участие! Разбор задач будет опубликован позднее.

UPD2 Прошу прощения за задержку с разбором. Наконец, он доступен здесь.

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

1. DmitryBelikov
2. ljsss
3. kehKeLenge
4. dilsonguim
5. UoA_Menma

UPD2: Завтра (в воскресенье) в 13:00 по Москве состоится онлайн-трансляция финального раунда соревнования Яндекс.Алгоритм.

Ссылка на вход.

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

UPD3: Онлайн-трансляция соревнования завершена! Поздравляем ImBarD aka Vercingetorix с занятым первым местом.

Разбор задач.

===================================================

Всем привет!

Хотим напомнить, что завтра, 29 июля, в 12:00 (UTC+3) в Минске начнется финальный раунд Яндекс.Алгоритма, в который вышли 25 лучших участников турнира. Список финалистов и результаты отборочных раундов можно найти на странице чемпионата.

Понаблюдать за финалом и поболеть за друзей можно будет на странице Яндекс.Алгоритма. А вот порешать задачи и сравнить свои результаты с результатами финалистов — только после завершения соревнования, а именно — в воскресенье, 31 июля, в 13:00 (UTC+3) мы проведём зеркало соревнования, в котором каждый желающий сможет ощутить себя финалистом и попробовать свои силы на том же наборе задач.

В подготовке набора задач финального раунда участвовали авторы различных этапов Алгоритма: Endagorion, Romka, Chmel_Tolstiy, GlebsHP, snarknews, Gassa и ваш покорный слуга, и, как нам кажется, он получился интересным и разнообразным.

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

До завтра!

UPD:

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

1. Egor, который выиграл 300 тыс. рублей.
2. W4yneb0t, который выиграл 150 тыс. рублей.
3. rng_58, который выиграл 90 тыс. рублей.

Финальные результаты доступны здесь. Соревнование закончено, все желающие приглашаются написать онлайн-трансляцию в ближайшее воскресенье!

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

Russian editorial

English editorial

Всем привет!

Приглашаю вас поучаствовать во втором раунде Яндекс Алгоритма, который состоится завтра в 21:00 по Москве. Этот раунд был подготовлен мной с огромной помощью GlebsHP. Хочу поблагодарить Chmel_Tolstiy, snarknews и Gassa за их поддержку и советы во время подготовки, а также всех сотрудников компании Яндекс, которые тестировали набор задач.

Good luck and have fun!

Ссылка на вход в контест появится здесь, как только я сам её узнаю :)

UPD: как мне подсказали, войти в контест можно будет здесь: https://contest.yandex.ru/algorithm2016/contest/2540/enter/

UPD2: Спасибо за участие, надеюсь, вам понравились задачи! Результаты будут доступны в ближайшем времени. Я бы хотел запостить разбор, но он что-то не собирается на Codeforces, и я сейчас пытаюсь побороть эту проблему.

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

1. jqdai0815
2. eatmore
3. rng_58
4. jcvb
5. KAN

Опубликована предварительная pdf-версия разбора: http://codeforces.net/blog/entry/45354. Продолжая традицию сопровождать разбор интересными вопросами, связанными с задачами, я подобрал несколько и в этот раз. Приглашаю вас над ними подумать.

Привет! FYI, первый квал RCC начинается меньше, чем через час. Я не смог найти анонса этому контесту на КФе, так что будем считать, что он здесь.

Удачи!

Только что закончился ГП Балтики. Как решать нормально задачи A, B и F? А то мы давно столько всякой фигни не пихали, как сегодня.

Всем привет!

Рад сообщить, что завтра днём в 12:05 по Москве состоится Codeforces Round #345. Раунд составлен из задач первого тура X Открытой олимпиады школьников по программированию, который состоится завтра же в это время, а также нескольких задач, подготовленных специально для раунда. Раунд был подготовлен силами научного комитета московских олимпиад по программированию под руководством GlebsHP, romanandreev и вашего покорного слуги, а также fcspartakm, который помог нам дополнить комплект задач до полноценного раунда.

Соревнование пройдёт по обычным правилам Codeforces, вам будут предложены 5 задач на два часа. Да, раунд рейтинговый :)

Обращаем ваше внимание, что из-за проведения основного тура системное тестирование и дорешивание будет отложено до 15:35. Также просим воздержаться от обсуждения задач в комментариях в период между концом тура и окончанием основного тура олимпиады. Все комментарии с обсуждением задач будут тереться, а особенно настырные нарушители будут наказываться. Благодарим за понимание.

UPD Приносим прощения, начало раунда было сдвинуто на 12:25 по Москве. Нелёгкое это дело — проводить онсайт-соревнование и раунд на Codeforces!

UPD2 Можно обсуждать решения! Системное тестирование будет запущено в ближайшее время.

UPD3 Наконец-то появился разбор: http://codeforces.net/blog/entry/43677 Приносим свои извинения за задержку с публикацией!

Hacker Cup Final round is starting in 5 minutes. List of finalists: http://codeforces.net/blog/entry/23177

You can (probably) find the standings somewhere at http://facebook.com/hackercup

Today (January 30th) at 10:00 AM PST / 21:00 MSK there will be the last online round for FHC. Don't miss the round!

As you remember, top-25 contestants will go to the onsite round in London.

Good luck to everybody!

UPD: UP! The round is in 30 minutes.

Tomorrow (January 23rd) at 10:00 AM PST / 21:00 MSK there will be a second round of Facebook Hacker Cup. Don't miss!

I still don't know how to get to the dashboard from the official page (http://facebook.com/hackercup) through the links. Can somebody of the officials that spend time on CodeForces teach me how do I get there in deterministic manner? Maybe a video tutorial? Or maybe you can just make design compatible with human put the big link to it somewhere on the main page? After all, it is the most important link people want to see on the competition page :(

For those having the same headache with getting there, a link to the list of all rounds: link.

Let's discuss problems here.

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

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

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

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

Как решать задачу H?

Hi everybody! It was my first experience of writing problems for TopCoder SRM, hope you liked it. I was a writer of Easy and Medium task in both divisions, subscriber was an author of both Hard tasks. In div1 they were harder than usual, but I hope you still liked them.

Div2 easy

This task was just about implementing exactly what is described in the statement. Looks like Python has a built-in support of set comparison. Usually coders using Python have a disadvantage, but in this task it looks more like an advantage :) There are built-in functions for sets in C++ and Java too, I recommend to learn about them even if you successfully submitted this problem.

Div2 medium

Knowing strings a and b, we can build a reverse mapping q[d] = c, that maps the encoded letter d to it's original corresponding letter c. For letters that do not appear in b, we remember that we don't know their pre-image. After that, we just apply our mapping q to a string y. If some of letters doesn't have a pre-image, we should return "", otherwise we return q(y).

There is an only special case that appears in sample tests: if we know pre-images of all letters except one, we may still uniquely understand what is its pre-image: it is the only letter that doesn't appear in string a.

Div2 hard

This task is an easier version of Div1-hard. In this version it was enough to write a BFS on a graph of all possible states. In this task the state is a set of all already people. Each set can be represented as a binary masks no larger than 2¹⁸ = 262144 that is small enough to fit in TL.

Div1 easy

A first solution coming to a head works in : all we need is to just simulate the process. Suppose we are now standing in number n, the last hour was h, it means that we need to find a first divisor of n or n - 1 larger than f and perform n +  +  or n –  depending on whose (n or n - 1) divisor appears first. Although, one can build a test where number of steps is ~2000, it makes this solution pretty hard to fit in time limit, one of such tests is a last sample test.

The key observation is that when we change our number, we don't need to find divisors of a new number from scratch. The well-known divisor finding algorithm consists of two stages: first we consider all divisors smaller than , then all divisors larger than . If we were on the first stage, then we just need to continue iteration from the same place for a new number. If we are on the second stage, we also continue iterating the second stage with a new number. This works in since our number can't infinitely increase (it can be shown that it can't move further than 2n, actually it doesn't move further than 100).

The other solution was to cache the divisors for all values of n that happen during the execution.

Div1 medium

The first observation is that an almost-Eulerian graph can be obtained from a unique Eulerian graph. Indeed, if we have an almost-Eulerian graph G that is not Eulerian, then there exists the only pair of vertices u and v that have an odd degree, the only possible original Eulerian graph G' is (here means inverting the specific edge, adding it or removing it). If G is Eulerian itself, then we obviously can't invert some edge keeping it being Eulerian.

This means that if there are E_n Eulerian graphs, then there are exactly almost-Eulerian graphs: each Eulerian graph G produces itself and all possible as almost-Eulerian graphs.

Now we need to calculate number of Eulerian graphs on n vertices, E_n. It's well-known that the graph is Eulerian iff it is connected and all its vertices have even degree. The good idea is to first calculate D_n, the number of graphs with all even degrees. If we succeed in it, we can then calculate E_n by using inclusion-exclusion principle on D_n.

How many even graphs on n vertices are there? The simplest way to understand that is to remove some vertex from it (let's say, a vertex 1) and notice that the graph on remaining vertices 2, ..., n may contain an arbitrary set of edges. Indeed, if there are some odd vertices among them, then when we return vertex 1 back to the graph, we have to connect it to all odd vertices among 2, ..., n. After that all 2, ..., n become even vertices, and 1 itself also becomes even due to handshake lemma. So, the answer is since there may be any possible set of edges between vertices 2, ..., n and all edges from 1 to the rest of the graph may be uniquely determined.

Now how to calculate E_n. We know that E_n = D_n - R_n where R_n is number of disconnected even graphs. Suppose that the connected component that contains vertex number 1 consists of k vertices (obviously, 1 ≤ k ≤ n - 1). Then there are ways to choose k - 1 vertices in this connected component from n - 1 remaining vertices, also there are E_k ways to organize a connected component that has all even degrees and there are D_n - k ways to organize an even graph on the rest of the vertices (note that it may possibly be disconnected if there were 3 or more components in the original graph, that's why we use D_n - k but not E_n - k here). So, there is a recursive formula: that leads us to an O(n²) DP solution.

Div1 hard

I'll describe an approach for this problem very briefly.

What we actually need in this task is to understand how the described process works. We can describe the process in following way. The detective acts almost like a Prim's algorithm: in each step he adds one of the maximal edges between the already visited set and the rest of the vertices in the graph. The only thing that we may adjust is an order of choosing the edges with the equal cost.

At any moment the visited vertices form some part of a maximum spanning tree. Suppose we want to get to vertex x in minimum number of steps. Consider the resulting path between 0 and x. It is a well-known fact that the minimum edge on this number is uniquely defined and is equal to a maximum possible minimum edge among all paths from 0 to x. Suppose the value of this edge is equal to d. We can calculate d by running a Floyd algorithm modification for metric d(u, v) =  minimum on path between u and v, that is needed to be maximized.

There are edges of two kinds on a path from 0 to x: those who are equal to d and those who are larger than d. In any situation we prefer larger edges, so when we touch a vertex with some outgoing edges larger than d, we will greedily first visit all those edges. So, let's contract all components connected by edges larger than d.

After contracting all we need is to find a shortest path from 0 to x remembering that each time we visit a vertex, we have to add a size of its connected component described above.