BeNew's blog

By BeNew, history, 2 months ago, In English,

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.

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
2 months ago, # |
Rev. 2   Vote: I like it +10 Vote: I do not like it

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.

Guess
  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by BeNew (previous revision, new revision, compare).

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by BeNew (previous revision, new revision, compare).

»
2 months ago, # |
Rev. 17   Vote: I like it 0 Vote: I do not like it

A recursive solution for this problem should be derived by induction as follows.

Base Case:

$$$f(1) = 1$$$

$$$f(2) = 2$$$

Inductive 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$$$.

  1. For $$$n = 1$$$, $$$S(1) = [1]$$$.

  2. For $$$n = 2$$$, $$$S(2) = [1+1,2]$$$.

  3. For $$$n = 2m+1$$$, $$$m \geq 1$$$, $$$S(2m+1) = [~1+s~|~\forall s \in S(2m)]$$$.

  4. 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, # |
  Vote: I like it +5 Vote: I do not like it

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 order

Like 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.