Need help for algorithm in combination problem

[Maggi Iggam]

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 !

[Maggi Iggam]

s

[coder777]

The problem is that you're facing three different scenarios:

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

something along that line

I don't see how this multiples of three coming in to play in your code

[Maggi Iggam]

@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 !!!

[ne555]

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)

[Maggi Iggam]

@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 :)

[Maggi Iggam]

@ne555 Help , i cant get dynamic Programming deployed here :(
In my last code i had added memorization , but that still results in time limit :(

[icegood]

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:

 
.._......._..
|..|.....|..|
|._|.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.

[icegood]

Sequence is too fine. Guess it could be done in O(log(N)) time...

[Maggi Iggam]

Let me implement it and see , it appears fine :D And thanks @icegood :)

[ne555]

@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.