Hi all!

I invite you to participate in the gym contest LU ICPC Selection Contest 2023 on Nov/08/2023 17:35 (Moscow time)! The onsite contest has been held on October 13th in Riga to select two teams from the University of Latvia to CERC 2023. Here's the headline of the local poster (in Latvian):

The contest has been prepared by me, cfk and Pakalns. Hopefully you'll find the problems interesting!

Всем привет!

Приглашаю поучаствовать в ICPC контесте в тренировке, отборочный контест Латвийского университета на ICPC 2020 и Открытая командная олимпиада Казанского федерального университета 2020 в эту 21.11.2020 11:00 (Московское время)! Контест был проведён 31-ого октября в Латвии для отбора лучших команд ЛУ на четвертьфинал (региональные соревнования Беларусии и Балтии), и затем 1-ого ноября в Казани, КФУ для студентов и учеников.

Контест был подготовлен AcidWrongGod, Ferume, KamilBek, cfk, gen, lessmeaning, авторами из ЛУ и КФУ.

Условия будут на английском и русском. Если есть свободное время в субботу, enjoy!

Привет всем!

Я рад пригласить всех к участию в онлайн зеркале Балтийской олимпиады по информатике в 22.07.2020 14:05 (Московское время) и 23.07.2020 14:05 (Московское время) на Codeforces!

Балтийская олимпиада по информатике 2020 (BOI 2020) – индивидуальное соревнование для учеников средней школы из одиннадцати стран (в алфавитном порядке): Германия, Дания, Исландия, Латвия, Литва, Норвегия, Польша, Украина, Финляндия, Швеция и Эстония. Более 60 участников борются между собой, решая сложные алгоритмические задачи. Каждая страна представлена 6 лучшими участниками по итогам национальных олимпиад. Официальную страницу олимпиады можно посмотреть на boi2020.lv.

Контест состоит из двух дней, каждый день участникам дано 5 часов на решение 3 задач различной сложности. За каждую задачу можно получить до 100 баллов, которые распределены по нескольким подзадачам с различными ограничениями, что позволяет участникам получить частичные баллы. Оценивание происходит по формату IOI, где участник получает полный отчёт по тестированию по всем тестам во время соревнования.

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

Обратите внимание, что соревнование не рейтинговое. Зеркало начинается на 1 день, 1 час и 5 минут позже официального контеста.

Желаем интересного контеста! :)

-- BOI 2020 committee

Мартиньш Опманис, Рихардc Опманис, Сергей Мельник, andreyv, Pakalns, gen, eduardische, Alex_2oo8, nvilcins, KarlisS.

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

UPD2: Разбор задач 1-ого дня опубликован.

UPD3: Разбор задач 2-ого дня опубликован.

UPD4: Поздравляем победителей с полным результатом 600 баллов WZYYN, isaf27, Arpa!

Привет всем!

Рад пригласить всех на Codeforces Round #599, который состоится в 06.11.2019 18:05 (Московское время)!

Меня зовут Евгений Вихров, это уже мой шестой контест на Codeforces. Немного обо мне: я дважды участвовал в финале ICPC (2012, 2014) и сейчас помогаю подготавливать команды Латвийского университета для участия в ICPC. Это мой первый соло раунд, и его подготовка заняла 3.5 лет! (Предыдущий раунд, #347, мы провели вместе с Alex_2oo8.)

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

Огромное спасибо arsijo за координацию раунда и терпение во время многочисленных задержек. :) Спасибо Xellos, Origenes, KAN и _overrated_ за щедрое тестирование задач. И, как всегда, спасибо MikeMirzayanov за хлеб и зрелища системы Codeforces и Polygon!

Желаю захватывающего раунда!

UPD1: McDic присоединяется как соавтор раунда (причины будут прояснены позже)!

UPD2: Scoring:

Div. 1: 500-1000-1500-2000-2500

Div. 2: 500-500-750-1500-2000-2500

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

Div. 1:

1. Benq
2. EvenImage
3. ecnerwala
4. AndreySergunin
5. tribute_to_Ukraine_2022

Div. 2:

1. hakobdilif
2. is1813r
3. Fype
4. KenMuse
5. tdas

UPD4: Разбор будет опубликован завтра, извиняюсь за задержку. :((

UPD5: Причина тому, что McDic присоединился как соавтор, в том, одна задача оказалась идентичной одной задаче из одного раунда Codeforces. Мы узнали об этом за день до контеста, и McDic великодушно разрешил использовать свою задачу.

UPD6: Разбор опубликован (пока что только на английском).

UPD7: Опубликован разбор на русском.

Hello, Codeforces!

I'm glad to invite you to participate in the online mirror of the Baltic Selection Contest for ACM ICPC 2015–2016 that will take place in Gym on the 22nd of October, 13:00 UTC.

This competition determines the best teams throughout the universities of Latvia, Lithuania and Estonia that will participate in ACM ICPC NEERC Western subregional contest in Minsk, Belarus. The onsite contest was held on the 12th of October. The participating universities were University of Latvia, Vilnius University, Kaunas University of Technology, Vilnius Gediminas Technical University, Estonian Information Technology College and others.

As a bonus, I'm posting some photos of the onsite action at University of Latvia. :)

The top 5 teams at the onsite competition were:

1. LU: 64428b862de0207ba0385b1ed2df43e1 (Alex_2oo8, zmad)
2. VU: 2B||!2B (vstrimaitis, jDomantas, JustasK)
3. LU: 0x7DF (Pakalns, Candyman, A_Le_K)
4. LU: leet (Instasamka, how_to_become_purple, JustN)
5. KTU #1 (wi_lius, lukgar, ASBusinessMagnet)

The detailed onsite standings will be posted after the contest.

The problems were prepared by a group of authors from University of Latvia: gen, KarlisS, andreyv, cfk.

Good luck & have fun!

405A - Переключение гравитации

Заметим, что в конечном расположении все высоты столбиков расположены в неубывающем порядке. Также, количество столбиков каждой высоты остаётся неизменным. Это означает, что ответом является упорядоченная последовательность данных высот столбиков.

Сложность решения: O(n), так как можно упорядочить подсчётом.

405B - Эффект домино

Если самая первая толкнутая доминошка слева была толкнута влево на позиции l, все доминошки на префиксе [1;l] падают, иначе пусть l будет 0. Аналогично, если самая последняя толкнутая доминошка была толкнута направо на позиции r, все доминошки на суффиксе [r;n] падают, иначе пусть r будет n + 1. Теперь, на отрезке (l;r) остаются вертикально стоящие доминошки, а также блоки домино, поддерживающиеся одинаковыми силами с обеих сторон.

Когда доминошка на позиции p на отрезке (l, r) остаётся стоять вертикально? В одном случае, её не толкает ни одна другая доминошка. Это можно легко проверить, посмотрев на ближайшие к p толкнутые доминошки (с обеих сторон). Она была затронута другими домино, если самая близкая толкнутая доминошка слева была толкнута направо и самая близкая толкнутая доминошка справа была толкнута влево. Допустим, эти доминошки находятся на позициях x и y, x < p < y. Тогда, единственная возможность для доминошки остаться вертикально тогда, когда она находится в центре блока [x;y], что можно проверить выражением .

Сложность решения: O(n) / O(n²), что зависит от реализации.

406A - Необычное произведение

Если записать в виде формулы искомое произведение в задаче, получаем

Допустим, что i ≠ j. Тогда сумма содержит слагаемые A_ijA_ji и A_jiA_ij. Так как сумма всегда берётся по модулю 2, вместе эти слагаемые дают 0 к сумме. Из этого следует, что выражение всегда равняется сумме битов на диагонали:

Теперь, каждый запрос типа 1 и 2 меняет значение ровно одного элемента на диагонали. Поэтому мы можем посчитать необычное произведение изначальной матрицы, и после каждого запроса типа 1 и 2 менять его значение на противоположное.

Сложность решения: O(n + q), если не брать во внимание ввод... :)

406B - Игрушечная сумма

Определим для числа k его симметричное число как s + 1 - k. Так как в задаче s чётное число, k ≠ s - k.

Заметим, что (k - 1) + (s + 1 - k) = s, т.е., сумма числа и его симметричного всегда равно s. Будем обрабатывать все числа x множества X по порядку. Различаем два случая:

1. Если симметричное x не принадлежит X, добавим его к Y. Оба числа дают одинаковые значения к соответствующим суммам: x - 1 = s - (s + 1 - x).
2. Симметричное x принадлежит X. Тогда возьмём любое y такое, что ни y, ни симметричное y не принадлежат X, и добавим их к Y. Обе пары дают одинаковые значения к соответствующим суммам, а именно s.

Как доказать, что во втором случае мы всегда сможем найти такое y? Пусть количество симметричных пар, которые были обработаны в первом случае, равно a, тогда остаются других пар. Среди них, для пар оба числа принадлежат X, а для других пар никакие из чисел не принадлежат X. Чтобы выбрать такое что количество пар для Y, как и в X, должно выполняться

что равносильно , как и дано в условии.

Сложность решения: O(s) / O(n).

406C - Разрез графа

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

Функция partition(v) будет работать на незаблокированных рёбрах. Она разбивает компоненту вершины v, связную по незаблокированным рёбрам, на пути длины 2. Если компонента имеет нечётное количество рёбер, функция разобьёт все рёбра компоненты, кроме одного ребра (u, v); тогда функция вернёт вершину u, ожидая, что предыдущий вызов функции присвоит это ребро какому-нибудь пути.

Функция работает следующим образом: найдём все вершины, соседние с v по незаблокированным рёбрам, назовём это множество adjacent. Далее заблокируем все рёбра из этих вершин в v. Для каждой u в adjacent, вызовем partition(u). Допустим, что вызов partition(u) вернул вершину w. Это значит, что мы можем присвоить её в путь (v, u, w). Иначе, если partition(u) ничего не вернул, добавим u к unpaired, потому что ребро (v, u) ещё не присвоено ни одному пути. Мы можем объединить в путь любые две вершины этого множества u, w в один путь (u, v, w). Спарим как можно больше таких вершин в любом порядке. Если из этого множества осталась только одна вершина, u, то функция вернёт u. В противном случае функция ничего не возвращает.

Функцию можно реализовать всего одним DFS:

partition(v) :
    adjacent = { u | not blocked[(u,v)] }
    for(u : adjacent)
        blocked[(u,v)] = true

    unpaired = {}
    for(u : adjacent)
        int w = partition(u)
        if(w = 0)
            add(unpaired, u)
        else
            print(v,u,w)

    while(size(unpaired) >= 2)
        int u = pop(unpaired)
        int w = pop(unpaired)
        print(u,v,w)

    if(not empty(unpaired))
        return pop(unpaired)
    else
        return 0

Сложность решения: O(n + m).

406D - Скалолазание

Заметим, что каждый путь скалолаза выпуклый в любом случае. Проведём пути из всех скал до последней скалы. Тогда эти пути образуют дерево с «корнем» в вершине последней скалы. Мы можем применить алгоритм Грэхема справа налево, чтобы найти рёбра этого дерева. Каждое удаление и добавление в стеке соответствует ровно одному ребру в дереве.

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

Сложность решения: .

406E - Тройки Хемминга

Давайте рассмотрим хэммингов граф из всех различных 2n строк, где каждые две строки соединены ребром длины, равному расстоянию Хэмминга между этими строками. Мы можем заметить, что этот граф обладает годным свойством: если упорядочить все вершины циклически по правильному 2n-угольнику со стороной длины 1, расстояние Хэмминга для каждых двух строк равняется длине кратчайшего пути между этими вершинами на периметре этого многоугольника.

Например, на рисунке изображён такой граф для n = 3. Серые рёбра имеют длину 1, оранжевые рёбра имеют длину 2, синие рёбра имеют длину 3. Это равняется соответствующему расстоянию Хэмминга.

Теперь, мы можем преобразовать каждую строку, закодированную парой чисел (s, f), в целое число (f + 1)·n - s. Новые числа будут среди 0, 1, ..., 2n - 1 и соотноситься с тем же циклическим порядком на периметре многоугольника. Данные строки переходят в какой-то набор вершин. Теперь нам нужно найти количество треугольников (возможно, дегенерированных) с наибольшим периметром в этом подграфе. Далее будет полезно упорядочить преобразованные числа.

Для начала, можно попробовать понять, каким может быть этот периметр. Если существует такой диаметр в полном графе, что все данные точки находятся по одну сторону диаметра, периметр будет равен 2d, где d является значением самого длинного ребра:

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

Если для любого диаметра это не выполняется, тогда наибольший периметр равен 2n. Это можно доказать, взяв две различных точки a, b, и проведя два диаметра из этих точек как концов; так как это не предыдущий случай, должна быть третья точка c в месте, где периметр треугольника a, b, c равняется 2n.

Самая хитрая часть и есть посчитать тройки в этом случае. Мы делаем это, работая с диаметром (0, n). Всего может быть несколько случаев:

1. Наибольший треугольник содержит обе вершины 0 и n. Это простой случай: с любой другой вершиной как третьей такой треугольник имеет периметр 2n.
2. Наибольший треугольник содержит вершину 0, но не n. Тогда вторая вершина должна находится на отрезке [0, n), а третья на отрезке (n + 1, 2n - 1], и расстояние по часовой стрелке между второй и третьей вершинами не должно превышать n (в противном случае периметр треугольника был бы меньше, чем 2n). Мы считаем количество таких троек, двигая два указателя (по одному на каждый из этих отрезков). Для каждого указателя в первом отрезке, все точки, начиная с n + 1 до второго указателя образуют наибольший треугольник. Аналогично мы решаем случай, когда треугольник содержит n, но не 0.
3. Наибольший треугольник не содержит ни 0, ни n как вершины. Тогда одна вершина треугольника должна находится на одной стороне диаметра (0, n), а две остальные на другой стороне. Чтобы посчитать их, будем двигать указатель на первую вершину на одной стороне, скажем, (0, n); обозначим диаметрально противоположную вершину за x. Тогда вторая вершина может быть любой на отрезке [n + 1, s], а третья может быть любой на [s, 2n - 1]. Количество этих точек легко посчитать, используя частичные суммы на круге. Заметьте, что s может быть как второй, так и третьей вершиной одновременно (строки могут повторяться). Тогда мы двигаем этот указатель через все вершины одной стороны и обновляем ответ. Аналогично мы решаем случай, когда первая вершина на второй стороне, а обе других на противоположной.

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

Сложность решения: из-за сортировки.

Post Scriptum

Какими были ваши решения? Не стесняйтесь поделиться любыми решениями или мыслями! Например, было ли в DivI E решение, проще авторского?

Всем привет!

Сегодня в 19:30 по Московскому времени состоится раунд Codeforces #238. Контест пройдёт в обоих дивизиях.

Раунд был подготовлен мной и cfk. Это мой 4-ый раунд и 2-ой раунд Кришьяниса. В этот раз, по-моему, задачи весьма необычные и, может, даже неожиданные. Мы уверены, что любой участник(ца) найдёт себе задачу по вкусу! Но нужно её найти. (:

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

Мы желаем вам захватывающего раунда!

UPD1: Распределение баллов:

DivI: 500 1000 2000 2000 2500

DivII: 500 1000 1500 2000 3000

Баллы выставлены относительно, чтобы стоимость каждой задачи делилась на 500, и была бы ближе к объективной оценке. Не пугайтесь, на самом деле задачи не настолько сложные. (:

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

DivI:

1. al13n
2. Shef
3. scott_wu
4. sillycross
5. Komaki

DivII:

1. NelsonMondialu
2. L_Ecry
3. aaaaAaaaaAaaaaAaaaaA
4. xorfire
5. Hec

UPD3: Замечательная статистика раунда от DmitriyH.

UPD4: Разбор опубликован здесь.

Привет всем!

Сезон ACM ICPC проходит в полном разгаре, и не за горами региональные соревнования северно-западного региона (NWERC). Поэтому 26-ого октября в Кембриджском университете среди 9 команд прошёл отбор (по крайней мере двух) лучших, которые поедут дальше бороться за свое место в финале. В итоге первые пять мест в следующем порядке заняли команды:

1. Fin! IRO (pooya_, bogdan2412, VladGavrila)
2. Beuler (borisgrubic, lm497, dcevid)
3. Rooftop Cornflakes (eduardische, Chortos-2, Gullesnuffs)
4. Zrakomlati (PetarV, mbucic4, dsobot)
5. CRTCM (Voro94, Andip, hadesgames)

С чем их и поздравляю!

Соревнование прошло на платформе Codeforces и его подготавливали я вместе с MikeMirzayanov. Организовывали соревнование преподаватель Кембриджского университета доктор Эндрю Райс, сам eduardische, Chortos-2, а также тренер школьной сборной Латвии Сергей Мельник. Сам контест был проведён на задачах Южного четвертьфинала ACM ICPC 2013. Да-да, именно того, интернет-версия которого 27-октября проходит в тренировках Codeforces. ;] Если после прочитанного вы решили, что пропустили что-то необычное на CF, то ничего подобного! Контест прошёл, в тестовом режиме используя (пока секретную) будущую функциональность Codeforces — группы.

Данная функциональность позволит проводить тренировки для ограниченной группы пользователей и зрителей. Менеджер группы добавляет пользователей в группу и ограничивает их доступ. Тренировку группы могут писать только пользователи этой группы, так же, как и наблюдать за результатами соревнования. Как видите, группы хорошо подходят для разного рода онсайт-соревнований. Для этой цели мы и использовали рабочую версию групп в этот раз. Огромное спасибо MikeMirzayanov за возможность попробовать этот функционал! Далее оставляю пару картинок-тизеров: ;]

В заключение пара слов о ходе отбора. Количество задач, решённых первыми пятью командами, является 10, 9, 8, 7, 6, что на фоне результатов самого четвертьфинала является серьёзной заявкой со стороны Кембриджского университета. ;] Между первыми тремя командами в течение долгого времени была интенсивная борьба за первые два места, но Fin! IRO в середине контеста вырвались вперёд и стабильно держали лидерство с большим количеством решённых задач. Команды Beuler и Rooftop Cornflakes боролись практически до окончания, пока первая не сдала целых две задачи где-то за полчаса до конца. Вторая из них тоже смогла сдать две задачи в последний час, но Beuler сдали задачу D в 4:47, и завоевали 2-ое место, когда Rooftop Cornflakes — 3-ье. Полные результаты команд из Кембриджа будут объединены с результатами тренировки на задачах южного четвертьфинала.

Привет всем!

Никогда не задумывались над странными последствиями социального поведения общества на CF? В частности, мне был очень интересен эксперимент пользователя I_love_Tanya_Romanova, и в сущности, я пришёл к следующему выводу. Ни для кого не секрет, что на CF довольно сильно проявляется «цветовая» дискриминация, и это очень сильно влияет на [+]/[-] оценку постов/комментариев. Более высокий цвет даёт пользователю неформальное основание считать своё мнение более обоснованным, чем мнение пользователя с меньшим цветом. С другой стороны, меньший цвет автора сообщения даёт наблюдателю больший повод сомневаться в написанном. Однако для пристрастного голосования нужно ещё подтверждение «со стороны», чтобы присудить комментарию значение с соответствующим знаком. Этим катализатором и является первый плюс или минус. В частности, для оранжевых и красных пользователей это означает практический социальный «иммунитет» (пока не начинается дебоширство ;]); серые и зелёные пользователи зато испытывают сильную «уязвимость». Естественно, «правильность» мнений по отношению к цветам верно в какой-то степени, но всё-таки далеко не в полной мере.

На самом деле это представляет весомую проблему для объективной оценки комментария/поста, а так же для свободного выражения мнения. Поэтому, как кажется мне, совершенно неправильно показывать точное количество плюсов и минусов, набранных сообщением (это также позволяет «тюнить» оценку, если пользователь считает, что сообщение набрало больше плюсов или минусов, чем заслужило). Известно, конечно, что многие системы оценок пытаются избежать таких ям. Одна из самых привлекательных альтернатив была бы следующей: не показывать точный рейтинг сообщения, а «подкрашивать» его зеленым цветом с насыщенностью, пропорциональной количеству плюсов. Особенно отрицательные комментарии скрывать, как обычно. «Подкрашивание» абстрактно, его можно реализовывать по разному. При том я не призываю что-то сразу менять, а просто поразмышлять на тему лучшего выбора.

Какого ваше мнение? Любые комментарии и обсуждения приветствуются. И не забудьте плюсануть пост! :]

344A - Магниты

По определению каждый островок состоит из последовательных одинаково направленных домино. Значит, в местах, где соседние домино направлены не одинаково, кончается один островок и начинается следующий. Значит, если таких мест x, то ответ равен x + 1.

Сложность решения O(n). Автор задачи: gen.

Бонус: Задача была придумана в день перед контестом и полностью дополнила физически направленный комплект для DivII :]

344B - Простые молекулы

Первое решение. Во-первых, заметим, что сумма a + b + c должна быть чётной, потому что каждое ребро прибавляет два к сумме. Теперь допустим, что между 1-ым и 2-ым, 2-ым и 3-им, 3-им и 1-ым атомами есть x, y и z связей, соответственно. Поэтому нам нужно решить систему x + z = a, y + x = b, z + y = c. Можно заметить, что решением этого уравнения являются длины касательных на треугольнике со сторонами a, b, c к его вписанной окружности, и равняются , , . Если бы в задаче просили проверить только, можно ли построить такую молекулу, то хватало бы проверить нестрогое неравенство треугольника для a, b, c.

Второе решение. Переберём значение x. Для него значения y и z определены однозначно: y = b - x, z = a - x.

Сложность решения O(1) / O(n). Авторы задачи: gen, andreyv.

Бонус: Можете ли вы решить задачу для произвольного n? Когда и как можно построить связный граф?

343A - Рациональное сопротивление

Если с помощью k элементов можем получить дроби , то нетрудно посчитать, что с помощью k + 1 элементов можно получить дроби и . То есть прибавление одного элемента эквивалентно одному шагу алгоритма Эвклида для числителя и знаменателя в обратном направлении. Значит, ответ равняется количеству шагов стандартного алгоритма Эвклида.

Сложность решения . Авторы задачи: gen, andreyv.

Бонус: Вначале мы думали об общей задаче (можно соединять два любых элемента, как многие неправильно поняли задачу), однако случился момент эврики, и мы поняли, что данная задача неожиданно естественно сводится к НОД. Кстати, дерево результатов – http://en.wikipedia.org/wiki/Calkin%E2%80%93Wilf_tree.

343B - Переменный ток

Вначале решим другую задачу: дана строка, состоящая из символов A и B. Если i-тый символ А, то на i-том шаге верхний провод (на рисунке) кладётся поверх нижнего. Если i-тый символ B, то нижний провод (на рисунке) кладётся поверх верхнего. Заметим, что если символ А стоит рядом с символом B, то эти два заплетания можно распутать и получить ситуацию, которую описывает та же строка, в которой выкинуты эти два символа. Поэтому провода можно распутать тогда и только тогда, если количество А совпадает с количеством В в этой строке. Нашу задачу мы можем свести к вышеописанной следующим образом: на каждой нечётной позиции заменяем – на B, а + на A. На чётных позициях заменяем – на A, а + на B. Можно видеть, что сведение правильное, потому что на каждой чётной позиции – и + всегда стоят перевернутые относительно начала, а на каждой нечётной порядок совпадает с порядком начала.

Сложность решения O(n). Авторы задачи: gen, andreyv.

Бонус: Если тема вас заинтересовала, можете ознакомиться с теорией кос http://en.wikipedia.org/wiki/Braid_theory :] Fun fact: усложнённый вариант задачи был предложен ещё на Round #142, но тогда в решении нашлась ошибка, и задача осталась лежать почти целый год.

343C - Время чтения

Будем искать ответ t двоичным поиском. Рассмотрим конкретное значение t. Рассмотрим первую головку слева h[i], которая может считать p[0]. Если p[0] > h[i], то h[i] просто идёт направо t секунд, и читает все дорожки на пути. Если p[0] ≤ h[i], то у головки есть два выбора:

1. идти направо секунд, затем налево и опять налево ещё h[i] - p[0] секунд;
2. идти налево h[i] - p[0] секунд, затем направо h[i] - p[0] и опять направо t - 2·(h[i] - p[0]) секунд.

Естественно, для h[i] выгоднее всего побывать в самой правой точке. Поэтому выбираем по . Дальше двигаем указатель на первую несчитанную дорожку, и повторяем алгоритм для h[i + 1], и.т.д. с каждой головкой.

Сложность решения . Авторы задачи: gen, gorbunov.

Бонус: Задача полностью реальна, если у диска есть только одна головка, и известно, какие данные нужно считать, то оптимальный алгоритм выбирает один из описанных двух вариантов. Это мы слушали на лекции вместе с gorbunov, и от скуки придумали такую задачу ;]

343D - Водяное дерево

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

Заведём дерево отрезков. Для него выполняется свойство: если вершина v была опустошена, и она до сир пор пуста, то эта вершина покрашена в дереве отрезков. В самом начале «опустошим» все вершины. То есть, покрасим все вершины в дереве отрезков. С помощью этого дерева можно эффективно обрабатывать запросы:

1. Заполняем вершину v. Стираем всё поддерево v в дереве отрезков. Если до этого поддерево не было пустым, то красим родителя v.

2. Опустошаем вершину v. Красим вершину v в дереве отрезков.

3. Отвечаем, заполнена ли вершина v. Если в дереве отрезков сумма поддерева v не равна 0, значит есть такой потомок v, который опустошён сейчас, поэтому вершина v не заполнена.

Идейно похожее, но более простое решение в написании предложил Shtrix.

Сложность решения . Автор задачи: gen.

Бонус: Некоторые участники могли заметить схожесть задачи с задачей Ball Machine из BOI 2013, однако решения этих задач имеют мало похожего.

343E - Насосные станции

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

Задача решается с помощью структуры данных дерево Гомори-Ху. Для данного взвешенного графа дерево обладает свойствами:

1. Множество вершин дерева совпадает с множеством вершин графа.
2. Максимальный поток в дереве между вершинами u и v равен максимальному потоку в графе между вершинами u и v.

Такое дерево на удивление существует для любого взвешенного графа и строится за время O(n·maxFlow). Оказывается, что для данной задачи ответом является сумма весов рёбер в таком дереве.

Докажем это утверждение индукцией по количеству вершин в дереве. Найдём ребро (u, v) с минимальным весом в дереве. Допустим, что для оптимальной перестановки вершин через это ребро проходит больше, чем один путь между парами соседних вершин в перестановке. Сотрём все такие пути, тогда в поддеревьях u и v остаётся в каждом по множеству несоединённых цепочек путей. Соединим все пути в каждом множестве в одну цепочку и получим две цепочки. Эти цепочки соединим одним путём s, который идёт через ребро (u, v). Получили перестановку, которая не хуже оптимальной. Для пути s ребро (u, v) является наименьшим, значит поток по этому пути равен весу этого ребра. Из индукции следует, что в поддеревьях u и v ответ равняется сумме ребёр. Добавляя к сумме вес ребра (u, v), получаем желаемое.

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

Сложность решения O(n·maxFlow). Авторы задачи: gen, Gerald.

Бонус: Ближе к соревнованию мы решили сделать ограничения лояльней, поэтому прошли также решения, которые O(n²) раз вызывают поток и затем строят дерево Гомори-Ху. Надеемся, этот факт никого особенно не огорчил. (;

Привет всем!

Сегодня в 19:30 по Московскому времени состоится юбилейный Codeforces Round #200. Раунд будет проведен в обоих дивизионах и будет рейтинговым.

Задачи раунда подготовили Евгений Вихров (gen), Андрей Вихров (andreyv) и Геральд Агапов (Gerald). Как всегда, выражаем благодарность Михаилу Мирзаянову (MikeMirzayanov) за системы Codeforces и Polygon. Отдельное спасибо Марии Беловой (Delinur) за перевод условий задач.

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

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

UPD1: Разбалловка задач стандартная:

DivI: 500 1000 1500 2000 2500

DivII: 500 1000 1500 2000 2500

UPD2: Поздравляем две лучших пятёрки победителей!

DivI

1. tourist
2. KADR
3. SillyHook06
4. niyaznigmatul
5. Igor_Kudryashov

DivII

1. Giraffy
2. jzc
3. ryad0m
4. Kamilot
5. API

Div II A — Завидный забор

Задача

Нужно определить, существует ли правильный многоугольник, углы которого равны a.

Решение

Рассмотрим все смежные углы правильного n-многоугольника с углом a, они равны . Их сумма равна , так как многоугольник выпуклый. Тогда выполняется следующее равенство: n·(180 - a) = 360, которое означает, что ответ есть, когда .

Время: O(t).

Память: O(1).

Реализация: C++, Java

Комментарий

Задача также решается поворачиванием вектора (1, 0) на угол величины , пока он не вернётся на свою позицию (поворот делаем не более 360 раз), и проверяя, совершили ли мы ровно один полный оборот (пример реализации: C++).

Это также одна из редких задач на Codeforces, у которой всего 1 пример, 1 претест и 1 полный тест.

Div II B — Обсуждения

Задача

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

Решение

Если какой-то a_i больше, чем a_i + 1, то ясно, что a_i точно был перемещён, так как порядок этих двух элементов изменился. Пусть последний такой элемент является a_k. Тогда все элементы a_k + 1, a_k + 2, ..., a_n могли быть не затронуты операциями, так как их порядок не изменился. Ответ на задачу равен n - k. Если такого a_k нет, то порядок не изменился вообще и тогда могло не быть операций.

Время: O(n).

Память: O(n) / O(1).

Реализация: C++, Java

Комментарий

Задача появилась, когда автор зависал на главной странице Codeforces, пытаясь придумать лёгкую задачу для Div II. =)

Div II C / Div I A — Волшебные ларцы

Задача

Нам даны a_i квадратов со стороной 2^k_i. Квадрат разрешено поместить только в больший квадрат, при том никакие два квадрата не дожны перекрываться. Мы должны найти наименьшее p такое, что мы можем поместить все данные квадраты в квадрат со стороной 2^p.

Решение

Допустим, что мы можем поместить все квадраты внутри квадрата со стороной 2^p. Тогда можно разместить квадраты типа k_i независимо друг от друга по сетке так, как показано на рисунке. Никакие два квадрата не будут перекрываться, так как 2^x делит 2^y, если x < y. Это значит, что мы можем найти наименьший квадрат, который вмещает все данные квадраты со стороной 2^k_i для каждого k_i отдельно. Тогда ответ будет равняться стороне наибольшего такого квадрата.

Чтобы можно было разместить a_i квадратов со стороной 2^k_i внутри квадрата со стороной 2^s, должно выполнятся следующее равенство:

Тогда мы можем найти наменьшее s:

В частном случае, когда s = k_i, s увеличиваем на 1.

Время: .

Память: O(1).

Реализация: C++, Java

Комментарий

Задачу также можно решить двоичным поиском по p. Однако, заметим что каждый квадрат со стороной 2^k + 15 помещяет в себе любое данное количество квадратов со стороной, меньшей 2^k, так как . Поэтому достаточно найти первый подходящий квадрат со стороной от 2^{max k + 1} до 2^{max k + 15}.

Div II D / Div I B — Теплица

Задача

На прямой даны n точек, каждая одного типа от 1 до m. Мы можем раздеить прямую на m - 1 интервалов и переместить какое-то количество точек так, чтобы каждая точка типа i находилась бы внутри i-того интервала, которые пронумерованы от 1 до m слева направо. Нужно найти минимальное количество точек, которые нужно переместить.

Решение

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

В этой задаче достаточно было реализовать квадратичное решение. Считаем dp[i][j] — длина наидлиннейшей неубывающей последовательности на префиксе [1;i], где j — тип последнего элемента. Переход динамики:

Для лёгкой реализации, хватает завести один массив dp[j], и пропустить обработку второго случая.

Время: O(n²) / .

Память: O(n²) / O(n).

Реализация: C++

Комментарий

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

Div II E / Div I C — Неисправный Поток

Задача

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

Решение

Ключевой элемент к решению задачи — следующее наблюдение: если нам известны все входящие рёбра одной вершины, то остальные рёбра должны быть исходящими. Исток не имеет входящих рёбер, поэтому мы уже знаем, что все его рёбра исходящие. Для всех остальных вершин, исключая сток, количество входящего и исходящего потока одно и то же, и равняется половине суммы потока, проходящего по всем рёбрам из этой вершины. Тогда алгоритм заключается в многократном направлении всех рёбер из вершин, для которых все входящие рёбра уже известны. Это можно сделать одним BFS:

for all v from 2 to n-1
    f[v] := sum(flow(v,u))/2;
put source in queue
while queue is not empty
    v := pop(queue)
    for all edges (v, u)
        if (v, u) is not directed yet
            direct v -> u
            f[u] = f[u] - flow(v,u)
            if u not sink and f[u] = 0
                push(queue, u)

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

Время: O(n + m)

Память: O(n + m)

Реализация: C++, Java

Комментарий

Очевидное «простое» решение — запустить алгоритм нахождения максимального потока на том же графе, и получить ответ. Однако все такие решения сваливались на претесте #6.

269D - Максимальный водопад

Задача

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

Решение

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

События сканирующей являются отрезками. Когда встречается новый отрезок, мы хотим найти все такие нижние отрезки, на которые мы можем направить поток с этого отрезка. Такими могут быть только такие отрезки, чьи части находятся в сканирующей и перекрываются с данным отрезком. Затем мы итерируемся по всем таким частям p (найти первую такую часть — операция). Как мы узнаем, можно ли направить поток на p? Заметим, что если какой-то другой отрезок мешает этому, то в сканирующей должна существовать такая его часть q, которая видна с данного отрезка. А так как все три проекции этих отрезков перекрываются, то такая часть может быть только сразу слева или справа от p в двоичном дереве. Поэтому мы просто проверяем, не мешают ли изначальные отрезки таких двух частей рядом с p направить поток с данного отрезка на на изначальный отрезок p.

Затем мы вынимаем все такие части из сканирующей, и кладём новую часть, соответствующую данному отрезку. Если этот отрезок только частично перекрывал какую-то из частей в сканирующей, мы вставляем обратно остальную часть этой же самой части. Таких частей может быть только две — по одной на каждой стороне отрезка. Поэтому при обработке каждого отрезка вставляется не более 3 новых частей и размер сканирующей O(n). Каждая часть обрабатывается ровно один раз перед выниманием, поэтому суммарное время таких операций .

Когда мы узнаём, что можно направить поток по , сразу же обновляем наибольший возможный нисходящий поток из a:

Когда обработаем верхний отрезок, f_top будет ответом.

Время:

Память: O(n)

Реализация: C++, Java

Комментарий

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

Div I E — Теория Струн

Задача

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

Решение

Всего есть 6 разных типов отрезков, соединяющих стороны:

1. слева-наверх;
2. сверху-направо;
3. справа-вниз;
4. снизу-налево;
5. слева-направо;
6. сверху-вниз;

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

Все справа-вверх отрезки должны находится в левом верхнем углу, и соединять точки (L,i) и (T,i), иначе они бы точно пересекались с какими-нибудь отрезками. Аналогично должны быть расположены все сверху-направо, справа-вниз, снизу-налево отрезки. Все сверху-вниз отрезки же должны быть параллельными. Также заметим, что количество слева-наверх отрезков должно быть равно количеству отрезков справа-вниз, а количество сверху-направо отрезков должно быть равно количеству отрезков снизу-налево. Из этого следует важное наблюдение: картинка прямоугольника после перестановок задана однозначно и может быть получена из входных данных, просто считая количество отрезков каждого типа.

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

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

В данный момент мы действительно находим циклы в обоих прямоугольниках. Есть только два типа циклов:

1. (слева-наверх) (сверху-направо) (справа-вниз) (снизу-налево);
2. остальные циклы

Можно легко проверить, равняются ли между собой множества циклов первого вида, так как длина таких циклов 4. Если они совпадают, то мы переставляем соответствующие ряды и столбцы в правильном порядке.

Как сравнить остальные циклы? Рассмотрим следующий пример:

Пусть разница количеств слева-наверх и слева-вниз отрезков равна i, а это число плюс количество сверху-вниз отрезков равно s. Если пронумеровать точки, как показано на рисунке, можно заметить, что кажая точка k сверху соединена с нижней точкой (сверху-направо отрезки продолжаются как соответствующие слева-вниз отрезки). Это можно описать перестановкой

Наши циклы соответствуют циклам перестановки, при том сверху-направо отрезки продолжаются в слева-вниз именно там, где в этой перестановке элемент цикла уменьшается. Известно, что перестановка такого типа состоит из циклов длины , то есть все циклы одинаковой длины. Обозначим каждый тип отрезка одним символом (на рисунке A, B, C). Тогда не только длина, но и строки, соответствующие циклам, тоже равны, но могут быть циклически сдвинуты, когда мы их нашли (именно здесь важно направление циклов). Кроме того, мы уже знаем, как выглядит такая строка из конечного прямоугольника. Поэтому нам нужно сравнить строки всех оставшихся циклов из данного прямоугольника с этой строкой, беря во внимание сдвиги как инвариант. Для каждой строки это можно сделать за линейное время, например, с помощью алгоритма Кнута-Морриса-Пратта. Когда для каждого цикла находим значение циклического сдвига, перестанавливаем ряды и столбцы по соответствию с конечным прямоугольником.

Время: O(n + m).

Память: O(n + m).

Реализация: C++, Java

Комментарий

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

Привет всем!

Раунд Codeforces #165 начнётся сегодня в 19:30 по Московскому времени, и будет проведён в обоих дивизионах. После долгого двухнедельного перерыва это первый раунд для участников Div I. :)

В этот раз задачи подготовили я, Евгений Вихров (gen), и Кришьянис Прусис (cfk). Кроме совместного участия в ACM ICPC в этом году, мы также коллеги по проекту с множеством алгоритмических задач. Некоторые задачи раунда появились именно во время работы над этим проектом.

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

Большое спасибо Геральду Агапову (Gerald) за помощь в подготовке раунда, Марии Беловой (Delinur) за перевод условий, а также Михаилу Мирзаянову (MikeMirzayanov) за великолепную платформу создания контестов на Codeforces — Polygon.

Мы желаем всем интересного раунда!

UPD1: Разбалловка задач:

DivII: 500 1500 1500 2000 2500

DivI: 500 1000 1500 2000 2500

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

Div I

1. PavelKunyavskiy
2. Egor
3. tourist
4. rng_58
5. tomasz.kociumaka

Div II

1. woxihuanni
2. mnbvmar
3. QLSpirit_011
4. PraveenDhinwa
5. leviathan

UPD3: Появился разбор.

Привет всем!

Сегодня в 19:30 по московскому времени состоится Codeforces раунд #142, который пройдёт в обоих дивизионах.

Задачи составляли я, Евгений Вихров (gen), и Андрей Вихров (andreyv). Мы оба — студенты Факультета компьютерных наук Латвийского университета. Это наш самый первый раунд на Codeforces!

Раунд нам помогал готовить Геральд Агапов (Gerald), а условия на английский язык по традиции перевела Мария Белова (Delinur). Большое спасибо! Отдельно хочется поблагодарить также Михаила Мирзаянова (MikeMirzayanov) за отличную систему подготовки задач Polygon.

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

Желаем интересного раунда!

UPD1: Разбалловка задач динамическая, однако задачи будут упорядочены в порядке возрастания предполагаемой сложности.

UPD2: По техническим причинам продолжительность контеста увеличена на 5 минут. Приносим извинения за неудобства.

UPD3: Разбор опубликован здесь.

Раунд завершён! В первом дивизионе все задачи покорились 5 участникам, во втором — первой 4-ке. Поздравляем победителей!

Div I

1. YuukaKazami
2. peter50216
3. kelvin
4. takaramono
5. Martin

Div II

1. coquelicot
2. llj_bash
3. kb.
4. niukuo
5. Petar

DivII A. Печеньки

Самый лёгкий способ решить задачу — сперва посчитать всю сумму чисел, и затем посчитать количество чётных разностей между этой суммой и каждым числом. Однако маленькое наблюдение позволит написать решение немного эффективней: помимо суммы (sum) посчитаем также, сколько среди данных чисел есть чётных (even) и нечётных (odd). Тогда, если сумма нечётна, то ответ — odd, иначе — even. Время O(n), память O(1).

DivII B. Шнурки и шестиклассники

Маленькие ограничения позволяют нам написать решение «в лоб». Будем хранить данный граф в матрице смежности, и симулировать происходящее. Также будем хранить степень каждой вершины отдельно, чтобы быстро находить детей, которые связаны только одним шнурком. Тогда при каждой итерации удаляем все вершины со степенью 1 и все грани, которые соединяются с этими вершинами; продолжаем до тех пор, пока не останется таких вершин. Ответом будет количество произведённых итераций. Время O(n³), память O(n²).

DivII C / DivI A. Статуи

Произведём симуляцию падения статуй. При каждой итерации будем сдвигать все статуи на одну клетку вниз. Перед каждым ходом (итерацией) будем получать список всех полей, куда Маша может пойти (до того, как статуи передвинутся на одну клетку вниз), используя список тех полей, куда она могла придти с прошлого хода (единственное, из полей с прошлого хода можно использовать только те, в которые после конца прошлого хода не переместилась статуя). Логично, что через 8 любых ходов на доске не останется ни одной статуи. Поэтому, если список  доступных Маше полей после 8-ого хода не пуст, то она может добраться до Ани, потому что дальше её ходы ничто не ограничивает. Время O(9· 8³) = O(1), память O(8²) = O(1).

DivII D / DivI B. Строка

Вначале ликвидируем случай невозможности — такой строки нет, если k больше, чем количество подстрок, т.е. , где n — длина строки.

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

Далее, используя найденную информацию, не сложно выяснить, с какой буквы будет начинаться нужная подстрока (потому что в слове при лексикографическом сравнении буквы слева важнее, чем буквы справа). Теперь заметим, что тоже самое рассуждение мы можем применить и для следующей буквы нужного слова, только теперь нужно проверить только такие буквы, которые следуют после первой буквы слова. Таким образом, мы повторяем итерации и для 3-ей, 4-ой, ... букв до тех пор, пока не найдём нужную строку. Чтобы не искать каждый раз нужные позиции, будем хранить их отдельно; при каждой итерации сдвигать их на одну позицию направо и исполнять алгоритм только для них, а после нахождения i-того символа убирать те позиции, буквы в которых не равны с найденным символом. Время благодаря k ≤ 10⁵ не квадратичное (самому ещё не получилось доказать), память O(n).

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

DivII E / DivI C. Игра с прямоугольниками

Рассмотрим все левые и правые границы всех k внутренних прямоугольников, вместе их 2k. Присвоим им произвольные 2k координат между левой и правой стороной данного прямоугольника, это можно сделать способами. То же самое сделаем и с верхними и нижними границами, это можно сделать способами. Заметим, что каждая пара таких размещений однозначно определяет одно искомое расположение, и все такие расположения можно определить одной парой размещений. Поэтому ответом является . Так как n и m не больше 1000, то коэффициенты можно посчитать с помощью треугольника Паскаля (не забывая вычислять по данному модулю). Время O(max(n, m)²), память O(max(n, m)²).

DivI D. Числа

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

Пусть у нас есть числа a, a + 1, ..., b, тогда количество связей у них 2|a|, 2|a + 1|, ..., 2|b|, где |x| — количество чисел x. Ясно, что 2|a| связей от 2|a + 1| «съедают» элементы a. У a + 1 свободными остаются p = 2|a + 1| - 2|a| связей. Аналогично, эти p связей соединяются с a + 2 элементами и т.д. В конце концов, если у b - 1 свободными остаются q связей, то должно быть q = 2|b|, чтобы завершить цепочку. Остаётся только проверить все эти соотношения (учитывая то, что цепочку нельзя завершить раньше, чем не истрачены все связи — то есть, вычисляемый p не может быть 0). Время (т.к. данные числа нужно отсортировать), память O(n). Для простоты вычислений можно ещё заметить, что 2|a| можно заменить на |a|, из-за этого ничего не изменится.

DivI E. День рождения

См. хороший разбор здесь.

A. Учет энергопотребления

В этой задаче всего-навсего нужно было имитировать работу ноутбука. Будем записывать результат в переменную res. Для каждого интервала прибавим к res число (r_i - l_i)· P₁, т.к. во время интервалов ноутбук работает на полную мощность. Обозначим функцию
int foo (int &m, int t) {
      if(m < t) t = m;
      m -= t;
      return t;
}
Далее для каждого i < n к res применим следующие действия: пусть время между концом i-ого и началом (i + 1)-ого интервалов — tmp. Тогда прибавим к res . Переменная res и является ответом задачи.

Думал, что программа запорется на крайних тестах. Оказалось, ошибочно думал — AC.

B. Кассир в кинотеатре

Сразу начал искать какой-нибудь быстрый алгоритм, на это потратил какое-то время. Потом подумал —"а зачем?" и написал bruteforce.

Алгоритм простой до безобразия и без оптимизаций (). Идём по всем возможным позициям x, y, если все выбранные места не заняты, считаем данную в задаче функцию для выбранных чисел, минимум вместе с координатами фиксируем в переменную. AC с первого раза.

C. Цифровой корень

Математика, обрадовался я. Известный факт, что . Заметим, что для задачи не важно, d(x) = 9 или d(x) = 0: в принципе это одно и то же. Поэтому можем упростить: .
Посчитаем, сколько троек чисел удовлетворяют Васиному условию. В массиве A[9][9] : чтобы знать значение d(i· j). В массиве B[9] B[i] — количество чисел, не больших n, которые дают остаток i при делении на 9. Итак: для каждых i, j количество искомых троек таких, что d(i· j) = d(l), является B[i]· B[j]· B[A[i][j]] (все эти тройки удовлетворяют Васиному суперусловию). Складывая все эти числа, получаем искомое (X).
Теперь посчитаем, сколько троек Вася найдёт правильно своим условием. Подумаем: ведь это те и только те тройки A, B, C, которым выполняется A· B = C ≤ n. То есть, произведение A и B не более n. Как найти это количество? Очевидно, что как A  и B годятся все числа 1 и i, i ≤ n. Так же годятся все числа 2 и i, . И так для каждого i как A годятся все числа B, которые не больше . Вся их сумма — искомое количество (Y).
Ответ — X - Y. Ну, думаю, сейчас уж не прокатит третий раз с первого раза. И внезапно — AC. Ну тут я обрадовался.

Посмотрел на задачи D и E. Вижу, почти никто D не решил. Однако всё-таки посмотрел, подумал, что DP, подумал, что уже раньше что-то подобное видел. Но писать что-то уже было влом, да и наверное, беcперспективно, раз даже лидеры не решили. В E тоже особенно не вдумывался. Поняв, что за полчаса не решу ни одну из этих двух задач, на этом и закончил. Впечатления: хороший контест, особенно понравилась задача C.

Ну, к определённому успеху я пришёл — поднялся с Сержанта (1466) до Лейтенанта (1610): +144. Ну что, отлично.