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

Автор Abra, 14 лет назад, По-русски
Привет, мир! Это мой первый разбор. =)

A. Разведка 2

Нахождение минимума в массиве, с одим дополнительным сравнением первого и последнего элементов.

B. Распродажа

Отрицательные элементы складываем в массив, сортируем, находим сумму m наибольших по модулю.

C. Список

Решается массивом булей, единственная заковыка - с выводом, но вполне преодолима.

D. Карта дорог

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

E. Столкновения

Заведем переменную времени ct, которая вначале равна 0.
Начинаем моделировать:
Пусть dt равен t - ct, просматриваем все пары шариков, по формуле 
x1 + v1 * dt = x2 + v2 * dt
dt = (x1 - x2) / (v2 - v1)
находим минимальную dt - промежуток времени, через который какие-нибудь шарики столкнуться, или время моделирования закончится.
Сдвигаем шарики на этот промежуток времени, снова просматриваем все пары, если координаты двух совпадают, меняем их скорости по формуле из условия.
Повторять, пока ct не сравняется с t.
Особое внимание стоит уделить точности, наверное на этом и подловили RAVEman'а с ACRush'ем. =)
В принятом решении я использовал double и точность сравнений 10-10.

Удачи в контестах!
Разбор задач Codeforces Beta Round 34 (Div. 2)
  • Проголосовать: нравится
  • -5
  • Проголосовать: не нравится

14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
В задаче D можно хранить предка каждой вершины, на пути от r2 до r1 для всех вершин предком сделать потомка
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Почему буковки разного размера?
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
В задаче E некоторые не учитывали, что может быть несколько столкновений в один момент. Правда, какие-то решения почему-то проходят и так, см. например 140641
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Допустим, что у нас есть два столкновения в один момент. Вышеописанным алгоритмом находим первое, перематываем время на момент столкновения. Теперь второе из этих двух столкновений произойдёт через 0 единиц времени, и алгоритм возьмёт это столкновение как следующее. Всё корректно, по-моему.
    • 14 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится
      Если столкновения происходят одновременно, то после того как мы перемотаем время, второе уже не произойдет, как и первое, разве не так?
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Просто время нужно сравнивать по точности, а именно если время <0.00001, то это не считать за столкновение.
        • 14 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Нет, дело не в этом. Если столкновения происходят в абсолютно одинаковое время, то это не поможет.
          Те решения, которые проходят, похоже, сортируют точки по координате (их порядок в процессе не меняется) и потом сравнивают скорости соседних. Тогда все работает.
          • 14 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            Я ничего не сортировал, и у меня прошло, просто как указано выше ,сравнивал время.
            • 14 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится
              Мы говорим вот про этот случай:
              екоторые не учитывали, что может быть несколько столкновений в один момент"

              Ты учитываешь :)
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      После того, как мы перемотали время на момент столкновения, можно просто рассмотреть все пары, благо время позволяет, и изменить скорости тех, что столкнулись, сколько бы таких пар не было.
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    А в условии сказано "Кроме того, гарантируется, что в одном столкновении не будет участвовать одновременно более двух шариков". Видимо, это гарантировалось для систестов, но  не для взломов :)
»
4 года назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

Tutorial for CF 34D Road Map

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

code for problem D Road Map` 142366754