orchidmajumder's blog

By orchidmajumder, 9 years ago,

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/

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

 » 9 years ago, # |   +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).
•  » » 9 years ago, # ^ |   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??
•  » » » 9 years ago, # ^ |   0 I think it is better for you to write Long Arithmetics yourself, without any extra libraries. You need to write only addition operation.
•  » » » » 9 years ago, # ^ |   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?
•  » » » » » 9 years ago, # ^ |   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.
•  » » 9 years ago, # ^ |   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.
•  » » » 9 years ago, # ^ | ← Rev. 2 →   0 < deleted >
•  » » » » 9 years ago, # ^ |   0 Well, what is "generic dp" in your opinion?
•  » » » 9 years ago, # ^ |   0 what is the correct formula ?? i dont think the recurrence is wrong but we have to define base conditions from 0 to 49 . @providec please provide the correct formula incase we are wrong . that d be of much help . thank you :)
•  » » 9 years ago, # ^ |   0 please let me know the 50*50 matrix for which exponentiation is to be done
 » 9 years ago, # |   +3 You can find solution in "Concrete Mathematics", chapter 7.