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

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

Собственно, расскажу о своей проблеме. SSP мне попалась в задаче J с финала ACM 2011 года. Я написал динамику по аналогии с рюкзаком за O(n) памяти и O(n * k) = O(n ^ (4/3)) времени (n - максимальное число, которое нужно разложить на слагаемые, k - количество элементов во множестве). Каким образом можно улучшить асимптотику? Можно ли как-то использовать две следующих вещи: а) множество состоит из квадратно-пирамидальных чисел, б) для разложения произвольного числа из промежутка [1; 1000000] требуется в худшем случае 6 чисел?

UPD. Буду особенно рад услышать финалистов :).

UPD2. От NEERC'а в прошлом году в финал вышли 13 команд, если не ошибаюсь, все они J решили. Почему такая гробовая тишина?

UPD3. По комментарию Артема я понял, что мое решение на финале бы прошло. Теперь буду рад услышать тех, кто загнали задачу на испанском сервере в ТЛ 3 секунды.

UPD4. Судя по топ20 решивших задачу на livearchive, наличие кого-то из русскоговорящих среди оставшихся 13 маловероятно. Придется загонять самому и/или с сокомандниками. Хотя если у кого-то есть идеи - буду очень благодарен, если этот человек ими поделится.

UPD5. Идея решения у меня появилась, скоро реализую, загоню, докажу асимптотику и отпишусь.

UPD6. Идея неверна, да и пытаться загнать такое решение на медленный сервер - дело бесполезное.

UPD7. Переписал динамику по вот этому разбору со следующими изменениями: а) искал не максимальную пирамидку, с которой возможен переход, а минимальную (максимальную находил при восстановлении ответа), б) отсек диапазон пирамидок, меньших n / count, где count - количество пирамидок в наборе. Решение зашло за 1 секунду. Вот код, спасибо Jokser'у за идею насчет минимальной пирамидки.

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

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

Что такое "квадратно-пмрамидальные числа" ? Почему я должен гуглить это, чтобы помочь тебе?

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

википедия: "4900 — единственное число > 1, которое является одновременно квадратным и пирамидальным." 

википедия, да блин, ссылки че-то не работают http://ru.wikipedia.org/wiki/Квадрат_(число)

»
13 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится
На финале были быстрые компы и большие TL, поэтому мы особо не думали и сдали это решение за времени и столько же памяти (считаются ответы сразу для всех n). Ничего хитрого не использовали.

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

    Ни черта себе... Я запустил ваше решение на своей железке (компилятор, правда, MS VC++ 10.0), оно работает примерно столько же, сколько и мое вот это на Яве, про которое я написал в основном посте - около 25 секунд.

    Кстати, можете сказать, на финалах ограничения каким образом проставляются? Аналогично NEERC'у с разницей, что на NEERC'е ограничения идут на один тест, или по-другому?

    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится
      На финале этот код работал около 7 секунд. Там главное, что тестирующий сервер и рабочий комп полностью идентичны, а ТЛ - какой-то заранее известный большой. То ли 10 секунд, то ли 15.
      • »
        »
        »
        »
        13 лет назад, # ^ |
          Проголосовать: нравится +10 Проголосовать: не нравится
        Спасибо за информацию, наконец-то узнал ее из надежного источника.