M-ary Partitions: Difference between revisions
imported>Kmk21 Created page with "We can solve the problem dynamically by solving dp(i,j) where i = value we're trying to obtain, and j = maximum exponent we're allowed to use. Assume b is the specified base...." |
imported>Kmk21 No edit summary |
||
| Line 7: | Line 7: | ||
i < 10k, and j < log(10k) ~= 13, so the DP table is only 130k large. Iterating over all x is at most another 10^4, which puts us at >1 billion, but that worst case only occurs at a very small number of places in the table (namely when j is 2, and it's exponentially smaller than that in any other instance). So the solution should work fast enough. | i < 10k, and j < log(10k) ~= 13, so the DP table is only 130k large. Iterating over all x is at most another 10^4, which puts us at >1 billion, but that worst case only occurs at a very small number of places in the table (namely when j is 2, and it's exponentially smaller than that in any other instance). So the solution should work fast enough. | ||
[[Category:ICPC Problems]] | [[Category:ICPC Problems]] | ||
[[Category:Gnyr2016]] | [[Category:Gnyr2016]] | ||
Latest revision as of 01:03, 4 November 2017
We can solve the problem dynamically by solving dp(i,j) where i = value we're trying to obtain, and j = maximum exponent we're allowed to use. Assume b is the specified base.
dp(i,j) = sum(dp(i - x*b^j, j-1))
For the maximum base we're allowed to use, we simply iterate over all possible number of multiples we use that base. We subtract that off the number we're trying to obtain, and recurse using exponent - 1.
i < 10k, and j < log(10k) ~= 13, so the DP table is only 130k large. Iterating over all x is at most another 10^4, which puts us at >1 billion, but that worst case only occurs at a very small number of places in the table (namely when j is 2, and it's exponentially smaller than that in any other instance). So the solution should work fast enough.