orchidmajumder's blog

coin change for n>=10^9
By orchidmajumder, 11 years ago, In English

Hi,

I was trying to solve this problem of finding no of possible ways of changing a value n.

http://www.spoj.com/problems/TPC07/

TJU judge link:

http://acm.tju.edu.cn/toj/showp2817.html

now this problem has a constraint of n<=10^9.so,I can't declare an array of that size and run a dp approach.Also,I think this problem will require BigInteger support by seeing the answer for the second test case.

So,any help on how to solve it using C/C++ would be much appreciated.

  • Vote: I like it
  • +10
  • Vote: I do not like it

Comments Comments (9)
| Write comment?
»
11 years ago, # |
  Vote: I like it +3 Vote: I do not like it

In DP, we must use this formula: F(i) = F(i-1) + F(i-5) + F(i-10) + F(i-25) + F(i-50)

As you can see, it is a linear function, so we can find F(n) faster than O(N) using matrix multiplications.

You can google "Fast k-th fibonacci algorithm", it can help you understand how to find F(N) for any linear function in O(logN*k^3).

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    But,in order to solve it in C/C++ I need to use some BigInteger library right??and also,I can't preprocess it.So,for every test case,I have to calculate this??

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I think it is better for you to write Long Arithmetics yourself, without any extra libraries. You need to write only addition operation.

      → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Ok thanx for clarifying that part. Now,I can't store f[1],f[2],..,f[n] because n can go upto 10^9.So what is the solution to that problem? For a particular n,should I find each of f(n-1),f(n-5),.. by matrix exponentiation??Will that pass in time limit?

        → Reply
        • »
          »
          »
          »
          »
          11 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I think it will pass time limit. And please, read about finding f(n) for linear function using matrix exponentiation and everything will be clear.

          And yes, formula is wrong. It counts "take 1 penny and 2 nickel" and "take 2 nickel and 1 penny" as different ways. But I think it can be fixed with small correction.

          → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Your formula is wrong. For instance if n is 6 then:

    f(6) = f(1) + f(5) = 3

    But for n = 6 the answer is 2.

    → Reply
»
11 years ago, # |
  Vote: I like it +3 Vote: I do not like it

You can find solution in "Concrete Mathematics", chapter 7.

→ Reply