Изменения рейтингов за последние раунды временно удалены. Скоро они будут возвращены. ×

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

Девятая Интернет-олимпиада на neerc.ifmo.ru/school/
Автор agul, 13 лет назад, По-русски
Сегодня в 16:00 (МСК) началась девятая интернет-олимпиада. После ее окончания предлагаю здесь обсудить решения и прочее.

Ссылка: neerc.ifmo.ru/school/
  • Проголосовать: нравится
  • +10
  • Проголосовать: не нравится

13 лет назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится
Наверное не МСК а МСД...
→ Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
а баллы в этой тренировке выставляются сразу?
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Нет, эта олимпиада проходит по правилам IOI, т.е. во время тура идет тестирование на претестах из условия, а полное тестирование происходит только после окончания олимпиады.

    В ИТМО работают быстро, как правило, через 1-2 часа уже висят полные результаты.
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      просто у моих друзей проверятеся, а у меня нет....
      → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Вообще говоря, по правилам IOI (2010) проверка идет с "токенами"... То есть участник имеет 2 токена, и может использовать их на свою посылку, получая возможность посмотреть все результаты по всем тестам. Каждый токен восстанавливается через полчаса
      → Ответить
      • 13 лет назад, # ^ |
          Проголосовать: нравится -6 Проголосовать: не нравится
        причем тут IOI-2010? Не важно что там канадцам(организаторам IOI2010) взбрело в голову, важно что под этим понимают люди. Традиционные IOI правила пока такие какие имелись в виду выше. Как только лет эдак 10 будут проводиться IOI по правилам канадцев тогда да, можно так говорить.
        → Ответить
        • 13 лет назад, # ^ |
            Проголосовать: нравится +6 Проголосовать: не нравится
          Канадский эксперимент был признан удачным, и, вроде бы, IOI 2011 пройдет по тем же правилам.
          Сомневаюсь, что к старым правилам вобще когда-нибудь вернутся.
          → Ответить
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          В этом году такие же будут правила, насколько я знаю. По-моему, и на Всеросе пора вводить хотя бы частичное онлайн-тестирование, а то народ тестирует во время тура не намного меньше, чем кодит и думает...что не есть хорошо, ИМХО
          → Ответить
13 лет назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится
У меня просьба: нельзя ли писать о соревновании хотя бы за полдня. А то чаще всего подобные сообщения появляются уже во время контеста.
→ Ответить
13 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
Кто на Д писал решение не на 40 баллов , поделитесь идеей.
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    По-моему, это динамика по поддеревьям.
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      А мне что-то подсказывает, что это бинпоиск + жадность.
      → Ответить
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Скажем так: я написал динамику. При обходе в глубину в каждой вершине храним расстояние до самой дальней вершины поддерева, от которой ближайшее отравленное логово > k шагов. А еще расстояние до самой близкой вершины в поддереве, которая отравлена.
        Может быть я конечно жестко туплю и все это неверно.
        → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится
      Я думаю что нужно пользовать дихотомию по ответу
      → Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Наверное можно написать динамику f[i][j]=нашему ответу,если мы стоим в вершине с номером i и максимальное расстояние до не помеченной вершины в текущем поддереве равно j.Зная для всех j текущего i ,мы пересчитаем для предка.Сложность O(n*k).
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится +10 Проголосовать: не нравится

      Решение D на 100 баллов

      Подвесим дерево за произвольную вершину. Посчитаем две динамики на поддеревьях: f[v] - на какой глубине находится ближайшая ловушка, и g[v] - на какой глубине находится ближайший непокрытый таракан. Как делать переходы? Для текущей вершины после обработки детей посчитаем минимум по всем f[child(v)] и максимум по всем g[child(v)]. Пусть первое число - a, второе - b. Тогда возможны три ситуации.

      1) a + b <= k

      Тогда самый удаленный таракан покрывается самой высокой ловушкой из другого поддерева. В этом поддереве не остается непокрытых тараканов, а самая глубокая ловушка находится на глубине a+1.

      f[v] = a+1, g[v] = 0

      2) a + b > k, b < k

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

      f[v] = a+1, g[v] = b+1

      3) a + b > k, b == k

      Самый глубокий непокрытый таракан в поддереве не может быть покрыт иначе, кроме как из этой вершины. Ставим тут ловушку, тем самым покрывая всех непокрытых тараканов в поддереве (т к их глубина <= k).

      f[a] = 0, g[a] = 0

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

      → Ответить
      • 13 лет назад, # ^ |
          Проголосовать: нравится +5 Проголосовать: не нравится
        Решение на 100 баллов.
        1) Сортируем все вершины по глубине в дереве обхода.
        2) Просматриваем их в порядке не возрастания
        3) Для каждой все еще живой вершины, находим k-ый предок (вершинку удаленную от текущей на k по направлению к корню, или же корень, если глубина меньше k).
        4) DFS-ом помечаем все вершины удаленные от текущей не более чем на k как убитые
        5) Проверяем следующую врешину.
        Итого решение проходит все тесты, хотя вроде бы асимптотически квадрат ;)
        → Ответить
13 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится
Мне интересно послушать идеи по задаче А, просто кто как решил.
→ Ответить
  • 13 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится
    Отдельно для парных , отдельно для непарных.
    odd(N) -N/2+D, -N/2+1+D, ..., D, ... D+N/2
    even(N) -N/2+D, -N/2+1+D,..., D-1, D+1, D+N/2
    Думаю , это очевидное решение.
    → Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Во второй ответом будет 10M-Len ,Len = кол-во цифр после запятой?
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Вроде бы так. Правда я это заметил уже только когда написал динамику.
    → Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Еще очень интересная вещь в этой задаче, (1 ≤ m ≤ 1000) при m=1 по условию Len=0, но "Количество цифр после запятой в числе k — натуральное число, меньшее m", получается, что 0 — натуральное число? 
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Ну походу это означает , что m=1 быть не может.
      → Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Поделитесь решением С на 100.
→ Ответить
  • 13 лет назад, # ^ |
    ← Rev. 3   Проголосовать: нравится +5 Проголосовать: не нравится
    Не знаю, правильно-ли я делал, но я просто каждый раз поддерживал четыре указателя: на самую левую дорогу которая пересекает прямоугольник, самую правую. Самую нижнюю самую верхнюю. Ну там еще небольшая ДП что-бы сумму на отрезке знать. Сложность O(N log N+M log M + T).
    Если пройдет, то напишу полностью.

    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Понятно. Мне тоже что-то похожее придумалось, но показалось, что там слишком много геморроя. Например, со случаями, когда как-то хитро пересекаются самая левая и самая верхняя дорога и наша туча одновременно.
      → Ответить
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        По результату видно, что это решение правильное. Паша внизу написал то что осталось нужным.
        → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится
      А теперь замечаем, что координаты маленькие, и задача сводится к промоделировать T шагов, и по считать суммы на отрезках любым способом. Ну и по несложным формулам посчитать ответ для квадратика по ответам для проекций. Кстати непрерывная задача, как я ее понял сначала, намного интереснее.
      → Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    По идее делаем события — начало новой улицы и конец, сортим события по возрастанию и далее используем метод двух указателей, время где-то — O(t+(n+m)log(n+m)).
    → Ответить
13 лет назад, # |
← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится
а почему никто не отметил, что персонажами всех легенд являются герои сериала "Теория большого взрыва"? :)
→ Ответить