I have this task:
Mother Anna opened a package of candies, which she wants to distribute to her children as a reward. So that they are not clashes between them, so of course the one who finished in a better place in the competition cannot get less candies than the one that ended up in a worse place. How many ways can Anna divide C candies among D children?
The task:
For the given numbers D and C, find the number of possible distributions of candies.
Entrance:
In the first line of the file there is a number Q indicating the number of sets.
There are Q rows with a pair of numbers D and C.
Output:
The output of the program is the result for each set modulo (2^30)-1 on a separate line.
Example Input:
3
1 10
2 4
3 8
Output:
1
3
10
I made this code and it works, but when i have 1000 inputs i get **Timelimit ** in evaluator, can you help me make code that will work faster?
def generate_combinations(d, c, current_combination=None, combinations=None):
if current_combination is None:
current_combination = []
if combinations is None:
combinations = []
if d == 0:
if c == 0:
if all(current_combination[i] <= current_combination[i + 1] for i in range(len(current_combination) - 1)):
combinations.append(list(current_combination))
return
for i in range(c + 1):
generate_combinations(d - 1, c - i, current_combination + [i], combinations)
return combinations
c = 8
d = 3
pocet = int(input())
for i in range(pocet):
d, c = map(int, input().split())
print(len(generate_combinations(d, c)))
I also have version using dynamic programming
def dynamic_programming(d, c):
dp = [[0] * (c + 1) for _ in range(d + 1)]
dp[0][0] = 1
for i in range(1, d + 1):
for j in range(c + 1):
dp[i][j] = dp[i - 1][j]
if j >= i:
dp[i][j] += dp[i][j - i]
dp[i][j] %= (2 ** 30 - 1)
b = dp[d][c]
return dp[d][c]
q = int(input().strip())
for i in range(q):
d, c = map(int, input().split())
print(dynamic_programming(d, c))
For better understending here is the example if we want to divide 8 candies among 3 children we have 21 possibilities:
[0, 0, 8]
[0, 1, 7]
[0, 2, 6]
[0, 3, 5]
[0, 4, 4]
[0, 5, 3]
[0, 6, 2]
[0, 7, 1]
[0, 8, 0]
[1, 0, 7]
[1, 1, 6]
[1, 2, 5]
[1, 3, 4]
[1, 4, 3]
[1, 5, 2]
[1, 6, 1]
[1, 7, 0]
[2, 0, 6]
[2, 1, 5]
[2, 2, 4]
[2, 3, 3]
[2, 4, 2]
[2, 5, 1]
[2, 6, 0]
[3, 0, 5]
[3, 1, 4]
[3, 2, 3]
[3, 3, 2]
[3, 4, 1]
[3, 5, 0]
[4, 0, 4]
[4, 1, 3]
[4, 2, 2]
[4, 3, 1]
[4, 4, 0]
[5, 0, 3]
[5, 1, 2]
[5, 2, 1]
[5, 3, 0]
[6, 0, 2]
[6, 1, 1]
[6, 2, 0]
[7, 0, 1]
[7, 1, 0]
[8, 0, 0]
And there is only 10 possibilities that fit for this task:
[0, 0, 8]
[0, 1, 7]
[0, 2, 6]
[0, 3, 5]
[0, 4, 4]
[1, 1, 6]
[1, 2, 5]
[1, 3, 4]
[2, 2, 4]
[2, 3, 3]
Consider that each assignment of candies is an integer partition of n candies into k parts. Also note that for each partition of n candies, there is a single unique assignment candies to children that is valid (e.g. for n=7 the partition 3 3 1 can only be mapped to children in one way, [0, 3, 3], anything else would be invalid).
With this, we just need to count the number of k-partitions of n, which has a nice recursive formula:
p(0, 0) = 1
p(n, k) = 0 if n <= 0 or k <= 0
p(n, k) = p(n - k, k) + p(n - 1, k - 1)
Now, we need to be careful- this formula counts non-empty partitions, but we allow giving a child 0 candies. We could alter the recurrence relation, but there's a simpler approach; if we just add 1 additional candy per each child at the start, and then imagine we just remove that one candy from their part afterwards, it'll be just as if we allowed empty partitions.
Implemented in python:
from functools import cache
@cache
def count_parts(candies, children):
if candies == children == 0:
return 1
if candies <= 0 or children <= 0:
return 0
return count_parts(candies - children, children) + count_parts(candies - 1, children - 1)
Example usage:
test_cases = [(10, 1), (4, 2), (8, 3)]
for candies, children in test_cases:
print(count_parts(candies + children, children))
Output:
1
3
10
This will be O(C*D) time and space, A bottom-up dynamic programming solution would have the same time complexity but would be slightly faster in practice and could be made to have a linear (in terms of C) space complexity.
The details are escaping me at the moment, but I believe there's also an early-exit shortcut calculation for p(2*k, k) that could be used for further speedup as well.