# Project Euler #78: Coin partitions

# Project Euler #78: Coin partitions

lamriniyounes + 0 comments Dynamic programming is not enough to solve this problem. You need to learn more about the mathematics. Euler rocks!

Kevinagin + 0 comments Great problem. Originally thought this would be another "copy and paste the solution from coin change". Turns out I needed to level up on number theory, so I learned a lot from this problem.

aman81387 + 2 comments Finally solve this problem after many unseccessfull attempt :)

**https://en.wikipedia.org/wiki/Pentagonal_number_theorem**This article will definetly helpfull for those who are still struggling and looking for an approach to solve.

akcr36 + 0 comments Thank You this article really helps me to crack this question

khoangcachxalam1 + 1 comment thank for your good idea ! thanks you very much !

aman81387 + 0 comments Glad that helped :

carl_p_morris + 1 comment Hey would anyone be able to help me out with this problem.

I can get the right answer but having problems with the speed tests in 6 and 7.

Here is my code:

from itertools import cycle t = int(input()) p = [] p.append(1) # p(0) = 1 penta = [1] for num in range(t): a = int(input()) n = len(p) while(n <= a): i = 0 p.append(0) signs = [1, 1, -1, -1] sign = cycle(signs) while(penta[i] <= n): p[n] += next(sign) * p[n - penta[i]] # Generative sequence p(n) = p(n - 1) + p(n - 2) - p(n - 5) - p(n - 7) + .. p[n] %= (10**9 + 7) i += 1 if(len(penta) <= i): if(i % 2 == 0): # Pentagonal numbers use m of m = 0, +/- 1, +/- 2, +/- 3, .... m = (i // 2) + 1 else: m = -1 * (i // 2 + 1) k = m * (3 * m - 1) // 2 #Pentagonal numbers 0.5m*(3m - 1) penta.append(k) n += 1 print(p[a])

djoshuac + 0 comments I tried a very similar algorithm as you in python and timed out. I rewrote the my algorithm in C++ and the results are almost instantaneous.

meet143169 + 0 comments timeout due to modulo, can anyone suggest any other way around

static long[] table = new long[60000 + 1]; //max size as given in problem static void count(int S[], int m, int n) { //long[] table = new long[n + 1]; Arrays.fill(table, 0); //O(n) table[0] = 1; for (int i = 0; i < m; i++) { for (int j = S[i]; j <= n; j++) { table[j] += table[j - S[i]] %(10^9+7);//timeout due to this modulo, if i remove modulo it works fine but will get wrong ans } } //Print all the table value // for (int i = 0; i < table.length; i++) { // System.out.print(" " + table[i]); // } //return (table[n] % 1000000007); } public static void main(String[] args) { //Pre calculate all the value till the max range(60000) int numberOfCoins = 60000; int[] coinArray = IntStream.range(1, numberOfCoins + 1).toArray(); //to fill the array with consecutive number count(coinArray, coinArray.length, numberOfCoins); Scanner sc = new Scanner(System.in); int testCase = sc.nextInt(); for (int i = 0; i < testCase; i++) { int input = sc.nextInt(); System.out.println(table[input]); } }

georeth2010 + 0 comments I got accepted by a O(N*N) time, O(N) space dynamic programming. The time limit is not strict enough for C >_<.

jac3tssm + 1 comment I'm getting a timeout for test cases 6 and 7, marked at 10 seconds. I cannot come up with a test case within the problem's constrainst that would cause a runtime >10 seconds. (I couldn't even find one that took close to that time).

vatsalchanana + 0 comments Create a test file with T=100 and all test cases have large N. Test your code with this file.

tiwariabhishek + 0 comments Learnt a new thing. Good One :).

sksuman_nitw + 1 comment getting termination due to timeout in testcase 6 and 7......even solving through dynamic programming

shashank21jHackerRank AdminChallenge Author + 0 comments It needs something more than that.

Indrasen + 0 comments This is a partition function(number theory)

the logis is: numbers of the form Â½m(3m âˆ’ 1), where m is an integer. The signs in the summation alternate as (-1)^{m}. This theorem can be used to derive a recurrence for the partition function:

`p(k) = p(k âˆ’ 1) + p(k âˆ’ 2) âˆ’ p(k âˆ’ 5) âˆ’ p(k âˆ’ 7) + p(k âˆ’ 12) + p(k âˆ’ 15) âˆ’ p(k âˆ’ 22) âˆ’ ...`

where p(0) is taken to equal 1, and p(k) is taken to be zero for negative k.

Sort 19 Discussions, By:

Please Login in order to post a comment