|
|
Show all threads Hide all threads Show all messages Hide all messages | Is there faster solution | DarksideCoder | 2129. Mortgage in Far Away Kingdom | 7 Aug 2022 09:47 | 3 | My solution is O(tl^3logn) , but its performance is good. 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 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). | Help... WA2 | Name must be given in English. | 2129. Mortgage in Far Away Kingdom | 1 Feb 2022 20:17 | 2 | Help... WA2 Name must be given in English. 3 May 2021 09:13 Can you give me some tests,please? I can't find any solutions on the internet. Edited by author 03.05.2021 09:14 Input: 2 100 2 20 1000000000000000000 2 100 Output: 184 967176416 |
|
|
|