Блог пользователя EG0R

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

11-13 октября 2013 года будет проходить южно-восточный европейский полуфинал мира студенческой олимпиады с программирования ACM-ICPC. Уже во второй раз олимпиада пройдет в он-сайт режиме в двух университетах:

  • Бухарестский политехнический университет\ Румыния
  • Винницкий национально технический университет\ Украина

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

Так же можно посмотреть онлайн видео-трансляцию здесь

От себя пожелаю командам удачи, и пусть победит сильнейший.

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

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

Есть ссылка на работающий монитор? Традиционно для SEERC — тотальное убожество, на сайте правила с 2011 года, неправильный список команд и остальные похожие приколы, и даже в адресе, по которому должны быть онлайн-результаты, ejudge/seerc2011.html тонко намекает... Хотя если поменять на 2013 — все равно не работает.

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

В связи с тем, что на задачах SEERC-2013 будет проведён Гран-При Южной Европы, просьба к участникам не обсуждать задачи до окончания Гран-При.

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

Если кто-то уже знает, то напишите, пожалуйста, кто прошел.

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

    Если квота 3 команды, как в прошлом году, то SobolevTeam, BZFlags и Phantom Menace.

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

Подскажите, как решать B?

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

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

    Если новые ребра дороже, то пустим бфс по старым) Ну там очевидно, что если мы отсортим списки смежности для новых ребер, то можно проверять наличие/отсутствие старого ребра в bfs простым указателем. Ну как-то так) Понятно, что если новые ребра дороже, то ответ это минимум из цены минимального пути исключительно по старым ребрам и цены одного нового ребра — лучший ответ будет состоять или исключительно из старых ребер, или из одного прямого нового ребра 1->n.

    Навешал туда каких-то костылей и break-ов и оно зашло. Ну еще у нас для N<4000 обычный Дейкстра.

    Ну и да, мне тоже интересно услышать авторское решение.

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

      Мы решали так же, только без брейков и костылей :-D

      Не зашло по времени :)

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

        Ну там БФС по старым рёбрам нужно ещё уметь за O(n+m) написать, ведь старых рёбер может быть O(n^2), что не заходит.

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

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

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

          Можно подробнее, как его написать за n+m? Я умею только обычный bfs, в котором m — это как раз О(n^2).

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

            Будем поддерживать сет активных вершин. Изначально в нем все вершины.

            На полном графе без M ребер когда пробуем пойти по ребру, происходит одно из двух событий — либо удалили вершину из сета, так как мы ее добавили в очередь и не нужно туда приходить второй раз, либо попробовали пойти по одному из тех M ребер. В итоге таких событий N + M, ч.т.д.

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

            Я как делал:

            Заведем множество интересных вершин (которых мы ещё не достигли), положим в него вершины [2,n].

            Окей, пустим БФС.

            Допустим, мы находимся в какой-то вершине u.

            Отметим все вершины, в которые есть ребро из u.

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

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

            Код: http://pastie.org/private/nndowmwfhstrmvw6iympgq

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

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

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

                Ну когда элемент попадает туда? Когда было ребро. Ребер m :)

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

    Мы написали дерево отрезков со следующими операциями: Найти минимальный элемент, удалить элемент, установить значение элемента, для всех элементов на отрезке обновить значение a[i]=min(a[i], val). С помощью такой структуры можно написать честную Дейкстру на заданном графе за O(n * log n).

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

Какое у вас зашло H? (Red John Game)
Знаю прошедшие решения:
1. если делители только степень двух и степень пятерки;
2. если не делится на три;
3. является степенью двойки или делится на пять.

Есть ли нормальное решение, и как его доказать?

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

    Можно показать, что из прямоугольника 2x3 можно получить 1x3. Этой операцией можно свести к n-3. Для 4 и 5 строится пример. Почему для кратных 3 нельзя, не знаю.

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

      Раскрасьте доску в три цвета по выражению (x+y)%3. Тогда каждый ход меняет четность числа фишек каждого из трех цветов. В конце должны придти к 1-0-0, а изначально при n%3==0 всех трех цветов поровну (т.е. и одной четности в том числе).

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

        Понятно почему нельзя кратные трем, но есть ли доказательство того, что найдется какая-то тактика для остальных чисел?

        И интересно сколько же тестов было на задачу если прошли явно неверные решения, такие как описанное у меня третье решение. Да и первое решение тоже должно выдать неверные ответы на числах не кратных 2, 3 или 5.

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

          я же правильно понял, что уже n=7 приводит к различным ответам в 1,3 vs 2 ?

          upd: сами сдали n%3 != 0, нашли когда игрались с монетками и пришли к выводу, что ряд, длина которого кратна трем приводит к "выбросу", нестрого, но решили проверить... И вот как реджаджить такое? Нестрого доказали, проверили сабмитом, зашло — ок, верная догадка. Ведь далеко не все есть время доказывать. Особо памятуя прошлый проблемсет с out.println(m*l/n)

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

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

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

          Это задача мне известна в более общем виде — для прямоугольника, а не квадрата, и там единственный инвариант именно такой, как я сказал, за исключением какого-то крайнего случая прямоугольника со стороной 1 и, возможно, 2. Пример стратегии основан на убирании прямоугольников 1на3 до какого-то маленького случая, которые можно разобрать руками. Насколько я помню, эта задача есть на тимусе, а вообще она взята с какого-то древнего всероса по математике.

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

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

      Покрасим все клетки в три цвета по сумме координат по модулю 3. Ясно, что вначале клеток всех типов по 3n, а в конце какого-то типа 1, остальных типов 0. Поймем, что от каждой операции количество клеток каждого типа меняет четность (например, скачем клеткой 0 через клетку 1, получаем клетку 2, тогда для 0 и 1 уменьшается на 1, для 2 увеличивается на 1). Поэтому все количества должны всегда иметь одну четность. Противоречие.

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

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

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

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

Ах, да — авторы С — за чтение в бинарном формате — горите в аду!

P.S. Мы ее все таки сдали с +11

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

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

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

      Для Румын это нормально давать такое на контест. Год за годом появляются новые места где можно сломать ногу ...

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

    +21, упорно сдавал то на плюсах, то на джаве. В итоге зашло рукописное чтение на джаве(через байтовый буфер и сдвиги) вместо DataInputStream. Просвятите, как на плюсах по-человечески должно быть чтение, а то за 0,5ч поиска не нашел

    • »
      »
      »
      11 лет назад, # ^ |
        Проголосовать: нравится +6 Проголосовать: не нравится
      freopen("H.IN","rb",stdin);
      int someVar;
      fread(&someVar,4,1,stdin);
      

      Такое считывает из бинарного файла один инт в переменную someVar. Подробнее здесь: http://www.cplusplus.com/reference/cstdio/fread/

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

        спасибо, а то ушел гуглить в сторону fopen и fscanf и зарылся

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

        Такой вопрос — там вообще был макстест? Как я понимаю, в этом тесте надо будет считать 10000*10000*4 байт — 400 мб инпута. В моем представлении, скорость доступа к типичному среднестатистическому винчестеру физически не позволяет это сделать за 2 секунды. За 4 — поверю. За 2?.. SSD какие-то?

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

          Более того, мы файл вообще два раза считывали — прошло.

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

          Я тестировал локально на макстесте — чтение отрабатывает за 0.16мс. Винт не ссд.

          Upd: но это видимо не совсем честный эксперимент, так как данные в кеше оседают.

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

          Ввод-вывод обычно не учитываются в user-time, по которому выставляется TL. Т.е. реальное время работы скорее всего будет дольше 2 секунд, но от процессорного времени чтение почти ничего не съест.

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

            Да ну? А зачем тогда придумали scanf вместо cin?

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

            Все тестирующие системы которые я знаю меряют usr+sys время. А считывание это как раз sys.

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

        Мы тоже так пытались, но на контесте в man freopen прочли, что идентификатор "b" игнорируется в UNIX подобных системах.

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

А как решалась задача G?

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

    Динамика dp[i][q]. Где i-текущий номер цели, а q принимает такие значения:

    • 0, если i-я цель не входит в наш выбор,
    • 1, если она входит, но её сосед слева не входит,
    • 2, если входит и она, и её сосед слева.

    Вначале d[1][0] = 0, dp[1][1] = a[1], остальные -INF (если нумеровать с 1).

    Зная dp[i][q] несложно вычислить dp[i + 1][j] для любого j.

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

      тоже решал dp, чуть по-другому описал сами состояния (может кому понятнее будет корректность)

      0 — предыдущая не входит, текущая — свободный выбор

      1 — предыдущая входит, текущая — свободный выбор — лишнее состояние, понял только когда дописал этот пост

      2 — предыдущая входит, текущую обязаны взять

      3 — предыдущая входит, текущую не можем взять

      Но было несколько AC очень быстрых, может проще что-то есть?

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

        По-моему, динамика несложная. Есть классическая задача про взрывоопасность, где надо ставить грузы друг на друга, чтобы никакие 2 опасных не были рядом. И количество вариантов этого считать. Чем-то похожи задачи, опытные команды могли накодить быстро.

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

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

          Классика на взрывоопасность разве не фибоначчи (модифицированные), без дп? Хотя тоже можно дп назвать.

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

            Ну, как-то так. Если просто сказать, что это Фибоначчи, то непонятно, почему. А если сказать, что ДП и объяснить через ДП, то всё понятно становится.

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

      У меня это же написано, дает ВА 3.

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

        У одной команды с нашей площадки тоже было что-то похожее. Не знаю, как сдавали, но сдали потом. Может, при переходах ошибка. Или просто скрытная бага.

        Если мы знаем dp[i][q] и хотим посчитать для i+1, то там такие переходы:

        • Если q = 0, то dp[i + 1][1] = max(dp[i + 1][1], dp[i][0] + a[i + 1])
        • q = 1, dp[i + 1][2] = max(dp[i + 1][2], dp[i][1] — a[i] + b[i] + b[i + 1])
        • q = 2, dp[i + 1][2] = max(dp[i + 1][2], dp[i][1] — b[i] + c[i] + b[i + 1])
        • для всех q — dp[i + 1][0] = max(dp[i + 1][0], dp[i][q])

        Ответ — максимум из dp[n][q] при всех q.

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

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

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

      У нас такая же фигня с пониманием была, долгое время боролись с WA3, пока не перечитали условие)) На самом деле странно, что авторы не прояснили это хотя бы в семплах.

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

        За фразу в формате инпута Follows the three integers, при том, что речь на самом деле идет не о трех числах, а о N тройках чисел, надо канделябром, простите.

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

      А я то думал почему у нас даже полный перебор падал на 3 тесте.

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

      Никак. На наш клар до конца контеста так и не ответили. Мы просто написали еще одно решение.

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

Какая сложность в І?

Я вспомнил прошлый этап, опять написал обычный N^3, оно опять прошло)

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

    Естественно на плюсах?:)

    UPD. Я могу к каждому OpenCup'у такой комментарий писать :)

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

    n^3/32 у нас, если я правильно вспомнил, что за задача

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

      Да все равно как-то больно много) Если подумать, то на самом деле у вас там N*(M+N)/32, нет? Ведь для запуска апдейта еще нужно, чтобы ребро было. С учетом разреженности графа — это важно.

      Ну и мои N*(N+M) — тоже не так уж и много, даже для полсекунды.

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

        N*M/32 ведь, откуда там N*(M+N)/32? 4*10^6 операция, все вроде бы четко.

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

          4*10^7. Хотя это не меняет сути дела)

          А разница между M и M+N в данном случае не столь значительна, чтобы обращать на нее внимание.

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

            Просто (N+M) — звучит как что-то, что дал нам дфс. Думал, там как-то не так написать можно.

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

              У меня идейно

              for i 1..n
               for j 1..n
                if edge(i,j)
                 for q 1..n
              

              Если хранить граф матрицей, то как раз и получается N*N+N*M. Да и топсортить ограничения позволяют тоже за квадрат. А если можно работать с матрицей — так зачем что-то придумывать?

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

      Давайте будем реалистами — 5000^3 / 32 == 3906250000 как это может зайти даже на плюсах за полсекунды?

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

        у нас на самом деле O(nm / 32) :)

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

          Не зря там ограничение на число ребер было..:)

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

        Давайте будем внимательнее, и заметим, что у тебя там два лишних нуля.

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

          Могу ошибаться, но N = 5000. Могу скринкаст выложить, где я возвожу это число в куб и делю на 32 :)

          UPD. Это все естественно только если сложность O(N^3)

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

            В данной задаче это не совсем правда, так как N^2!=M.

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

              Угу. А что это за алгоритм такой? Просто для I я умею транзитивное замыкание сделать за куб от вершин.

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

                Просто ДФС пускаем и в каждой вершине храним битсет достижимых из неё.

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

В E есть нормальное решение без рандома, эвристик и прочей ереси? =)

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

    Да. Нужно только доказать факт, что если в какой-то ячейке написано число (ax + by), то (x, y) = 1

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

      Ну, доказали. Разве пар (x, y) не очень много? Как найти среди них хоть одну взаимно простую?

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

        Решим диофантово уравнение, получим решения (x0 - at, y0 + bt). Найдем границы для t так, чтобы оба этих числа были неотрицательными. Дальше запустим алгоритм Евклида, который gcd(x0 - at, y0 + bt) преобразует в gcd(x, y + t). Теперь надо подставить возможные значения t и посчитать этот gcd. Если отрезок возможных значений t достаточно большой (больше, например, 200), то обязательно найдётся t, которое даст взаимно простое решение. Иначе просто переберем все возможные t и посчитаем для них этот gcd.
        P.S. бОльшую часть решения писали в BigInteger

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

          Если отрезок возможных значений t достаточно большой (больше, например, 200),

          Мне кажется именно это Миша и имел ввиду под магией.

          Мы сдали следующее. Будем считать, количество таких хороших t в обозначениях Kostroma. Легко посчитать количество комбинаций сnt(s), таких что a и b положительны. А теперь формула обращения мебиуса дает формулу .

          Правда писать не очень приятно — надо раскладывать S на множители. Правда основное время убилось не на это, а на не нужные BigInt'ы с java, на которой мы все пишем в разы медленнее.

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

            А __int128_t не пробовали? Там просто 64-битный компилятор есть.

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

          Дальше запустим алгоритм Евклида, который gcd(x0 - at, y0 + bt) преобразует в gcd(x, y + t).

          Расскажите, пожалуйста, как преобразовать? Не совсем понятно.

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

            Запускаем алгоритм Евклида для a и b, попутно преобразовывая x и y. Делаем такие операции: .

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

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

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

          Мы брали миллион пар с самым маленьким x, миллион с самым большим x и миллион случайных. Да и то до конца не были уверены, что зайдет.

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

Интересно, а почему в таблице OpenCup только одна команда Moscow SU? Остальные не решали?

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

    В Москве сегодня командная олимпиада школьников. Наверняка все ушли проводить.

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

Как доказать решение J?

UPD. Нагуглил.

Вытекает из

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

А как решать задачу D?

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

    У меня есть предположение, что там ответ небольшой, скажем, не больше 20. Тогда можно безидейное дп писать.

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

      А, то есть от циклов избавляем дополнительным параметром?

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

    Самый что ни на есть стандартный ретроанализ. Граф с 64^3*2 вершинами влезает в память, поэтому можно за O(n+m) было писать. А от циклов ретроанализ сам избавляется.

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

      Я подозреваю, что сложность задачи была не в написании ретроанализа (про ретроанализ есть на e-maxx кстати), а в инициализации графа + выигрышных и проигрышных позиций :) Мы посадили пару багов вида: король рубит ладью уходя от шаха и что-то еще. Было забавно, когда я не смог поставить мат в 2 хода на тест руками, и считал, что у нас есть еще баг, так как наше решение выдавало 2. ОК пришел как раз тогда, когда я увидел этот мат.

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

        Конечно, ясно, что просто BFS написать несложно :) И сам я с этими позициями порядка часа парился. Долгое время, помню, думал, что если на ходе ладьи королю стоит шах, то король еще может убежать. Ну и прочая подобная ересь.

        Но я не думаю, что автор вопроса хотел получить в ответ доскональный рассказ о том, как позиции строить :)

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

          Ну скорее всего да :) Просто написал свои ощущения от задачи

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

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

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

          http://e-maxx.ru/algo/games_on_graphs Тут про ретроанализ. Ничейные вершины могут быть, конечно. Но по условию ничья равносильна поражению, так что просто для таких позиций выведем 0.

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

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

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

В задаче А тысяча запусков Дейкстры с потенциалами должна заходить по времени, или надо что-то хитрее?

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

    У нас не заходило, зато зашла жадность.

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

    Мы делали так: смотрим на самую дорогую, пока еще пустую матрешку; допустим мы вложим в нее не самую большую из возможных, тогда что это нам даст? — ничего :) таким образом всегда пихаем в как можно большую матрешку в самую дорогую на текущий момент.

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

    Расскажите, пожалуйста, как решать Дейкстрой с потенциалами.

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

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

      Ответ на задачу — это покрытие такого графа вершинно-непересекающимися путями минимальной стоимости. Просто покрытие графа путями (минимальным количеством) ищется через максимальное паросочетание (построим двудольный граф с двумя долями размера n, где ребро (i, j) есть тогда и только тогда, когда в исходном графе есть ребро (i -> j) и найдем паросочетание в нем).

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

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

Когда-то раньше людям, которые проводят SEERC, вроде бы задавали вопрос про то, зачем ставят ТЛ по 0,5с и ответ был вроде бы в духе "серверов мало, участников много, чтобы все быстро тестировалось". Но я все-таки не могу понять, зачем, например, в задаче D стоял TL 1c, если у нее всего 2 теста?

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

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

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

    Стратегический вопрос: а почему нельзя переписать на плюсы прямо на контесте, если понятно, что решение на Java пихать и пихать?

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

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

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

        Мы переписывали. Я написал на Java и не смог даже нормально запустить у себя :) Переписать на С++ заняло 5-10 минут.

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

      В русских условиях разве не 1 секунда стояла?

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

Когда мы заполняли анекту Яндекса на регистрации SEERC в Виннице нам обещали дать 250 Gb на Яндекс.Диске. Кто-то получил их?