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

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

Напоминаю, что сегодня (20.10.2012) в 18:00 по Москве состоится первый контест хорватской олимпиады по информатике. Залогиниться/зарегистрироваться можно тут. Продолжительность: 3 часа. Удачи!

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

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

Система проверки по блокам без токенов?

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

    Ну, я надеюсь, что система не поменялась — без групп (за исключением там где реально надо) и без feedback'a.

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

Запоздал на полтора часа на тур :-\

Успел что-то сдать по всем задачам, совершенно не тестя, чувствую, потеряю баллов на тупых багах. Последняя — интересная. Единственное, что придумалось и быстро написалось — решение за O(24K) — динамиика D[v][a][b] — мы находимся в вершине v полного бинарного дерева, причём его листы упорядочены так, что самый левый — a, а самый правый — b. Значение — минимальная длина цепочки в этом поддереве, удовлетворяющей таким условиям на крайние элементы. Пересчитываем, понятно, перебирая барьерное ребро между двумя центральными листами.

До K = 7 работает, а вот дальше начинает тормозить.

Умею разбирать два верхних слоя динамики за побыстрее, а дальше пускать мою эту за O(24K), но хочется чего-нибудь покрасивее.

UPD:

Да, как и предполагалось, какие-то баги, баги :-( 50-80-10-120-98-96.

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

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

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

      У меня сначала было O(2^2K * 2^2K), но это можно превратить в O(2^2K * (2^K + 2^K)). Попробую написать щас.

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

50-80-100-45-140-160, потому что замутил правый край бинарного поиска на 10^6. :|

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

Расскажите KONCERT и SNAGA, пожалуйста.

Вроде в SNAGA я нашёл циклическую закономерность значений strength(n) : 2 3 2 4 2 3 2 3 2 3 2 3, но на числах 420 и 360360 она сваливается (возможно, есть ещё такие числа, но перебор их не нашёл).

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

    Число в которое переходит большие числа — маленькое. Будем его перебирать, а потом считать для скольких чисел оно будет переходом.

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

      Можно подробнее?

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

        Смотри, если у тебя есть переход в число х, то нету в х-1, тоесть число должно быть больше НОК(1,2,3,...,х-1). Получаем, что х не велико.
        Теперь нам нужно для каждого числа х посчитать — сколько есть чисел, которые кратны 1, 2, ..., х-1 и не кратны х. Это значение равно N/lcm(1,2,...,x-1) — N/lcm(1,2,...,x). Дальше для мелких считаем перебором и лепим все в кучу.

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

    Концерт — задача на понимание условия.
    Отдадим все мальчику №1, затем будем действовать так:
    - первый дает билет 2му
    - они оба заходят
    - второй отдапет билет первому
    - первый выходит
    И так со всеми.
    Потом просто запускаем 1го в зал. Так как билетов не меньше 2х, то все нормально.

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

      У меня девочка одна всех мальчиков провожала...

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

    В зависимости от значения strength(n) = 2,3,4,5.. числа удовлетворяющие этим значениям растут очень быстро. Находим для каждого strength(n) = 2,3,4,5.. минимальное число которое удовлетворяет этому strength. Достаточно до 42. И считаем кол-во чисел из этого диапазона умноженное на необходимое число + 1

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

    koncert: Найдём какого-то парня с билетом и какую-то девушку с билетом. Парень отдаёт билет девушке. Теперь для каждого парня: эта девушка даёт ему один билет, они проходят внутрь, парень отдаёт ей билет, девушка выходит.

    snaga: Разобьём все числа на такие множества:

    • x не делится на 2 (здесь strength(x) = strength(2) + 1)
    • x делится на 2, но не делится на 3 (здесь strength(x) = strength(3) + 1)
    • x делится на 2, 3, но не делится на 4 (здесь strength(x) = strength(4) + 1)
    • x делится на 2, 3, 4, но не делится на 5 (здесь strength(x) = strength(5) + 1)
    • ...

    Для каждого из множеств можно посчитать, сколько есть таких чисел до нужного нам предела. Будем перебирать эти множества и суммировать их общий strength до тех пор, пока lcm(2, 3, …, k) не станет больше n (тогда уж точно не найдём более чисел).

    Считаем эту функцию для b и a - 1, отнимаем второе от первого.

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

MARS:

Во-первых, будем действовать снизу вверх, то есть объединять [1..1] и [2..2], [3..3] и [4..4], .... Потом, второй слой — [1..2] и [3..4], [5..6] и [7..8] и.т.д. Так пока не объединим всё.

Во-вторых, можно заметить, что если у нас есть цепочка с началом l и концом r (обозначение: {l-r}), то мы однозначно можем определить её длину. И какие числа в ней. Это упрощает реализацию и даёт, что у нас 2^2K положений.

Будем делать ДП — a[l,r] = минимальная длина {l-r}. Будем считать их в порядке объединения отрезков (см. начало). То есть, если мы сейчас объединяем [17..24] и [25..32], то мы на данном этапе считаем a[l,r] где l любое число в [17..24], а r — любое число в [25..32].

Тогда a[l,r] = min(a[l,x] + dist[x,y] + a[y,r]), где x — неравный l число из половины же l, а y — неравное r число из половины r (если объединяем отрезки длины 1 — оно не может быть неравное — особый случай). Итого получаем O(2^2K * 2^K * 2^K), так как надо выбирать x и y.

Не забываем потом, что a[r,l] = a[l,r].

Однако давайте разобъём подсчёт. Идея такая — мы перебираем только x, а минимальное расстояние по второй половине мы уже преподсчитали. Итого: a[l,r] = min(a[l,x] + precomputed[x,r]). Осталось, подсчитать precomputed. Понятно, что precomputed[x,r] = min(dist[x,y] + a[y,r]). Осталось заметить, что для того чтобы подсчитать precomputed для данного слоя, всё что нам надо это константные длины и значения a из предыдущего слоя. То есть вычисления precomputed выполняем между слоями, и это занимает O(2^2K * 2^K), зато теперь и главное вычисление имеет такую же ассимптотику. Ответ на задачу: минимальное значение a из последнего слоя. Итого: O(2^3K), и то это довольно грубая оценка сверху (0.09 с в худшем).

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

How to solve problem F ... >_<

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

How to solve problem F >_< ..

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

    Does anybody know why don't they display results immediately ? Can't wait for results ! :(

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

      Your personal results are up right after the contest ends. Full results are posted in a week or so ( accoring to the organizers , this is an 'appeal period' , some contestants may complain about testcases {not meeting problem's constraints} , the grading process .. etc )

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

50-80-50-120-140-160

Так и не понимаю условие C. Они что должны парами ходить? Как они это проверяют? Почему этого в условии нет.

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

    Да, по одному билету можно двоих провести, если один заберет билет другого в зале.

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

1 — easy, 2 — sort then easy, 3 — all tickets to girl one then easy, 4 — binary search, 5 — math, how to solve? 6 — thinking...

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

    5 — one can observe that for any number smaller than k! the number in the second iteration will be smaller or equal to k. so all you have to do is finding out, which of the numbers have 2 as smallest "not divisor" which one has 3 and so an, up to 21 i think .

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

      I believe it's LCM of first k integers, instead of k!

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

        but when you have a number n smaller than k!, than there is one number between 1,2,3,4,5,..,k that does not divide n, so one of the smallest should be between 1 to k.

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

          oh ok, if it is divisible by n, it is also divisible by 2*n and so on, so lcm should be right.

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

    how do you want to solve 4 with binary search?

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

    6 — trivial divide and conquer works, when merging two 2k groups into a 2k + 1 group, you need to multiply three 2k × 2k matrix, use ordinary O(n3) algorithm, then whole algorithm works in O(n3) either

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

Can anyone add this contest to the gym, please?

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

    The problem is that it's not an ACM ICPC format but IOI format instead and as far as I know the gym cannot accept the second one yet.