ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 2129. Ипотека в Тридевятом Царстве

Is there faster solution
Послано DarksideCoder 9 мар 2022 07:22
My solution is O(tl^3logn) , but its performance is good.
Re: Is there faster solution
Послано __Andrewy__ 17 мар 2022 18:31
could you describe your solution? my algo O(logn * l^3 * t) has TL(
i try to find solution like this: dp[i, a, l] , i is bit number, a is addition to i-bit, l is lost count
Re: Is there faster solution
Послано Harkonnen 7 авг 2022 09:47
Yes, there is. (L^2)*log(N) solution (0.187 sec). I DP on total amount of coins and amount of extra coins for next denomination (the latter is used to know how much more can I push forward when I advance a digit). The first index always increases by K-1, the second always increases by K, so it's kind of diagonal partial summing up matrix to itself. If you precalculate reachable sums properly, you can perform DP transfer in O(L^2).