ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 2129. Mortgage in Far Away Kingdom

Is there faster solution
Posted by DarksideCoder 9 Mar 2022 07:22
My solution is O(tl^3logn) , but its performance is good.
Re: Is there faster solution
Posted by __Andrewy__ 17 Mar 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
Posted by Harkonnen 7 Aug 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).