986 - How Many?

[joy]

Code: Select all

hi,

I don

[ayon]

Code: Select all

  /\   
/    \/\

    /\
/\/    \

[sakhassan]

I too really confused about the problem ?? can u pls explain ?

Thanks in advance

[rio]

Explain of (3, 1, 2):

There are five kind of mountains for n = 3.

Code: Select all

                                      /\
           /\         /\     /\/\    /  \
/\/\/\    /  \/\   /\/  \   /    \  /    \

1st mountain has 3 peek of height 1, 0 peek of height 2, 0 peek of height 3.
2nd and 3rd mountain has 1 peek of height 1, 1 peek of height 2, 0 peek of height 3.
4th mountain has 0 peek of height 1, 2 peek of height 2, 0 peek of height 3.
5th mountain has 0 peek of height 1, 0 peek of height 2, 1 peek of height 3.

So the number of mountains that has exactly r = 1 peek of height k = 2 is 2 (2nd and 3rd).

Other examples of n = 3.
(3, 0, 2) = 2 (1st and 5th)
(3. 0, 1) = 2 (4th and 5th)
(3, 2, 1) = 0 (none)
(3, 1, 3) = 1 (5th)
(3, 0, 4) = 5 (all)
(3, 1, 4) = 0 (none)

I hope this helps.
----
Sory for my poor English.

[sakhassan]

Thanks buddy.... Now i can give a try

[joy]

Is there any DP solution or anything......

[sohel]

Yes, this is a dp problem.

I basically optimized dp[x][y][p][a]..
..ie how many ways I can come to coordinate x,y with p peaks and 'a' indicates last move(down hill or uphill ).

So ultimately the required answer is dp[2*N][0][R][0] // 0 -> downhill

[predicate]

some random test cases for debugging:
input :

Code: Select all

3 1 2
10 3 2
10 5 4
20 5 4
20 1 2
20 0 1

output :

Code: Select all

2
2002
69
282172814
1767263190
2892818244