### BeNew's blog

By BeNew, history, 2 months ago, ,

I tried to solve the problem sumset by the idea of coin change. But i am getting Run time error.I know there's an another way to solve the problem. As I am new to dp i am facing difficulties to think how to approach this problem. sorry for bad English.

Problem Link: http://poj.org/problem?id=2229 Problem description : how many ways to get the number 1<=n<=1000000 by the sum of 2's power.

• 0

 » 2 months ago, # | ← Rev. 2 →   +10 Adding a problem link will probably earn you more help.Adding your approach and code that gets RTE will probably earn you more help.What is your other way of solving the problem? Adding your intuitions will probably earn you more help. GuessIs it using the formula: $Number - (Number of set bits in Number) + 1$?N = 61 + 1 + 1 + 1 + 1 + 11 + 1 + 1 + 1 + 21 + 1 + 2 + 22 + 2 + 22 + 4
•  » » 2 months ago, # ^ |   0 No actually I got a pattern like:if i is even f[i] = f[i-2] + f[i]/2 if i is odd f[i] = f[i-1]. Why this formula is working?
•  » » » 2 months ago, # ^ |   0 If i is odd: if the sum of 2's power contains 1 as a term then f[i] += f[i-1] if the sum of 2's power does not contain 1 as a term — it's impossible because i is odd If i is even: if the sum of 2's power contains 1 as a term then f[i] += f[i-1] if the sum of 2's power does not contain 1 as a term then we have the sum of even numbers and the number of ways is f[i/2] so f[i] += f[i/2]
 » 2 months ago, # |   0 Auto comment: topic has been updated by BeNew (previous revision, new revision, compare).
 » 2 months ago, # |   0 Auto comment: topic has been updated by BeNew (previous revision, new revision, compare).
 » 2 months ago, # | ← Rev. 17 →   0 A recursive solution for this problem should be derived by induction as follows. Base Case:$f(1) = 1$$f(2) = 2Inductive Case: m \geq 1$$f(2m+1) = f(2m)$ $f(2m+2) = f(2m)+f(m+1)$ Proof: By definition, $f(n) = |S(n)|$, where the sumset $S(n)$ is the set of different multisets of powers of 2 that sum to $n$. Let $T(N) = [S(n) | 1 \leq n \leq N]$ be the set of all sumsets up to N. It can be shown sumsets in $T(N)$ are mutually disjoint, i.e. $S(i) \cap S(j) = \emptyset$ when $i \neq j$. Therefore, $|S(i) \cup S(j)| = |S(i)|+|S(j)|$ when $i \neq j$. For $n = 1$, $S(1) = [1]$. For $n = 2$, $S(2) = [1+1,2]$. For $n = 2m+1$, $m \geq 1$, $S(2m+1) = [~1+s~|~\forall s \in S(2m)]$. For $n = 2m+2$, $m \geq 1$, $S(2m+2) = [~1+1+s~|~\forall s \in S(2m)] \cup [2s|~\forall s \in S(m+1)]$. Example:When $n = 7$:$S(7) = [~1+s~|~\forall s \in S(6)]$$S(6) = [~1+1+s~|~\forall s \in S(4)] \cup [2s|~\forall s \in S(3)]$$S(4) = [~1+1+s~|~\forall s \in S(2)] \cup [2s|~\forall s \in S(2)]$$S(3) = [~1+s~|~\forall s \in S(2)]Therefore, S(3) = [1+1+1,1+2]$$S(4) = [1+1+1+1,1+1+2] \cup [2+2,4]$$S(6) = [1+1+1+1+1+1,1+1+1+1+2] \cup [1+1+2+2,1+1+4] \cup [2+2+2,2+4]$and so on.
•  » » 2 months ago, # ^ |   0 thanks a lot man
•  » » » 2 months ago, # ^ |   0 With pleasure.
 » 2 months ago, # |   +5 It can be solved using a simple DP.Consider $dp[i]$ is the number of ways you can make $i$. Now $dp[i] = \displaystyle\sum_{0}^{20} dp[i-x]$ where $x$ is a power of two. Now we have a problem of counting the same way several times, consider $i=3$, now we'll count $2,1$ and $1,2$ as two different ways while they are only one. So this needs a small modification.Let's consider $dp[i][j]$ is the number of ways you can make $i$ while you are using $2^j$. Here, $dp[i][j] = dp[i-2^j][j] + dp[i][j+1]$. This means you can either subtract $2^j$ from $i$ and stay at the same power of two (so you can subtract it again in $dp[i-2^j][j]$), or let's now try the following power which is $j+1$. Like this we won't count the same way twice because we're subtracting the powers of two in orderLike this we'll consider the way only once. If things are not explained pretty well take a look at this problem: Coin Combinations II and icecuber's editorial: CSES DP section editorial.
•  » » 2 months ago, # ^ |   +5 thanks a lot man
•  » » » 2 months ago, # ^ |   0 Anytime!