I've been trying this [problem](http://www.spoj.com/problems/EIDSALAMI2/) on spoj but not been able to come up with a optimal solution.↵
The statement translates to — find number of ways to divide a number 'm' into 'n' distinct positive numbers.↵
↵
1<=m,n<=10^6↵
also, m*n<=10^6↵
↵
I was thinking of applying dp, but was stuck at it because it required all the numbers to be distinct.↵
It is obvious that for all values of 'n' around 1400 and above, answer is 0.But that didn't help me in my approach.↵
↵
Can dp be applied? Or could it be solved using other method?↵
↵
EDIT: Solved using dp — consider a list of numbers — 1,2,3,....n (minimum possible) and at each index i,increment all numbers (i to n) by some constant.Apply dp here. I still faced some time complexity issues — http://ideone.com/yXCYeo↵
I had to optimise it using sieve — http://ideone.com/jpHIlR↵
↵
Please let me know if you used some other method.
The statement translates to — find number of ways to divide a number 'm' into 'n' distinct positive numbers.↵
↵
1<=m,n<=10^6↵
also, m*n<=10^6↵
↵
I was thinking of applying dp, but was stuck at it because it required all the numbers to be distinct.↵
It is obvious that for all values of 'n' around 1400 and above, answer is 0.But that didn't help me in my approach.↵
↵
Can dp be applied? Or could it be solved using other method?↵
↵
EDIT: Solved using dp — consider a list of numbers — 1,2,3,....n (minimum possible) and at each index i,increment all numbers (i to n) by some constant.Apply dp here. I still faced some time complexity issues — http://ideone.com/yXCYeo↵
I had to optimise it using sieve — http://ideone.com/jpHIlR↵
↵
Please let me know if you used some other method.
