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

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

Напоминаю, что сегодня (10.11.2012) в 18:00 по Москве состоится второй контест хорватской олимпиады по информатике. Залогиниться/зарегистрироваться можно тут. Продолжительность: 3 часа. Удачи!

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

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

Как решать 4ую?

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

    Отсортируем все блюда по неубыванию обычной цены (**B**). Предподсчитаем 3 массива:

    • sum[i] = сумма первых i обычных цен
    • maxD[i] = максимальная разность обычной цены и особой (**B-A**) среди первых i блюд
    • minA[i] = минимальная особая цена (**A**) среди последних блюд, начиная с i-того

    Рассмотрим 2 случая:

    1. Первое блюдо будет среди первых k — тогда суммой будет sum[k] - maxD[k]
    2. Иначе — sum[k-1] + minA[k]

    Выберем минимум из этих вариантов — это и будет ответом для текущего k.

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

Третья уже была :)

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

Anyone has idea for problem 6? It looks like we have to maintain a set of slopes to calculate the queries, but I can't find an effective way to add a new slope since the profit values are not monotonous.

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

Как решать 5ую задачу?

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

    Сделаем паросочетания цифра — место. Каждое наблюдение делает 2 вещи. Если мы знает что на одном отрезке минимальное число Х, то во-первых, на этом отрезке числа могут быть только от X до N-1, а во-вторых число X может быть только на этом отрезке. Получаем матрицу из 1 и 0. Дальше можно делать всё, что угодно — макс. паросочетания, Венгерка и.т.п.

    Матрицу можно получить следующим образом: будем считать "во-первых" и "во-вторых" отдельно. "Во-первых": сначала пробежимся по наблюдениям, и посчитаем, какие числа могут на этим месте быть. Заметим, что это отрезок. Соответственно, обновлять можем за O(M*N) — для каждого наблюдения пробежаться по каждому месту. Потом обновим матрицу "во-вторых": для каждого наблюдения возьмём "пограничное" число и обнулим его вне допустимого отрезка. O(M*N). Итого, получили матрицу.

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

Just published Results.