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

Vekua Cup 2015
Автор yarrr, 9 лет назад, По-русски

Расскажите, пожалуйста, а что нужно было по условию сделать в задаче G и как ее решать?

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

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

Могу только рассказать, что надо было сделать, решать не умею:(

Дано не более 20 чисел (каждое не более 100) и число k (не более 6). Также дано число L.

Мы умеем выбирать любое упорядоченное подмножество наших чисел размером не более k (упорядоченное в плане индексов). Из этого подмножества мы можем брать любой (возможно, закругленный) подотрезок. Число считается достижимым для заданного упорядоченного подмножества, если мы можем получить его как xor какого-то из таких отрезков.

Ответом для подмножества назовем такое наибольшее число R, что для него достижимы все числа от L до R. (либо -1 если L недостижимо). Наша задача — сказать максимальный ответ по всем подмножествам.

Ну и еще гарантируется, что тесты генерировались рандомно

Пробовал упихать отжиг — не удалось.

У кого-то есть размороженная таблица, кстати?

UPD И еще — расскажите как решать E и F?

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

Задача: найдите такой упорядоченный поднабор данных чисел размера k, что как можно больше чисел начиная с L представимы в виде ксора какого-то подотрезка (закольцованного).

Я пихал такое решение:
1) Перебираем kn упорядоченных выборов. Для удобства массив сортируем и отсекаем ситуации, когда первый элемент выборки не минимальный, также отсекаемся, если от разворота последовательность станет меньше.
2) Теперь мы хотим получить все числа, которые можно получить из данной шестерки. Я считал только числа, которые можно получить на подотрезках длины не больше 3, возвращал маской в int128. Делается прекалком — посчитать ксоры, которые можно получить из трех элементов и всевозможные ксоры на префиксах и суффиксах. Потом из двух частей собираем то, что можно получить из шестерки — это буквально 4 дополнительных варианта.
3) Теперь проверяем для всех чисел начиная с L, можно ли представить x или ксор нашей шестерки без x. Тесты случайные, в среднем довольно быстро отсечемся (можно локально погенерировать).

Аккуратно написанное это вроде без каких-либо еще оптимизаций заходит.

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

Позвольте такую глупость спросить: как решать A?

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

    У меня было так.
    1) Все X-ы должны быть последними, потому что они не добавляют урона или времени, и влияние Y-ов и Z-ов таким образом будет максимально.
    2) Дальше динамика. dp[i][j] — какой максимальный урон получится на префиксе [1, i], если там ровно j Y-ов, ровно i — j Z-ов. При этом считается, что в оставшемся суффиксе будут только X-ы. Но урон от X-ов в этой динамике не хранится, для того чтобы можно было ее пересчитывать. Дальше в пересчете либо на i-ом месте ставишь Y, либо Z. Тогда ответ либо когда ты везде ставишь X-ы. Либо максимум по всем dp[i][j] + соответствующий урон от суффикса с X-ами. Получается O(N^2).
    Что-то подробнее надо?

    → Ответить
  • »
    »
    9 лет назад, # ^ |
    ← Rev. 3   Проголосовать: нравится +5 Проголосовать: не нравится

    Опередили :)

    Понятно, что первый тип башен может всегда идти последними.

    Тогда весь вопрос в том, как расположить башни второго и третьего типа на префиксе.

    Давай напишем динамику d[i][j] = максимальный урон, если мы разместили уже i башен второго типа и j третьего.

    Переходы очень простые, так как по этим количествам мы можем высчитать время на проход и урон в секунду.

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

    → Ответить
  • »
    »
    9 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

    Заметим, что башни, которы бьют по x можно ставить в конец. Действительно, ставить их раньше башни, которая бьет по y нет смысла (иначе башня которая бьет по y будет бить меньше времени). Аналогично, не имеет смысла ставить их раньше башни, которая замедляет.

    Теперь пишем динамику по тому, сколько башен-замедлялок и башен, которые бьют по y мы уже поставили на префиксе. Переходы — до конца ставим башни, которые бьют по х, или ставим замедлялку, или ставим башню, которая бьет по y.

    UPD Super slow :(

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

    Спасибо!

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

Ни у кого нет условий задач и таблицы после разморозки?

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

Как решать задачу про приятное множество точек на плоскости? (не помню какой у нее номер)

→ Ответить