Can you share your approach for the question Towers of Baskland ( link : https://www.codechef.com/AGOF2017/problems/ALGFLXQH/ ) ? asked 01 Feb '17, 13:58

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 x_{i} 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: x_{1}+x_{2}+x_{3}+....+x_{N}=N The solution to this equation is ^{N+K1}C_{K}, here N=K so we get: ^{2N1}C_{N} 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*^{2N1}C_{N}  N to calculate this very fast, use Lucas Method, For complete implementation check my submission here answered 01 Feb '17, 17:05
1
Can you exlain the part ^{N+K1}C_{K} ? How did you reach that formula? Are not you talking about stars and bars problem?
(01 Feb '17, 18:31)
1
yes, check out theorem 2 from this link The number of nonnegative integer value solutions of the equation x_{1}+x_{2}+....+x_{k}=N is ^{N+k1}C_{k} more detailed explanation here
(01 Feb '17, 19:43)
1
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 x_{i} >=0
(01 Feb '17, 19:46)
1
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?
(01 Feb '17, 21:09)
2
i considered x_{i} 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..
(01 Feb '17, 21:22)
Nice explanation! and approach :)
(02 Feb '17, 01:24)
showing 5 of 6
show all

Let $F(idx , curr)$ denote the number of possible non decreasing sequences from index $idx$ and placing $curr$ at index $idx$ . 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 . I precomputed all the factorials and their modular inverses and then multiplied them . Our code answered 01 Feb '17, 17:12
1
Can you please elaborate your pascal triangle part?
(01 Feb '17, 19:30)
Thanks for the link to the Quora thread.
(01 Feb '17, 23:15)
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 TriangleAs you can see the entries of the table are the diagonals of the triangle
(01 Feb '17, 23:47)
But how can [6 3 1] counted as increasing sequence ?
(02 Feb '17, 01:55)
1
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.
(02 Feb '17, 02:16)
