11600 - Masud Rana

All about problems in Volume 116. 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
battirunner
New poster
Posts: 14
Joined: Fri Aug 15, 2014 3:48 pm

Re: 11600 - Masud Rana

Post by battirunner » Thu Dec 25, 2014 1:55 pm

i don't get the sample input output of this problem.... why the day is represented in fraction ? it'll be very helpful if anyone just enlighten it

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11600 - Masud Rana

Post by brianfry713 » Tue Jan 06, 2015 5:42 am

Expected number of days can be a floating point. Read about probability.
Check input and AC output for thousands of problems on uDebug!

battirunner
New poster
Posts: 14
Joined: Fri Aug 15, 2014 3:48 pm

Re: 11600 - Masud Rana

Post by battirunner » Fri Jan 09, 2015 11:08 am

but how in this problem ? If you please explain just 2 sample input & output of the question ,, thanks in advance...

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11600 - Masud Rana

Post by brianfry713 » Fri Jan 09, 2015 10:15 pm

First sample input, on day 1 he will travel to either city 2 or 3. After that all cities are connected by safe roads.

Second sample input, After day 1 there is a 2 / 3 chance he will travel to city 2 or 3 - I will call this 1a, there is a 1 / 3 chance he will travel to city 4 - I will call this 1b.
E(0) = 1 + 2 / 3 * E(1a) + 1 / 3 * E(1b)

1a: Cities 1, 2, and 3 are connected, he is in city 1, 2, or 3. There is a 2 / 3 chance he will go to city 1, 2, or 3 (remember that he always chooses a new city other than the one he's staying in), There is a 1 / 3 chance he will go to city 4. If he travels to city 4 then all cities are connected, if he travels to city 1, 2, or 3 then we are in the same situation 1a.
E(1a) = 1 + 2 / 3 * E(1a)
Solving for E(1a) = 3

1b: Cities 1 and 4 are connected, also 2 and 3 are connected, he is in city 1 or 4. There is a 1 / 3 chance he will go to city 1 or 4, There is a 2 / 3 chance he will go to city 2 or 3. If he travels to city 2 or 3 then all cities are connected, if he travels to city 1 or 4 then we are in the same situation 1b.
E(1b) = 1 + 1 / 3 * E(1b)
Solving for E(1b) = 3 / 2

Solving for E(0) = 1 + 2 / 3 * 3 + 1 / 3 * 3 / 2 = 3.5
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 116 (11600-11699)”