Автор RussianCodeCup, 9 лет назад, По-русски

Всем привет!

В это воскресенье 31 мая в 13:00 по Москве состоится третий квалификационный раунд Russian Code Cup. Раунд продлится 2 часа. По итогам раунда 200 лучших выйдут в отборочный раунд, где сразятся за выход в финал.

Третий раунд — последний шанс для тех, кто еще не успел пройти квалификацию, так что не пропустите! Отборочный раунд состоится в 13:00 14 июня, в него проходят 200 лучших участников из каждого квалификационного раунда.

Для того чтобы принять участие в Russian Code Cup, нужно зарегистрироваться на сайте http://russiancodecup.ru/ (регистрация будет открыта до начала третьего квалификационного раунда).

Подробнее о чемпионате, правилах и призах и читайте на сайте http://russiancodecup.ru, по всем вопросам обращайтесь на russiancodecup@corp.mail.ru

Приглашаем всех принять участие в квалификационном раунде Russian Code Cup и желаем всем удачи!

  • Проголосовать: нравится
  • +65
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится +40 Проголосовать: не нравится

Ну покажите какая будет футболка :) Интересно же.

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +129 Проголосовать: не нравится

    Вот такие футболки получат лучшие 200 участников отборочного раунда.

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится +169 Проголосовать: не нравится

      А я так и не освоил Фенвика. Интересно, в такой футболке можно будет ходить на соревнования, куда с распечатками нельзя.

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится +42 Проголосовать: не нравится

      А Вы сами готовы ходить в такой футболке в приличном месте? :(

      • »
        »
        »
        »
        9 лет назад, # ^ |
          Проголосовать: нравится +12 Проголосовать: не нравится

        А что не так с футболкой?

        • »
          »
          »
          »
          »
          9 лет назад, # ^ |
            Проголосовать: нравится +23 Проголосовать: не нравится

          Длинная надпись на груди девушек не будет полностью видна =)

          Белый цвет быстро пачкается.

          Возможно, стоило бы поменять местами принт спереди и сзади.

          В любом случаи код на футболке, в качестве главной темы, а не фона выглядит крайне задротски для людей со стороны. Это конечно "1 + 1 = 10", но не сильно далеко ушло.

          • »
            »
            »
            »
            »
            »
            9 лет назад, # ^ |
              Проголосовать: нравится +14 Проголосовать: не нравится

            1 + 1 = 10 — классно! меня много детей спрашивали, как это может быть.

            а на код никто даже внимания не обратит — напечатана фигня какая-то мелким кеглем, да и все.

          • »
            »
            »
            »
            »
            »
            9 лет назад, # ^ |
              Проголосовать: нравится +42 Проголосовать: не нравится

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

          • »
            »
            »
            »
            »
            »
            9 лет назад, # ^ |
              Проголосовать: нравится +40 Проголосовать: не нравится

            выглядит крайне задротски для людей со стороны

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

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

          • »
            »
            »
            »
            »
            »
            9 лет назад, # ^ |
              Проголосовать: нравится +15 Проголосовать: не нравится

            не знаю по-задротски это или нет, посмотрел по сторонам — вокруг никого..

»
9 лет назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

very nice shirts, especially on the left side of the shirt, shirts will be able to gain

»
9 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Баг: не могу выполнить вход на сайт. Вход на cups.mail.ru проходит успешно, когда захожу на RCC — не залогинен

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится -8 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

А зачем мне по почте пришло приглашение принять участие в третьем раунде, если я уже прошел в отборочный раунд ранее?

»
9 лет назад, # |
  Проголосовать: нравится +19 Проголосовать: не нравится

Как решать D?

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +36 Проголосовать: не нравится

    Будем решать задачу с конца.

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

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

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +9 Проголосовать: не нравится

    Построили граф где вершины это кнопки. Для некоторых пар кнопок однозначно задается кто из них идет раньше. Сделали топологическую сортировку, для каждого суффикса проверили в лоб приводит ли такая последовательность к ответу. Если нашли, то вот он ответ, а иначе NO.

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится

      однозначно задается кто из них идет раньше

      Можно подробнее, пожалуйста?

      • »
        »
        »
        »
        9 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      9 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

      А компоненты сильной связности ни на что не повлияют?

      Рассмотрим тест:

      5 4
      10111
      1 10110
      1 11000
      0 11000
      1 00001
      

      Выходит, что есть ребро из 2 в 3 (из-за второй лампочи; индексация с 1), из 3 в 2 (из-за первой) и из 3 в 1 (тоже из-за первой). Вроде бы больше никаких ребер нет.

      Рассмортим "топологическую сортировку" (тут есть компонента сильной связности, не уверен что этот термин можно юзать) 4 3 2 1. Вроде бы нет суффикса, который включает то что нам нужно, а вот решение есть — кнопки 4 и 1 в любом порядке.

      Надеюсь, нигде не натупил.

      • »
        »
        »
        »
        9 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится -20 Проголосовать: не нравится

Нашел на последних минутах баг в С, отправил. Потом пока ждал результаты тестирования нашел такой же в другой части кода, переотправил. Зашло. 211 место...

»
9 лет назад, # |
  Проголосовать: нравится +65 Проголосовать: не нравится

У кого-то была следующая проблема? Сижу, смотрю на таймер обратного отсчета перед раундом: 12..., 11..., 10..., 0 -> нажмите, чтобы увидеть задачи. Думаю: странно, что после 10 сразу 0. Ну ладно, что-то наверное рассинхронизировалось, не важно, сейчас уже начался контест. Я открываю задачи по любезно предложенной Мейл.ру ссылке. Решаю первую, напишу код, нахожу ошибку, исправляю, хочу отправить и ... не могу найти кнопку "отправить решение". Выяснилось, что Мейл.ру дал мне ссылку на условия второго квала. Итого первые десять минут я решал совершенно другой контест. Распознать подставу я не смог, так как второй квал не писал.

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +9 Проголосовать: не нравится

    Хорош, поздравляю, у меня тоже так было

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    Было, материсля после того, как уже посылку по задаче сделал с решением другой задачи.

»
9 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Как решать Е?

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    Поймем, что ответ — это прямая посередине между двумя параллельными прямыми, на которых лежат искомые точки. Делаем прямые, сортим их по (a,b,c), дальше проходимся смотрим кол-во одинаковых троек (a,b,c). По ним определяем кол-во точек на прямой, Дальше смотрим на группы с одинаковыми (a,b) — берем два максимальных значения — сумма точек на этих прямых и будет ответом, ну и так для всех пар (a,b).

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Спасибо! Я тоже так делал, но WA 2. Где-нибудь есть тесты?

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      Важно отметить, что "одинаковых троек (a,b,c) с точностью до множителя" и "с одинаковыми (a,b) с точностью до множителя". Тройка (1, 1, 1) и (-3, -3, -3) дают одинаковые прямые.

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

how can solve E?

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Есть ли у B другие решения, помимо динамы по сумме и количеству цифр?

  • »
    »
    9 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится -8 Проголосовать: не нравится

    Я такое сдал: посмотрим на цифровой корень числа А, тогда заметим, что каждое последующее число имеет цифровой корень на 1 больший предыдущего, а когда у числа (A + i) цифровой корень 9, то у числа (А + i + 1) цифровой корень -- 1.

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится -16 Проголосовать: не нравится

      А как объяснить эту последовательность?

      • »
        »
        »
        »
        9 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится -10 Проголосовать: не нравится

        По индукции. База: утверждение очевидно работает для чисел от 0 до 10. Переход: при увеличении числа на единицу сумма чисел также увеличивается на единицу. Эта сумма и будет цифровым корнем. Даже если сумма состоит из двух и более цифр, ее цифровой корень по индукции также увеличится на один в кольце 1..9. Исключение: числа с k девятками на конце, их сумма уменьшится на k*9 и увеличится на 1, что в кольце 1..9 даст то же, что и прибавление единицы.

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +32 Проголосовать: не нравится

    Цифровой корень — это остаток по модулю 9.

    • »
      »
      »
      9 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится -8 Проголосовать: не нравится

      Если точнее, это 9 для чисел, кратных 9 и остаток при делении на 9 — для некратных.

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    Заметим что на отрезке длины кратной 9 всех цифровых корней поровну(т.к. цифровой корень это остаток при делении на 9). Если длина отрезка не кратна 9, сдвинем левую границу, пока длина не станет кратна 9, пересчитывая число остатков(мы его сдвинем не более 8 раз)

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Вот без динамики: http://pastebin.com/vBtvhXis

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Я был 127-ом месте, теперь я не в рейтинге, почему. Обычно когда списывают или дают на списывание так делают но я такого не делал

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

А как задачу С решать? Я сделал цикл до z / 24 дней, но свалилось по TL. Может там точка пересечения максимум 1 может быть? Или их какое-то ограниченное число и поэтому цикл не нужен?

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    А как ты решал? Я шел от 1 до z и для каждого часа честно подсчитывал то, что просят. Можно было и умнее, но там и такое заходит

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      хм, интересно тогда. Может дело в Java и считывании обычным Scanner'ом? Вообще я все подсчёты вёл в double, может можно было обойтись целыми числами? Но мне показалось, что нет

      • »
        »
        »
        »
        9 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Моя C на C#. С простым проходом по всем z: http://pastebin.com/8ieWSnA0

      • »
        »
        »
        »
        9 лет назад, # ^ |
          Проголосовать: нравится +11 Проголосовать: не нравится

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

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Во-первых можно построить график движения второго относительно первого.

    Пусть a = a2 - a1, b = b1 - b2. Тогда график, который начинается в нуле и поочередно возрастает на отрезке длины 12 на a и убывает на отрезке длины 12 на b является графиком движения второго относительно первого. Время, когда первая улитка выше — это длина отрезков оси, под которыми лежит график. Тогда рассмотрим отдельно дни и ночи: пусть в i-ый день под графиком было di, а в i-ую ночь под графиком было ni. Несложно заметить, что di и ni — арифметические прогрессии (до тех пор, пока функция не перестает менять знак окончательно). Действительно, каждые сутки график сдвигается на одно и то же значение: разность b и a. Поэтому сумму di и ni можно посчитать за O(1), или чуть проще за . Главное, аккуратно всё посчитать, что к сожалению у меня не вышло во время контеста

    Вот код, зашедший в дорешке.

    P.S. Нужно внимательнее читать ограничения

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Два решения: WA 11371933 и AC 11371926 Различие только в том, что в первом вывод делается так:

    cout << res << "\n";
    

    а во втором так:

    cout.precision(10);
    cout << fixed << res << "\n";
    

    В итоге первый код выводит например 1.333, в то время как второй 1.3333333333. Это нормально вообще? Почему он в первом случае выводит так мало знаков после запятой?

    • »
      »
      »
      9 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится +6 Проголосовать: не нравится

      Ну просто у cout по умолчанию точность вывода вещественных чисел низкая.

      • »
        »
        »
        »
        9 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Спасибо, понял. Просто в джаве оно по умолчанию выводит много знаков после запятой )

      • »
        »
        »
        »
        9 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Хотя нет, в случае AC там просто добавилось fixed, строчка с выставлением precision'a закоменчена.

»
9 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

Хотел спросить (возможно это где-то оговаривалось), сертификаты будут высланы на электронную почту или же как — то иначе?

  • »
    »
    9 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    А он нужен?

    Я надеюсь, что организаторы еще раз прислушаются к мнению участников и добавят еще 400 футболочек, чтобы не обидно было — "̶а̶в̶т̶о̶м̶г̶о̶д̶у̶б̶ы̶л̶о̶6̶0̶0̶"̶ "автомгодубыло800"

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

А кто-нибудь в курсе, следует ли какой-нибудь job offer по окончанию RCC? Если да, то какое место надо занять, чтобы его получить?

»
9 лет назад, # |
  Проголосовать: нравится -27 Проголосовать: не нравится

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

A,B — легкие (только мне как обычно надо внимательно читать условия и не писать как обычно int где нужен long)

C — почасовое моделирование зашло сразу (хотя и нудятина... 12 условий по расчету — день/ночь, кто выше при равной скорости, итп)

D — самая сложная для меня задача раунда, идею понял только когда разбор прочитал и то не сразу

E — интересная задача с математики — "количество одинаковых троек" в лоб дает TL — порядка 500000 прямых надо сравнить попарно — для каждой прямой Ax+By+C можно сразу просчитать расположенные на ней точки подстановкой и затем уже ее повторно не трогать, и нормировать (привести либо к A=1, либо к A=0, B=1). Ну и частные случаи: для числа n<=3 ответ всегда n, для всех точек на одной прямой ответ тоже n