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

Автор ifsmirnov, история, 21 месяц назад, По-русски,

Закончился очередной этап кубка.

Как решать I нормально? Сначала думали, что это просто сесть и написать, потом оказалось, что следить за текущими картами в колоде довольно нетривиально.

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

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

Закончился этап. С удивлением обнаружил команду моих студентов с 4-мя задачами и временем последней успешной попытки на 1:27. Говорят очень математические задачки, много конструктивов — не придумывалось. Как вы думаете, правда?

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

    Да, так и было. Задачи были интересные, и очень хочется узнать решения задач. Хорошо было бы если опубликует разбор с авторскими решениями.

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

    Ну из задач, которые они не сдали, задача B (http://opencup.ru/files/ocg/gp8/problems1.pdf) — совершенно классическая задача на динамику по профилю, никакой математики. Так что хотя бы пять нужно было сдавать :)

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

      Да только она была предпоследней по сложности :-) Писать её было долго 40-50-60 минут (2 разные динамики нужны были) и после этого это могло получить тл, поэтому мы не стали её писать.

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

        Да, задача не супер простая, но как верно отмечает ниже PavelKunyavskiy, динамика там одна. Вторая получается транспонированием обеих матриц и заменой p на 100-p.

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

          (Чтобы это доказать, представим себе новые вершины в центрах квадратов старой сетки, и будем разрезать сверху вниз)

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

          Да я видел. Мы к этому не смогли прийти на контесте, не очень это очевидно.

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

      Нужно было хотя бы шесть сдавать! Я вот после того как понял, что слишком глупый, чтобы решать математику, сел и сдал две классические техники (B и I) :)

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

Рассакажите, как F решать, пожалуйста

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

    Необходимо и достаточно, чтобы p и q были взаимно просты и имели разную чётность.

    По одной координате мы должны получить ap + bq = 0, это a = kq, b =  - kp. По другой up + vq = 1, это какое-то линейное представление НОД, одно из которых можно найти расширенным алгоритмом Евклида.

    В этот момент стоит решить на бумажке какой-нибудь нетривиальный пример типа p = 2, q = 7 и понять, как связаны с ответом эти a, b, u и v.

    Спойлеры: код и длинный текст решения с доказательством минимальности.

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

      Мы воспользовались немного альтернативной идеей написать решение, которое пробует buben1 решений одного уравнения и buben2 решений другого, и проверить, что при изменении бубнов ответы не меняются.

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

        Да, так даже проще: несложно показать, что хватит перебора O(1) пар решений, близких к минимальным по абсолютной величине.

        Например, у команды Shanghai JTU Dreadnought, которая вскрыла эту задачу через 20 минут после начала, именно такое решение, и buben1 = buben2 = 11 (от -5 до +5).

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

Как решать C?

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

    TL;DR Курить сюда

    Если в кратце — задача про равенство элементов свободной группы. Надо понять что это за группа, и проверить как равенство в ней. В группе есть элементы степени 2, 3 и 5, значит она размера кратного 60. Можно доказать, что если взять любую группу и элементы, в которой выполнены эти соотношения максимального размера, то достаточно проверять равенство в ней (в одну сторону понятно, в другую это не совсем тривиальный алгебраический факт). На самом деле это группа изоморфна четным перестановкам длины 5.

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

    Еще есть магия от Egor и компании, которые долго подбирали и подобрали какой-то набор замен, каконинзирующий строку, если я правильно поняд. А так подразумевалось как гроб.

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

      Do you know how to prove that there are only 60 equivalence classes and not more?

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

        Well, at least i belive to wiki. We did something like that on algebra course. Some group counting with mormilizers and stabilizers. I don't remember exectly which. Also, we can recuce everything with length at least 14, so probably brute force can do it.

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

      «Магия от Egor и компании» — это я, на самом деле.

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

      00 →

      111 →

      0101010101 →

      011011 → 101010

      110110 → 010101

      10101 → 0110110

      010110101101 → 101101011010 и обратно

      Не спрашивайте, как это придумать и почему работает :)

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

        Мне не хватило преобразований 10101 -> 0110110 и 010110101101 -> 101101011010 :(

        Я полагаю, что ты сидел и выписал тождества на ноликах-единичках, которые выводятся из соотношений, данных в условии. Откуда берутся первые пять штук я понимаю, я к ним тоже пришел. Но вот чем мотивируются последние два мне непонятно, можешь все-таки для меня пояснить? (мне понятна эквивалентность, мне непонятно, почему именно они)

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

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

          Смотри, долгое время, пока я действительно делал всё на бумажке я сильно верил, что достаточно делать вообще только:

          10101 → 0110110 и обратно

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

          Кучу моих примеров это проходило.

          Потом пришлось 0110110→10101 чуть-чуть переформулировать на 011011 → 101010 и 110110 → 010101, что почти не меняет дела.

          Мне дали комп, я закодил и получил WA. Написал стресс-тест, увидел две вот те длинные строки, проверил на бумажке, что они не подходят под предыдущее предположение, поверил, что это последний особый случай — сработало :)

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

      Паш, как задача может предполагаться как гроб, когда в википедии по статье "задание группы" (!) черным по белому указана группа, описанная в условии? Сложность в задании вращений икосаэдра? Без обид, но мне бы совесть не позволила дать на тур настолько легко гуглящийся математический факт.

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

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

      UPD: только увидел, что в этой статье еще и эквивалентность A5 указана, значит, никакие вращения задавать не требуется. Решение вообще в десяток строк выходит :(

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

        Все-так онсайт имеет чуть больший приоритет, а там инета нет. К OpenCup я всегда больше отношусь как к образовательному и тренировочному контесту, по этому гуглить или не гуглить — выбор команды, и прокачивать скил гугления тоже не так плохо. Ну и было б из чего выбирать :(

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

          Все-так онсайт имеет чуть больший приоритет, а там инета нет. К OpenCup я всегда больше отношусь как к образовательному и тренировочному контесту, <...>

          Тут уже вопрос к snarknews, насколько он понимает, что некоторые проблемсеты готовятся из расчета на определенную аудиторию/правила, и что видение авторов (например, тебя), каким должен быть проблемсет, да и отношение к открытому кубку как к явлению может отличаться от его видения. Не уверен, например, что он согласится с твоим тезисом про тренировочность.

          Насколько я помню, когда на последнем гран-при Екатеринбурга попалась задача на алгоритм Шраера-Симса (какое совпадение, тоже алгебра :) ), snarknews был крайне раздосадован этим фактом.

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

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

            А про алгоритм Шраера-Симса... Между прочем был на одном вполне официальном соревновании (спойлер в предыдущих правках, не смотреть финалистам, отдельный привет Petr)

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

        А как ты догадался бы, что надо гуглить по словам "задание группы"? По многим другим словам не находится. Например, есть ли хоть один поиск по-английски, который даёт нужный результат?

        У нас на эту задачу осталось полтора часа. Мы пытались и решать, и гуглить. Гуглил сначала я по-английски, довольно долго, и ничего вразумительного не нашёл. Потом мы долго пытались решить сами, написали дфс, который нашёл классы эквивалентности для строк длины до 11 используя промежуточные длины до 23 (их кажется было 59 :)), но закономерностей тоже не нашли. Потом минут за 20 до конца _meshanya_ сел погуглить по-русски, и довольно быстро нашёл эту статью в Вики. Потом нужно было за 10 минут вбить вращения икосаэдра, что, как верно подметил PavelKunyavskiy, несколько расширяет сознание, да.

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

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

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

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

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

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

    Я нашел представление этой группы в перестановках 5, 6 и 10 элементов (т.е. подобрал такие перестановки x и y, что выполняются указанные в задаче равенства). Даже если бы группа была бесконечной, вероятность случайного совпадения перестановок у неравных строк только 4096^2/5!/6!/10! — малая величина, даже с учетом сотни тестов. Реально достаточно было представления в группе перестановок 5 элементов, но мы этого не знали.

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

      А можешь пояснить аргумент с вероятностью подробнее?

      Если бы скажем в этой бесконечной группе был элемент порядка, делящегося на 11, то вроде как эти перестановки не помогли бы его отличить от тождественного, так как у перестановок размера до 10 не бывает такого делителя порядка?

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

        Я об этом не подумал. Но обычно в бесконечных группах порядок либо маленький, либо бесконечный. Бесконечный порядок, конечно, порождает другую проблему — можно взять слово в степени НОК(2,...,10) и мы его не отличим от тождественного. Но жюри могло и не додуматься до такого плохого теста, а на случайных тестах все хорошо.

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

А как посмотреть условия див.1?

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

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

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

    У меня получилось сконструировать нечто подобное:


    Т.е. на каждом из n/2 шагов делается ребро сначала в 2 (на следующих шагах 3, 4 и т.д.), а затем змейкой поочередно соединяются вершинки: левая-правая-левая-правая... Доказать почему это будет верно не пытался, но AC
    Ссылка на фрагмент кода

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

      Можно выделить центр, скажем вершину номер 1. А все остальные нарисовать на окружности. Тогда все ваши циклы получаются поворотом картинки. И понятно почему они не совпадают и покрывают все ребра.

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

      Кажется это даже авторское решение. В целом, придумать явную конструкцию, так или иначе.

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

Как решать I?

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

Остальное уже дело техники.

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

    Да, всё так.

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

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

    Чтобы ответить на вопросы, нам нужно уметь понимать, какое максимальное число локомотивов может быть у заданного игрока, и какое максимальное число карт (цвет X или локомотив) может быть у заданного игрока.

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

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

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

F (рассказали выше, спасибо).

А у жюри было по H за куб решение, просто упростили?

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

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

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

      На миптовых сборах месяц назад была задача "Bus Stop" с контеста AimFund, в которой предлагалось посчитать математическое ожидание максимума равномерно распределенных случайных величин ξ1, ξ2, ..., ξn, где ξi ~ U[0, ti]. Ограничения были n ≤ 105, и никаких проблем с точностью дабла (там во всяком случае) не было, а там еще, между прочим, было преобразование Фурье.

      Я для своего решения умею объяснять, почему у него разумная абсолютная погрешность. Правило, к которому я пришел ещё на той задаче, заключается в том, что все интегралы должны быть в пределах от 0 до 1: тогда если мы посчитали коэффициенты многочленов без большой ошибки (в частности, если коэффициенты многочленов не растут экспоненциально), то интегрирование не добавит никакой ошибки (так как фактически интеграл будет линейной комбинацией коэффициентов многочлена с коэффициентами )

      Сегодня я вообще сдал решение за n5.

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

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

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

        Все-таки, на нашем контесте, проблемы с точностью у многих решений были.

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

      Ещё в H есть такой забавный момент, что из-за маленьких ограничений координат задачу можно сделать дискретной. Мы считали вероятность, что "второй максимум окажется на отрезке [x,x+1), и всего на этом отрезке будет k точек, и верно ли, что первый максимум на том же отрезке". Это дискретная задача. А дальше мы просто говорим, что матожидание первой из k точек это k/(k+1), а матожидание второй из k точек это (k-1)/(k+1).

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

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

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

Как решать нормально задачи C E и H? В задаче C E мы еле упихали тернарный поиск, а в H пытались численно брать интегралы, но получали WA2.

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

    А как решать С тернарником?

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

      Извините, опечатался. Задачу E, конечно же, про точки на прямой. Решение задачи C тоже интересно, но его уже написали вверху. :)

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

    Problem H: 1. First I divided the whole range into segments (sorted start/end ends of the segments) 2. Done numerical integration for all these ranges (adaptive simpson) 3. Now the question is how to compute the probability of x being the second maximum. 4. First run a loop to select the segment where this "second maximum" x belongs to (say i) 5. Run another nested loop to select the segment where the "first maximum" lies (say j) 6. Now run another loop through all the segments, if it is j, find the probablity for selecting number greater than x, if it is i, do nothing (it contributes dx of the integration), for other segments multiply the probability for selecting number less than x. 7. Sum these up to get the probability of x being on the i'th segment. (You need to divide by the length of i'th segment) 8. Multiply the sum with x to get the "expectation".

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

How to solve B?

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

Может кто-нибудь объяснить, почему в G (Div2) работает просто перебор случайных чисел (и даже простой цикл до 15000 с проверками доступности единицы на каждом шагу)? Ведь вероятность найти нужную вершину, из которой можно пройти в единицу, очень мала (всё же их аж 2^32 штук). А если переходы есть только между 3% вершин, то вообще невозможно. P.S. И как усиливает безопасность запрет использования модуля random в питоне? В кларе ответили, что запрет из-за того, что питон лезет в /dev/random, но как использование этого устройства может обойти проверки безопасности?

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

    В ejudge довольно строгие политики безопасности и запускаемый модуль получает минимум прав. В частности, при запуске Питона в secure mode обращение к /dev/random считается нарушением политик безопасности (прямое обращение к объекту извне контейнера, насколько я понимаю).

    Причём, что интересно, в ранних версиях Питона random был реализован как-то иначе и обращения к /dev/random не было.

    А ставить insecure на контест из-за этого не хочется.

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

      Можно тогда в этом случае предупреждать участника при помощи соответствующего сообщения? Насколько я помню, в Ejudge есть статус Security Violation, но при использовании random получается Runtime Error 1. Вот и сидишь, гадаешь, что сделал не так.

      Было бы здорово снять ограничение с /dev/random, но оставить все остальные меры защиты.

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

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

        События происходят на уровне "Интерпретатор увидел, что ему не удалось прочитать из /dev/random, после чего вышел с ненулевым кодом возврата". Примерно то же бывает, когда по ошибке сишный код отправляется на Питоне.

        Более того, если включить SV (enable_violations), то программы на Питоне вообще не будут запускаться — пытается открыть /dev/random любая(!) программа на Питоне в момент запуска.

        Что касается "снять ограничение с /dev/random" — там не пофайловое ограничение, там просто не открывается ничего вне "разрешённой области". Разве что интерпретатор Питона переписать...

        Есть ещё вариант — попробовать подключить PyPy и PyPy3 и посмотреть, всё ли там в порядке с этим вопросом, но тут уже интересно, насколько PyPy будет полноценной заменой "классического" Питона.

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

          Просто было странно получить RE 1 даже после помещения вызова главной функции в блок try except, где в except происходит выход программы с нулевым кодом.

          Ну ладно, раз снять ограничения чисто с /dev/random нельзя, то можно хотя бы предупредить об этом в условиях (а ведь там даже про flush в питоне написано, значит авторы не игнорируют питон) или вердикт Security Violation. С другой стороны, есть решение и без использования случайных чисел. Но в будущем наверняка будут задачи, которые не решаются без случайных чисел.

          Да, поддержка PyPy 2 и 3 не помешала бы :) Только нужно как-то учитывать, что на прогрев JIT тратится много времени, которое более-менее одинаково для любой программы. По крайней мере так было раньше.

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

            Ну авторы задачи не обязаны знать тонкости устройства ядра Linux. Если что-то тут и можно исправить, то в самом ядре или хотя бы в патче к нему (файл fs/open.c в исходниках ядра).

            Хотя мне вариант с PyPy кажется более перспективным. Или же у данной реализации есть какие-то недостатки по сравнению с "классикой"?

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

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

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

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

        Ну альтернатива — вставить соответствующий путь в патч к ядру, перенакатить патч и пересобрать ядро. Или вручную добавить кое-что в open.c и сделать то же самое. То есть там даже не в сам fs/open.c, а в fs/open.c после отработки ejudge-патча (ну или собственно в ejudge-патч).

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

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

    А если переходы есть только между 3% вершин, то вообще невозможно.

    Что это значит? Что между остальными 97% вершин вообще попарно нет переходов? Это никак не следует из условия.

    В условии написано другое: из любой вершины i в любую вершину j есть ребро с вероятностью p.

    Например, из вершины 0 в вершину 1 есть ребро с вероятностью p.

    И из вершины, например, 123456789 в вершину, например, 987654321 — тоже есть ребро с вероятностью p.

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

    Может кто-нибудь объяснить, почему в G (Div2) работает просто перебор случайных чисел (и даже простой цикл до 15000 с проверками доступности единицы на каждом шагу)?

    У нас есть граф из 232 вершин, между каждой парой вершин с вероятностью p есть ребро.

    Пусть f(x) — вероятность того, что за x ходов мы успеем попасть из некоторой вершины, не равной 1, в вершину 1 (стартовое значение f(0) = 0).

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

    f(x) = p + (1 - p) * pf(x - 1) + (1 - p)2 * pf(x - 2) + ... + (1 - p)x - 1 * pf(1)

    Вероятность того, что мы не справимся за 30000 ходов, равна 1 - f(30000) = 1.8 * 10 - 12.

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

А можно мне списать сабмит в C?

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

    И какая проблема с этим?

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

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

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

        Все решения с такой ошибкой пересужены с учётом изменения формата. В частности, 207-я попытка OK.

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

Как решать A?

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

    Воспользоваться несколько раз формулой

    .

    Где -- функция Эйлера.

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

      Не совсем. Эта формула верна только для взаимно простых a, M. Там надо аккуратно учесть это (нужен не только остаток по модулю функции Эйлера, но и то является ли степень больше либо равна функции Эйлера).

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

        Действительно. Совсем забыл про условие взаимной простоты.

        Тем не менее, по задаче заходило ровно такое решение как я написал.

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

          У вас (если khabarovsk01 это вы) не совсем так написано, всё время берётся по модулю 4 и 10 в цикле, и ещё начальное значение не берётся по модулю. То есть в какой-то момент берётся по модулю 10 то, что нужно далее по модулю 4, что в общем случае неправильно делать.

          Тем не менее, числа в башне таковы, что можно считать не очень аккуратно. Если всё считать по модулю какого-нибудь большого числа, делящегося на LCM(10, φ(10), φ(φ(10)), ...) = 20 — например, по модулю 100 — то предпериод учитывать отдельно не придётся, так как на всех тестах у больших степеней больших чисел не получатся по такому модулю слишком маленькие остатки.

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

    А еще можно использовать Wolfram Alpha и забить в код решения для всех a, b. С помощью Wolfram не удалось получить только ответы для a<9, b == 10, но там вид последовательности очень намекает, что он такой-же, как и при b == 9.

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

      Собственно, это можно и руками сделать. Для каждого a можно быстро понять, что будет при всех b. Табличка-спойлер в правке.