techgig july edition part 3

techgig july edition part 3

There is problem statement on techgig :
Davis is playing a very interesting mathematical game. He has collection
of sticks of length 1,2,3,....,N. He is making hexagon out of his
collection by using 6 sticks for each hexagon. He considers a hexagon
"good" if the biggest stick has length at least L and lengths of all the
other sticks are not more than X. A "good" hexagon does not have sticks of
the same length more than K times.
How many ways he can make a "Good" hexagon?
Input/Output Specifications Input Specification: Input contains four
integers-
N( 2 <= N <= 10^9)
L ( 2 <= L <= N and N-L<=100)
X( 1<=X< L )
K ( 1 <= K <= 5)
Output Specification: Output the number of different ways to make a "Good"
hexagon % 1000000007
Examples
Example:1 when N=8, L=7, X=5, K=3: { 1,2,2,5,5,7 } is a good hexagon but
{1,2,2,2,2,7}, { 1,2,3,4,5,6},{1,2,3,4,6,7} are not.Two hexagons are
considered different if their side length sets are different.
For example {1,2,3,4,5,6} , {1,1,1,2,2,3} and {1,1,2,2,2,3} are all
different hexagons. But {1,2,3,4,5,6} and { 2,4,6,1,3,5} are not
different.
Example:2 When N=10, L=8, X=6, K=2 Output: Total hexagons= 374
Note: Please return -1 for invalid cases.
I am trying to solve it by calculating different combinations and adding
it together, my approach(probably wrong) is as below :
def factorial(x):
if x<=1:
return 1
else:
return x*factorial(x-1)
def combination(n,r):
return (factorial(n)/(factorial(n-r)*factorial(r)))
def goodHexa(N,L,X,K):
a=combination(N-L+1,1)
c=0
if K>=1: #total no. of combination without repeating any number
b=combination(X,5)
print b
if K>=2:
b+=combination(X,3)*3 #one number occurs twice
print b
b+=combination(X,4)*4 #two number occurs twice
print b
if K>=3:
b+=combination(X,2)*2 #one number occurs 3 times and one 2 times
b+=combination(X,3)*3 #one number occurs 3 times
if K>=4:
b+=combination(X,2)*2 #one number occurs 4 times
if K>=5:
b+=X #one number occurs 5 times
return (a*b)
what is wrong in my approach? what are other ways to solve this problem ?