company_banner

Разбор задач четвертого квалификационного раунда Russian Code Cup 2014



    В воскресенье, 1 июня, прошел четвертый, заключительный, квалификационный раунд Russian Code Cup 2014.

    На участие в раунде зарегистрировалось 5428 человек. Как минимум одно решение прислали 730 участников. Всего за раунд было прислано 4793 решения, из них правильных — 1531.

    Больше всего решений на GNU C++ — 1786.
    Решений на Python — 307, из них правильных 86.
    Решений на PHP — 93, из них правильных 15.
    Решений на Perl — 6, из них правильных 2.

    Первым задачу А решил Филиппов Дмитрий (DimaPhil) за 2:42 минуты, он же первым решил и задачу В за 12:09. Задачи С и D первым решил Обедников Александр (AOb) на 12:25 и 37:44 минуте соответственно. Первым задачу Е решил Фефер Иван (Fefer.Ivan) на 45:22 минуте. Иван также первым справился со всеми задачами за 1 час 8 минут. Всего 5 задач решило 12 человек. 10 участников были дисквалифицированы судьями.

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

    Задача А. Соцопрос
    Идея: Андрей Станкевич
    Реализация: Николай Ведерников
    Разбор: Николай Ведерников

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

    Так как по условию задачи её решат только те, кому она не противна и умеют решать, то количество тех, кто попытается решить задачу, будет равен или менее nb. То есть если среди всех, кто попытается решить задачу, будут те, кто это умеет, то это будет максимум из тех, кто решит. Это min(a, nb).

    Минимум же достигается, если все, кому противна задача, будут уметь решать задачу, тогда ответ max(0, ab).

    Задача B. Сто
    Идея: Виталий Аксёнов
    Реализация: Павел Кротков
    Разбор: Павел Кротков

    Решением задачи является программа, аккуратно рассматривающая несколько несложных случаев. Самым простым случаем является ситуация, когда количество цифр в числе x равно k+1. В этом случае необходимо вывести −1, если число не содержит ни одного нуля, и ноль — если в числе присутствует хотя бы один ноль.

    Если же количество чисел в числе x превышает k хотя бы на три, эту ситуацию необходимо обрабатывать более аккуратно. Найдем в числе второй ноль с конца. Убедимся, что за ним стоит не более, чем k+1 цифра. Вычеркнем из числа все ненулевые цифры, стоящие за вторым с конца нулем, а также вычеркнем необходимое количество цифр, стоящих сразу перед вторым с конца нулем. Заметим, что первая цифра никогда не вычеркивается, а значит, в итоговом числе не будет ведущих нулей.

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

    Задача C. Поход в гости
    Идея: Георгий Корнеев
    Реализация: Борис Минаев
    Разбор: Борис Минаев

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

    Задача D. СНМ
    Идея: Артем Васильев
    Реализация: Артем Васильев
    Разбор: Артем Васильев

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

    Хоть массив rank и не задавался во входных данных, легко понять, что без сжатия путей ranki — это высота поддерева с вершиной i в корне. Также отметим, что алгоритм устроен так, что ranki каждый раз увеличивается не более, чем на единицу, а после того, как вершина подвешивается к другой, ее parent и rank не изменяются, поэтому можно строить от листьев к корню.

    Рассмотрим поддерево с корнем в вершине u. Если ranku = r, то у вершины u должны существовать дети с рангом 0, 1, ..., r-1. Легко показать, что это условие является достаточным: если провести операции union в порядке увеличения ранга сына, все операции пройдут корректно.

    Отсюда следует решение для одного дерева:

    1. Рекурсивно построим решение для всех детей корня дерева.
    2. Проверим, что для всех h от 0 до rankroot — 1 существует сын с рангом h.
    3. Проделаем операции union(root, childi) в порядке увеличения ранга childi.

    Также возможно реализовать СНМ и непосредственно проделать все операции, проверив, что получившийся массив parent совпал с нужным.

    Время работы решения — O(n log (n)).

    Задача E. Нанороботы
    Идея: Виталий Аксёнов
    Реализация: Андрей Комаров
    Разбор: Андрей Комаров

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

    Будем решать эту задачу при помощи динамического программирования. Обозначим за dp[w][x][y] минимальное число шагов, за которое можно довести робота массой w из клетки (x, y) до финальной клетки (n, m). Начальные значения dp[w][n][m] = 0 говорят о том, что из целевой клетки идти никуда не надо. После того, как dp будет посчитано, ответ будет содержаться в ячейке dp[w][1][1].

    Научимся считать dp. Чтобы посчитать dp[w][i][j], сделаем одно из двух:

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

    Чтобы не было проблем с пониманием того, в каком порядке считать значения динамики, можно считать её лениво. Итоговая сложность алгоритма: O(w2n2m2).
    • +22
    • 6,2k
    • 7
    Mail.ru Group
    1018,00
    Строим Интернет
    Поделиться публикацией

    Комментарии 7

      0
      Вот я всегда, еще со школы, когда имел дело с/слышал об олимпиадах по информатике/программированию не мог понять одну вещь: кому в реальной практике приходилось хоть раз вычислять задания, подобные конкурсным? Нет, я согласен — аналитическое умение и математика в программировании только в плюс. Но и без них можно быть замечательным разработчиком любого уровня. Иначе надо идти в ученые, а не программисты (ученые ведь тоже кодят, но на каких-нибудь Scala).

      Просто никогда не мог понять людей, занимающих первые места на олимпиадах по программированию, но не понимающих разницу между полиморфизмом и перегрузкой.
        0
        У меня такое ощущение, что подобные задачи вылезают всё время, причём там, где их не ждёшь. То неожиданно возникнет транспортная задача (хотя работа шла над совмещением изображений), то реализация кучи структур в ограниченной памяти, то оптимальным решением оказывается какая-то динамика…
        А чтобы объяснить разницу между полиморфизмом и перегрузкой, нужно, хотя бы, знать, что под ними понимается в этом десятилетии. Для решения задач это знание, пожалуй, ни к чему — если термин встретится в умной книжке, то его смысл можно понять и по контексту, а где он может попасться ещё? Неужели в разговорах в курилке?
          0
          А вообще, Вы, конечно правы. Можно стать разработчиком любого уровня — при условии, что вы не будете браться за задачи, требующие для решения использования аналитики/математики на уровне, соответствующем олимпиадному. Сейчас и других задач много.
            0
            Что в вашем понимании соответствует олимпиадному и насколько часто они встречаются? Программирование термоядерного реактора? Так это ученые. Логистическая система или игры? Ну, да. Однако это процентов 20% от всех задач в обычной работе на мой взгляд. Тогда как знание ООП требуется всегда и постоянно.
              +1
              Если бы это было 20%, то каждая пятая задача требовала бы олимпиадного подхода, и большинство программистов встречались бы с ними регулярно. Тогда бы и вопроса «бывают ли такие задачи» не возникало. И думаю, что 30-40 лет назад ситуация была примерно такой.
              Мне кажется, что более близкая к реальности оценка — 3% (что примерно соответствует количеству задач, в которых Дейкстра разрешает предварительную оптимизацию — впрочем, множества этих задач совпадать не обязаны).
              Но делать такие оценки и обобщения в мире, где программистами считаются все от пишущих коды для ПЛИС до работающих в HTML, довольно опасно. Наверное, ООП действительно нужно всегда, но оно может принимать такие формы, что его будет очень сложно узнать.
          0
          --редко, но бывает нужно

          польза от таких задач — расширяют сознание.
            +1
            Это примерно то же, что и сказать, что обучение школе в течении 11 лет закладывает какие-то там основы и дает знание на будущее, хотя все нужные знания можно получить в течении 3-4 лет без испорченной молодости и нервов. Расширение сознания само по себе бессмысленно, если только этим и заниматься.

            «Теория — это когда все всё знают, но ничего не работает. Практика — когда никто ничего не знает, но всё работает.»

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

          Самое читаемое