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

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

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

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

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

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

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

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

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

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

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

UPD:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  • »
    »
    14 лет назад, скрыть # ^ |
    ← 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, отнимаем второе от первого.

»
14 лет назад, скрыть # |
← 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 с в худшем).

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

How to solve problem F ... >_<

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

How to solve problem F >_< ..

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

50-80-50-120-140-160

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

»
14 лет назад, скрыть # |
 
Проголосовать: нравится 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...

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

Can anyone add this contest to the gym, please?