Блог пользователя orchidmajumder

Автор orchidmajumder, 11 лет назад, По-английски

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.

  • Проголосовать: нравится
  • +10
  • Проголосовать: не нравится

»
11 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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??

    • »
      »
      »
      11 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        11 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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?

        • »
          »
          »
          »
          »
          11 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          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.

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
11 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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