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

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

Всем привет!

Сегодня 15:00 MSK состоится личное соревнование.

AtCoder Regular Contest 067

AtCoder Beginner Contest 052

Приглашаю всех поучаствовать и предлагаю обсудить задачи после контеста!

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

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

Решил все задачи контеста :) до 3 минуты окончание раунда. Первый раз жизни. Я в top100

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

Approaches for Task E : Grouping http://arc067.contest.atcoder.jp/tasks/arc067_c ?

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

    denotes number of ways of putting people in groups of size . where denotes number of ways to distribute people in groups of size .

    .
    Answer is .

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

How to solve F?

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

    First observation : a solution will visit a range of restaurants, pick the best meal for each ticket in the range, and pay the distance from the start to the end of the range.

    It is possible to compute the optimal solution for a range in O(m) time using m range maximum queries and subtracting the distance. This gives a O(n^2 m) algorithm. It is possible to improve it to O(m n log(n)) with divide and conquer optimization.

    Code for D&D optimization :

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

    Let's for each pair (restaurant; ticket number) find all segments of restaurants, on which this pair will be used. To do so we can use standard algorithm with stack, to find nearest restaurants with better meals for this tickets. Let's call position of our restaurant pos, and these two restaurants rightPos and leftPos. Our pair will be used on segments with left border [leftPos + 1;pos], and right position [pos;rightPos - 1]. To find values for each segment we can just add value of all pairs in correspounding rectangles in [leftPos;rightPos] plane. It will work in O(n2 + nm)

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

Can the editorials be provided in English as well?

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

Problem C was very good, and I can solve it for O(N log N). Is there more efficient algorithm like O(sqrt(N))?