Блог пользователя Dart-Xeyter

Автор Dart-Xeyter, история, 3 года назад, По-русски

Кажется, подобного поста ещё не было, поэтому... Здесь вы можете обсуждать всё об Открытке 2021-2022 :)

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

Условия задач. Таблица результатов.

Наконец-то добавленный официальный разбор.

Решение А.
Решение С (красивое).
Решение С (напрашивающееся).
Решение D.
Решение Е.
Решение F.
Решение G.
Решение I.
  • Проголосовать: нравится
  • +109
  • Проголосовать: не нравится

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

I можно добить до $$$O(n^2 \log n + n^2 \log C)$$$, если заранее посортить круги и стороны вокруг каждого круга по углу. Тогда почти таким же сканлайном можно найти объединение плохих отрезков за линию.

Ну и бинпоиск не нужен, потому что плохих/хороших отрезков суммарно линия.

У меня есть еще веселое решение на 78 по F

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

Я бы хотел решение для D, долго бился, особенно никуда не пришёл(разве что для линии смогу ответ найти)

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

В I на 100 зашёл $$$O(n^4logC)$$$ (за 0.6), ключевой момент — random shuffle

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

    Хм... С отсечением по времени? Просто, если честно делать — я тоже в своё решение shuffle добавлял, но не ускоряло. Немного ускорила сортировка — но хитрая, и не сильно :)

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

      Моё решение с хронологией пихания такое:

      1) бинпоиск по ответу

      на всякий случай бп от умника

      2) Перебираем две точки, которые касаются первой окружности, строим слева и справа и каждую проверяем

      3) В проверке перебираем точки, каждая блокирует интервал угла второй окружности

      4) Теперь есть не более $$$n$$$ интервалов, нужно узнать, есть ли угол, который не заблочен; достаточно проверить левые границы блоков на кандидаты. Тут можно решать за $$$O(n^2)$$$ или за $$$O(nlogn)$$$, со вторым всё решение работает медленнее.

      Сперва это проходило только для $$$n \leq 100$$$.

      +random shuffle -> $$$n \leq 300$$$

      замена long double на double -> $$$n\leq 500$$$ (80)

      в проверке сначала проверяем что нет точек внутри первого круга, а потом строим интервалы, а не одновременно -> $$$n \leq 1000$$$ (100)

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

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

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

Жаль, что нет разбора задачи E :(

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

Можно разбор G? Только за O(n^2) придумал, на дальнейшее ни знаний, ни времени не хватило

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

Можно разбор Н? Лучше чем на 57 не смог придумать...