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

IFMO Training 09
Автор Creed, 13 лет назад, По-русски
Подскажите как решать K. Как я только не решал все равно WA4
  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

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

Такой вот вопрос по сегодняшней тренеровке, задача H, может кто-нибудь знает хитрый тест, у меня такое решение, в начале отсортируем данный массив, теперь все выборки делятся на те, которые не содержат минимальный элемент - их посчитаем рюкзаком(на элементах массива с 2..n) и те которые содержат - это просто вызовемся рекурсивно с новым массивов 2..n и с новой суммой = сумма - минимальный элемент.

Вопрос снят, понял в чем некорректность.

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

    Я аналог рюкзака написал: 

    D[i][max_remain][money_remain], где i -- количество уже уложенных предметов, max_remain -- максимально возможный остаток денег, money_remain -- текущий остаток денег.

    База:
    D[0][money][money] = 1

    Переходы:
    Берём предмет: D[i + 1][max_remain][money_remain - price[i]] += D[i][max_remain][money_remain]
    Не берём: D[i + 1][Math.min(max_remain, price[i] - 1)][money_remain]] += D[i][max_remain][money_remain]

    Ответ суммируем из D[n][j][k], где k <= j.
    → Ответить
13 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
K - можно двумя динамиками, d1[i] - минимальное кол-во палочек чтобы получить i, и можно пользоваться только умножением, тут переходы очевидны.
d2[i] - минимальное кол-во палочек чтобы получить i, тогда переход для d2[i] = min(d2[j] + 2 + d1[i-j])
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Спасибо. Проблема была как раз с параллельным использованием сложения и умножения. Как однако она просто решалась =)
    → Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    странно, так и написал: ва4....
    → Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Как решать I?
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Лично я решал перебором маски, а дальше гауссом в целых числах. На контесте сдать не успел, а сейчас не могу дорешивание найти чтоб проверить.
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      А какую маску перебирать и зачем? И почему у целочисленного гаусса не возникнут числа > 264?
      → Ответить
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Маска по словам: 0 - слово в левой части 1 - в правой. Т.е. переменными в СЛАУ у нас являются коэффициенты по словам. А вот насчет возникновения чисел больше 2^64 не смог найти подходящий большой тест, поэтому и хочется на дорешивании проверить.
        → Ответить
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Так это не перебор маски, а просто решение СЛАУ)
          (я побоялся такое писать т.к. непонятно почему это должно работать)
          → Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Как решать E?
→ Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Как решать E?
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Неправильно условие понял на контесте. Не понял, что когда несколько циклов, то решения нет. А для одного цикла решение очевидное.
    → Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Подскажите пожалуйста как решать J?
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится
    Если n четно, найти ответ для n / 2 и умножить все слагаемые на 2. А если нечетно, вычесть из n максимальную степень 3. Можно понять, что алгоритм корректен.
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Есть ли где-нибудь дорешивание по представленным задачам??
      → Ответить
      • 13 лет назад, # ^ |
        ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        На SPb IFMO Training Center "...Upsolving is up! Log in using your login/password after the contest and submit any problem from past trainings....", проверяем... и действительно есть дорешивание...

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

Интересно, как решать задачу E("Human Knot"), если были бы разрешены несколько циклов?

И еще, задачу I("String Equations") кто-нибудь решил без BigInteger'ов?

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

Кто-нибудь в курсе сегодня будет тренировка?

→ Ответить