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

×

ALGOFLUX - ALGFLXQH

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

pankajkhan's gravatar image

5★pankajkhan
1.2k10
accept rate: 15%


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

link

answered 01 Feb '17, 17:05

swetankmodi's gravatar image

6★swetankmodi ♦♦
6008
accept rate: 15%

edited 01 Feb '17, 17:06

1

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★
1

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★
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 xi >=0

(01 Feb '17, 19:46) swetankmodi ♦♦6★
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) bansal12325★
2

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

link

answered 01 Feb '17, 17:12

bhishma's gravatar image

4★bhishma
2977
accept rate: 11%

1

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

Follow this question

By Email:

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

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "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:

×890
×2

question asked: 01 Feb '17, 13:58

question was seen: 631 times

last updated: 02 Feb '17, 02:16