ALGOFLUX - ALGFLXQH

Can you share your approach for the question Towers of Baskland
( link : https://www.codechef.com/AGOF2017/problems/ALGFLXQH/ ) ?

1 Like

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

3 Likes

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
2 Likes

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

1 Like

Can you please elaborate your pascal triangle part?

1 Like

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]: https://en.wikipedia.org/wiki/Stars_and_bars_(combinatorics)
[2]:https://www.quora.com/If-a+b+c+d-20-how-many-unique-non-negative-integer-solutions-exist-for-a-b-c-d

1 Like

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

1 Like

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?

1 Like

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…

2 Likes

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 :slight_smile:

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.

1 Like
//