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

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

Напоминаю, что завтра (27.10.2012) на acm.timus.ru пройдет этот контест в 11.00 мск. Предлагаю здесь обсудить контест после его окончания.

Хотелось бы узнать, задачи будут впервые, или они уже были в каких-то контестах (типа опенкапа)?

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

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

впервые конечно, это же, как я понимаю, отбор на ВКОШП для уральских школьников

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

Контест уже завершился, так что можно обсуждать задачи. Как решалась G?

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

    Храним остаток от деления данного числа на каждое простое не большее 47, восстановление ответа по КТО.

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

      Можно поподробнее про КТО?

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

      Я эту КТО не знаю. Хотя прочитав задачу, открыл статью на википедии, хотя мне это никак не помогло. Там для каждого простого множителя можно линейное модулярное уравнение решить и тогда тоже получается. А как делать через китайцев?

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

        Пусть мы знаем, что искомое число дает остаток mi от деления на простое число pi. Тогда найти число можно так:

        void merge(ll &ans, ll &mod, int rem, int nmod) {
            while (ans % nmod != rem) ans += mod;
            mod *= nmod;
        }
        
        ...
        
        ll ans = 0, mod = 1;
        for (int i = 0; i < n; ++i) {
            merge(ans, mod, m[i], p[i]);
        }
        cout << ans << endl;
        
        • »
          »
          »
          »
          »
          12 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

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

          Эта теорема говорит, что такое у нас всегда получится?:)

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

            Эта теорема говорит, что всё однозначно по модулю произведения pi(в общем случае, по модулю их НОК).

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

              спасибо, круто:)

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

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

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

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

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

А что в H на 23 тесте? Это там где две полоски пересечь надо.

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

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

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

    просто ранодомный тест, даже без параллельных отрезков...

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

      А до этого были рандомные? Ведь до 23 дошло как-то...

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

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

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

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

J решалась комбинаторикой?

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

    Тупо перебираем все тройки, в которые входит Холден, получается чистый квадрат.

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

      Можно и за константу: разобрать случаи, когда m == n/3, m — n/3 == 1 и m — n/3 > 1. Для каждого случая смотрим: teddyhater ли Холден; плюс случай, когда m < n/3. Получаем 7 вариантов ответа, которые довольно легко считаются. Код: http://pastebin.com/N16dDbMr

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

        Понятно, что можно. Вот только зачем?)

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

          Мне почему-то в голову пришло это решение :) Разобрать случаи тоже несложно, в общем-то, так что оно имеет право на жизнь.

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

            Осмелюсь возразить. Посмотри на монитор: сколько времени у тебя заняло решение за константу и сколько у меня — за квадрат. Плюс с какой попытки ты это решение запихал. В контесте из 12 халяв это решает.

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

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

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

Урал, ты ли это? такой халявный контест, чем это вызвано?

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

    Это был школьный контест.

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

      Обычно на УРКОПах есть над чем подумать. Вспомнить хотя бы прошлый-позапрошлый год. Сегодня я даже пожалел, что командой сели решать.

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

      для каких-то неполноценных школьников. в прошлом году этот же контест был куда интереснее

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

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

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

Как задачи B и I решались?

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

    В B разбирал случаи, l-1 > max(m, n) — неудача, k = 1 легко, при k >= 4 ответ всегда есть (квадратики размера (l-1)x(l-1)), иначе l = 2 возможно только при n > 1 и m > 1; если же l > 2, то хватит двух букв (шахматное замощение с клеткой 1x(l-1) или (l-1)x1).

    I делал динамикой по размеру госбюджета, переход за k, сложность O(nk).

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

      Спасибо!

      А можно чуть подробнее про пересчёт динамики?

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

        Храним пары dp1[i] и dp2[i] — сколько бюджета удастся распилить соответственно первому и второму игроку. Перебираем ход первого от 1 до k, пусть j. Если i — j < 0, то первый выгадывает m миллиардов, а второй ничего. Иначе первый получает j + dp2[i — j], а второй — dp1[i — j]. Максимизируем по всем j выигрыш первого, при равенстве минимизируем выигрыш второго. Ответ — dp1[n].

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

        У меня было две динамики: dp1[i] — количество денег, которое получит игрок, делающий ход первым, при том, что размен бюджета равен i, dp2[i] — количество денег, которое получит игрок, делающий ход вторым. Соответственно, мы максимизируем первую динамику и по возможности минимизируем вторую. Выбираем базу динамики как dp1[0] = dp2[0] = 0 (если в бюджете денег нет, то никто ничего не получит). Далее проходим i в порядке возрастания и перебираем j. Для фиксированного i и фиксированного j имеем: если j > i, то dp1[i] = m, dp2[i] = 0 (мы запросили больше денег, чем есть в бюджете), в противном случае — dp1[i] = dp2[i — j] + j, dp2[i] = dp1[i — j] (мы взяли j миллиардов из бюджета и передали ход оппоненту).

        UPD. Опоздал :).

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

Как же решалась задача H? Может кто поделится мыслями. Спасибо.

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

    Если отрезки параллельны, то ответ или 0, или -1. Нужно аккуратно посмотреть на проекции концов одного отрезка на прямую, содержащую другой отрезок, и наоборот. Иначе проводим через концы отрезков четыре прямые, пересекаем, считаем площадь четырёхугольника.

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

      А ответ 0 когда они совпадают? А -1 когда на параллельных прямых? И зачем нам смотреть на проекции? Если можно поподробнее расскажите. Спасибо.

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

        Когда они совпадают, ответ как раз -1.

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

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

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