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

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

Совсем недавно завершилась очередная личная интернет-олимпиада на сайте http://neerc.ifmo.ru/school/io/index.html. Предлагаю обсудить здесь задачи. Особой интерес представляют задачи C и D. :) Как их решить на полный балл?

Вот задачи: http://neerc.ifmo.ru/school/io/archive/20140322/problems-20140322-individual.pdf. И результаты, если кто-то ещё не видел: http://neerc.ifmo.ru/school/io/archive/20140322/standings-20140322-individual.html. ;)

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

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

Последняя просто решалась sqrt-эвристикой по запросам. Сделаем корень добавлений, потом пройдемся по массиву, глянем какие элементы стали "хорошими". Для каждого такого элемента еще раз пройдемся по запросам этого блока, чтоб уточнить когда именно он стал хотя бы b[i].

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

    Точно. Спасибо. =)

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

    Я решал чуть (ну как чуть...) извращённей — персистентным деревом отрезков. Построим дерево, в вершинах будем хранить x, y и левый конец запроса. Тогда значение в определённой клетке после нескольких запросов сможем посчитать за log n, просто пройдясь вниз от вершины до листа и собрав все значения. Для каждого элемента массива найдём бинпоиском первую такую версию, где он не меньше b[i]. Итого времени и памяти, чего еле-еле хватило.

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

    а как делать добавление блока запросов за O(N) ?

    Там же У меняется ( у*(i — L) ) для L<=i<=R

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

      Это можно сделать, например, вот таким образом:

      • создадим два массива xx и yy; xx[i] — сколько нужно добавить к текущему числу в позиции i и yy[i] на сколько нужно увеличить коэффициент возрастания числа в позиции i.

      • тогда каждый запрос можно сохранить с помощью таких четырёх операций(l[j], r[j], x[j], y[j] — текущий запрос, l — левая граница, r — правая граница, x — начальное числа, y — возрастание):

      1. xx[l[j]] += x[j] — y[j];
      2. yy[l[j]] += y[j];
      3. xx[r[j] + 1] -= x[j] + y[j] * (r[j] — l[j]);
      4. yy[r[j] + 1] -= y[j];
      • потом одним проходом за O(n) мы храним текущее число и коэффициент, и вычисляем какое число нужно прибавить к позиции i.

      Более детально: http://pastebin.com/u5jAseLC.

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

а может стоит выкладывать блоги про олимпиады, до их начала? а то я вечно пролетаю..

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

    К сожалению, в данный момент у нас нет человека, который готов регулярно писать подробные анонсы про эти олимпиады, а писать что-то совсем короткое для галочки тоже не хочется.

    Уже есть договоренность, что в следующем году этим будет заниматься кто-то из пресс-службы NEERC и всех остальных соревнований, проводимых в ИТМО.

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

Третья решалась так:

Сделаем бин. поиск по ответу. Чтобы проверить, подходит ли нам такой ответ, для начала увеличим радиус всех окружностей на R (R — текущий радиус, который мы проверяем). После этого останется проверить, что существует луч из стартовой точки, который имеет с каждой окружностью хотя бы одну общую точку. Для проверки этого проведем из стартовой точки касательные ко всем окружностям, получим набор углов (те окружности, в которых наша точка уже лежит, не будем рассматривать). Теперь осталось проверить, пересекаются ли все эти n углов (на самом деле, эти углы можно рассматривать как отрезки на окружности). А это делается уже довольно просто. Например, сортировкой и сканирующей прямой. Можно проверять и за линию, но заходила и сортировка.

К сожалению, во время контеста выяснилось, что решение жюри содержит ошибку (как раз в проверке того, что все углы пересекаются), приношу свои извинения за эту недоработку :(

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

    А как проверять пересечение за линию?

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

      Лично я писал решение с сортировкой, но за линию вроде можно делать как-то так:

      Две касательные — два угла, то есть отрезок на окружности. Надо проверить, имеют ли несколько отрезков на окружности общую точку. Ну а это как-то довольно просто делается. Так как они лежат на окружности, а не на прямой, будут вылезать случаи, но если аккуратно написать, все должно быть хорошо.

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

        Вот про "это как-то довольно просто делается" собственно и вопрос :-)

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

          Ну, окей. Во-первых, мы явно может понять, какая касательная будет левым концом, а какая правым (просто по построению). Осталось пересечь отрезки. Для этого нужно только уметь пересекать два отрезка. А это делается просто разбором случаев (оба отрезка не проходят через 0, один проходит через 0, оба через ноль)

          Может быть, можно и проще, это то, что первое в голову пришло :)