Can you share your approach for the question Towers of Baskland
( link : CodeChef: Practical coding for everyone ) ?
Given: A set of numbers from 1 to N (possible non zero height of towers)
{1,2,3,…N}
Task: to arrange the towers in increasing or decreasing order (that is, with repetitions)
Solution:
Let xi denote the number of times the number(that is, height) i is chosen
We have N unique heights and we have to choose N numbers(not necessarily unique) and arrange them in ascending and descending order.
We can write:
x1+x2+x3+…+xN=N
The solution to this equation is N+K-1CK, here N=K so we get:
2N-1CN
The above is the number of ways we can arrange the height in ascending order.
To calculate the ways in descending order, we can simply multiply the above number by 2 since we can get the descending arrangement by reversing each ascending arrangement!
But wait,
what about the case where all the N numbers selected were same? (ie. 1111,2222,3333,4444 for N=4)
Reversing them will not produce a unique arrangement, but we have counted these occurrences as unique.
So, we need to get rid of the double counting. To do so, we can subtract N from the answer because there are only N occurrences where all the heights chosen are same.
Finally, the answer comes out to be 2*2N-1CN - N
to calculate this very fast, use Lucas Method, For complete implementation check my submission here
Let F(idx , curr) denote the number of possible non decreasing sequences from index idx and placing curr at index idx .
Now F(idx , curr) = \sum_{i = curr}^{N} F(idx + 1 , i) , base case F(N , i) = 1 , 1 <= i <= N
After computing the values , the number of non decreasing sequences is \sum_{i = 1}^{N} F(1 , i)
Each row in the table is the diagonal in the pascal triangle. Hence you’ll get the answer as \binom{2N - 1}{N}
Since the question also asks us to find the non increasing sequences , we can show that they also have the same recurrence as we had in the non decreasing case . But they both have the sequences such as 111...N\ times , 2222...N\ times in common, so we shouldn’t count them twice.
So the final answer is 2*\binom{2N - 1}{N} - N
For computing binomial coefficients mod prime , there are various [methods][1] . I precomputed all the factorials and their modular inverses and then multiplied them .
Our
[2]
[1]: https://www.quora.com/How-do-I-find-the-value-of-nCr-1000000007-for-the-large-number-n-n-10-6-in-C
[2]: https://www.codechef.com/viewsolution/12676486
Can you exlain the part N+K-1CK ? How did you reach that formula? Are not you talking about stars and bars problem?
Can you please elaborate your pascal triangle part?
yes, check out theorem 2 from this [link][1]
The number of non-negative integer value solutions of the equation
x1+x2+…+xk=N
is N+k-1Ck
more detailed explanation [here][2]
[1]: Stars and bars (combinatorics) - Wikipedia
[2]:https://www.quora.com/If-a+b+c+d-20-how-many-unique-non-negative-integer-solutions-exist-for-a-b-c-d
here you can consider the balls and bins both to be N. Basically i reduced the problem to finding the number of ways of solving the equation with each xi >=0
Ya i know these theorem but i wanna know about how did you relate this to this question where you are asked to form a non decreasing number?
i considered xi to be the number of times the height i is selected.
for n = 3 we have 17 such arrangements
111,112,113,122,133,123 and so on…
so when i chose 3 1’s my equation becomes 3+0+0=3
when i choose 122 my equation becomes 1+2+0=3
when i choose 133 my equation becomes 1+0+2=3
when i choose 112 my equation becomes 2+1+0=3
and when i choose 123 my equation becomes 1+1+1=3
and for decreasing order, the number of ways remain same just reverse the number like 112 becomes 211 123 becomes 321 and so on…
Thanks for the link to the Quora thread.
This will be the table for N = 3 . Rows denotes the index and columns represents the number placed at that index . So F[idx][curr] is the number of non decreasing sequences which has curr placed in index idx
\begin{bmatrix} 6 &3 &1 \\ 3 &2 &1 \\ 1 &1 &1 \end{bmatrix}
Pascal Triangle
![Pascal Triangle][1]
As you can see the entries of the table are the diagonals of the triangle
[1]: https://upload.wikimedia.org/wikipedia/commons/thumb/f/f6/Pascal’s_triangle_5.svg/250px-Pascal’s_triangle_5.svg.png
Nice explanation! and approach
But how can [6 3 1] counted as increasing sequence ?
It does not represent the sequence . The entry at the i^{th} row and j^{th} column represents the number of sequences possible if you place the number j at index i (i and j are one based indexed). So here F[1][1] = 6 means that there are 6 non decreasing sequences possible if you place 1 at position 1.