### Need help for algorithm in combination problem

Pages: 12
Thanks dude , @ne555 & @mik2718 thanks a lot . It works , i spent so many days only to notice i had kept p instead of n and thought algo was wrong ! XD . And if you could tell what concept was behind this wonderful algo , it would really help not only me but also many - it was first combinatorical question i had faced ! Thankyou once again !
s
Last edited on
The problem is that you're facing three different scenarios:

even numbers -> 2n/2
odd numbers -> 2n/2 + 1
multiples of three -> 2int(n/3)

something along that line

I don't see how this multiples of three coming in to play in your code
@coder777 i couldnt make a word of what you said - i just applied the recursive relation for N(k) with k & p(k) with base cases just as ne555 had told ? for k=1 or 2 p=1 else for rest p=2 and used that recursive relation "N(K) = P(K) + \sum_{J=1}^{K-1} P(J) N(K-J)" . Thats what i did , i cant get what you speak about 3 scenarious ?

And even for three scenarious , how can i get Negative numbers as answer !!!
Last edited on
Overflow.
You need to compute the modulo at each step
(a+b) mod m = (a mod m + b mod m) mod m

The concept is dynamic programming'

By the way, your implementation is O(n^2). If you get TLE, will need to change it to O(n)
@ne555 , okay fixed the overflow :D Let me now implement Dynamic Programming !

And yeah , i am first using O(n^2) algo , then if it works then i will try to implement O(n) , step by step :)
Last edited on
@ne555 Help , i cant get dynamic Programming deployed here :(
In my last code i had added memorization , but that still results in time limit :(
I don't know whether my solution is better or worse (or even same), just let me describe.
At least mathematically it's simple to calculate all those tilinigs. For k>=1 call tiling to be strongly k-divided, if it consists of two subtilings, one of them covers 2x[1...k] and rest covers 2x[k+1...N], and there is no l<k with same property within considered tiling. Moreover call first subtiling (which covers 2x[1...k] )
to be fundamental for strongly k-dividing.
Notice that for k<=2 there are exactly one fundamental k-tiling, namely
__ - for k=1
|| - for k=2
For rest k>=3 there are exactly two fundamental ones:
 1234  .._......._.. |..|.....|..| |._|.and.|_.| `

for k=4 e.g. (stupid padding, cannot show better)

It remains to notice that each tiling is strongly k-divided for some k. If F(n) - number of tilings for 2x[1...n] then last sentence leads to formula:

F(N)=F(N-1)+F(N-2)+ 2*sum(F(k), k=1..N-3)
If G(n)=sum(F(k), k=1..N) then

F(N)=2*G(N-1)-F(N-1)-F(N-2)
and
G(N)=G(N-1)+F(N-1)

so algorithm could be done in O(1) memory and O(N) time without any dynamic programming stuff.
Last edited on
Sequence is too fine. Guess it could be done in O(log(N)) time...
Let me implement it and see , it appears fine :D And thanks @icegood :)
@icegood: good job. The concepts are the same, but you changed the formula in order to be computed in O(n) time.
> without any dynamic programming stuff.
Oh, but you are using dynamic programming.
Topic archived. No new replies allowed.
Pages: 12