You are not logged in. Please login at to post your questions!



Can you share your approach for the question Towers of Baskland ( link : ) ?

asked 01 Feb '17, 13:58

pankajkhan's gravatar image

accept rate: 15%

Given: A set of numbers from 1 to N (possible non zero height of towers)


Task: to arrange the towers in increasing or decreasing order (that is, with repetitions)


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:


The solution to this equation is N+K-1CK, here N=K so we get:


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


answered 01 Feb '17, 17:05

swetankmodi's gravatar image

6★swetankmodi ♦♦
accept rate: 15%

edited 01 Feb '17, 17:06


Can you exlain the part N+K-1CK ? How did you reach that formula? Are not you talking about stars and bars problem?

(01 Feb '17, 18:31) bansal12325★

yes, check out theorem 2 from this link The number of non-negative integer value solutions of the equation x1+x2+....+xk=N is N+k-1Ck

more detailed explanation here

(01 Feb '17, 19:43) swetankmodi ♦♦6★

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

(01 Feb '17, 19:46) swetankmodi ♦♦6★

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) bansal12325★

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

(01 Feb '17, 21:22) swetankmodi ♦♦6★

Nice explanation! and approach :)

(02 Feb '17, 01:24) bansal12325★
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$ .
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 . I precomputed all the factorials and their modular inverses and then multiplied them .

Our code


answered 01 Feb '17, 17:12

bhishma's gravatar image

accept rate: 11%


Can you please elaborate your pascal triangle part?

(01 Feb '17, 19:30) bansal12325★

Thanks for the link to the Quora thread.

(01 Feb '17, 23:15) pankajkhan5★

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

As you can see the entries of the table are the diagonals of the triangle

(01 Feb '17, 23:47) bhishma4★

But how can [6 3 1] counted as increasing sequence ?

(02 Feb '17, 01:55) bansal12325★

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) bhishma4★
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:


question asked: 01 Feb '17, 13:58

question was seen: 631 times

last updated: 02 Feb '17, 02:16