986 - How Many?

All about problems in Volume 9. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
joy
New poster
Posts: 48
Joined: Wed Oct 18, 2006 1:00 pm
Location: Dhaka, Bangladesh
Contact:

986 - How Many?

Post by joy » Thu Nov 16, 2006 8:35 pm

Code: Select all

hi,

I don
form kisui na ... class tai asol....
iF U hv d class u get the form....

ayon
Experienced poster
Posts: 161
Joined: Tue Oct 25, 2005 8:38 pm
Location: buet, dhaka, bangladesh

Post by ayon » Thu Nov 16, 2006 9:50 pm

Code: Select all

  /\   
/    \/\

    /\
/\/    \
ishtiak zaman
----------------
the world is nothing but a good program, and we are all some instances of the program

sakhassan
Experienced poster
Posts: 105
Joined: Sat Mar 11, 2006 9:42 am
Location: cse,DU

Post by sakhassan » Tue Nov 28, 2006 11:22 am

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

Thanks in advance
Time that gone is gone forever ...

User avatar
rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Post by rio » Tue Nov 28, 2006 4:07 pm

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
Experienced poster
Posts: 105
Joined: Sat Mar 11, 2006 9:42 am
Location: cse,DU

Post by sakhassan » Sat Dec 02, 2006 12:17 pm

Thanks buddy.... Now i can give a try :)
Time that gone is gone forever ...

joy
New poster
Posts: 48
Joined: Wed Oct 18, 2006 1:00 pm
Location: Dhaka, Bangladesh
Contact:

Post by joy » Sat Dec 02, 2006 12:52 pm

Is there any DP solution or anything......
form kisui na ... class tai asol....
iF U hv d class u get the form....

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

dp

Post by sohel » Sat Dec 02, 2006 1:45 pm

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
New poster
Posts: 18
Joined: Tue Jun 17, 2014 9:32 pm
Location: Hyderabad, India

Re: 986 - How Many?

Post by predicate » Thu Jul 02, 2015 1:39 pm

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

Post Reply

Return to “Volume 9 (900-999)”