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

×

FTRIP - Editorial

3
2

PROBLEM LINKS

Practice
Contest

DIFFICULTY

SIMPLE

PREREQUISITES

Simple Math

PROBLEM

In your class of S students, N students are being selected to go on a trip. Your friend circle has M students in the class, including you. You will only enjoy the trip if you have at least K other friends with you.

What is the probability that you will enjoy the trip if you are selected?

QUICK EXPLANATION

Firstly, by Bayes' Theorem we know that we must find

  • P = number of ways that N students are selected from S students, such that you are selected and at least K of your friends are selected (from your M-1 other friends)
  • Q = number of ways that N students are selected from S students, such that you are selected

The result will be P/Q.

EXPLANATION

Q = (S-1)C(N-1)

Since you are already chosen, we need to select N-1 more students out of the S-1 students left.

To find P, we can iterate over the number of friends chosen.

P = 0

for f = K to min(M-1,N-1)
    P += (M-1)Cf * (S-M)C(N-f-1)

We iterate from K to min(M-1,N-1), since the cap on the number of friends who can come with you on the trip is defined by either the remaining number of slots, or the number of friends you have.

The term that we add for counting the number of ways of choosing f friends should be straight forward. The two terms in the product are

  • number of ways of choosing f friends from a corpus of M-1 friends, and
  • number of ways of choosing the students for the remaining slots from a corpus of students who are not your friends

We can precalculate the values of nCr for all n and r because the limits are small. None of the calculations will overflow.

The overall complexity of the algorithm is dominated by the precalculation of the combinations. Otherwise, the complexity of processing each case is linear.

SETTER'S SOLUTION

Can be found here.

TESTER'S SOLUTION

Can be found here.

This question is marked "community wiki".

asked 14 May '13, 15:26

gamabunta's gravatar image

1★gamabunta
2.4k128183169
accept rate: 14%

edited 14 May '13, 17:50

http://discuss.ww2.codechef.com/questions/9554/field-trip-getting-tle. Some body plz give the exact reason for tle. So that I could keep that in mind in future.

(15 May '13, 09:53) timepass1232★

  1. Why "k = Max(K, N-1 + M-S)" is used as initial value of k in the solution ?
  2. Its given atleast K friends so loop starts only from K and so on upto min(m-1,n-1).

2nd Part is quite obvious. Please Clarify the first part.

link

answered 15 May '13, 10:45

al3x1784's gravatar image

2★al3x1784
041416
accept rate: 0%

edited 15 May '13, 12:21

Haven't you checked the line We iterate from K to min(M-1,N-1), since the cap on the number of friends who can come with you on the trip is defined by either the remaining number of slots, or the number of friends you have. ?

(15 May '13, 12:16) bugkiller3★

I think you have misinterpreted my question. I want reason for 1st part.

(15 May '13, 12:23) al3x17842★
2

Suppose, if number of students going N-1(Alice being already selected) is greater than S-M(students who are not Alice's friend). i.e, N-1>S-M then atleast N-1-(S-M) = N-1+M-S friends of Alice will certainly go. Hence, we start iteration from max(K, N-1+M-S). Hope this helps.

(15 May '13, 18:35) bit_cracker0073★

@bit_cracker007 without considering that case also the solution is turning out to be same, could you please tell what is the reason? This solution is the proof, the assert statement should give error but the code was accepted.

(13 Oct '13, 12:28) sudharkj3★

:O For some reason I thought C[1000,500] had 2500 digits, so I used logarithms instead. http://ww2.codechef.com/viewsolution/2111679

Edit: Turns out I'd checked the digits of 1000!/500!*500! and not 1000!/(500!*500!) >.<

link

answered 14 May '13, 17:36

sanchit_h's gravatar image

6★sanchit_h
24617
accept rate: 0%

edited 14 May '13, 17:39

logarithms, good point ;-)

(14 May '13, 17:47) betlista ♦♦3★

Cool solution! :)

(14 May '13, 18:45) bugkiller3★

i too feared overflow .. so i used prime numbers to calculate factorials and got AC :) i used the property that n! contains ([n/p]+[n/p^2]+[n/p^3]+....) powers for any prime p

link

answered 15 May '13, 15:25

rroxxovv's gravatar image

4★rroxxovv
462
accept rate: 0%

I was afraid that this will lead to WA, that I used formulas how to calculate nCr from nCr - 1 or nCr + 1. Because we can see, that in

P += (M-1)Cf * (S-M)CN-f-1

M-1 and S-M are constants...

link

answered 14 May '13, 15:46

betlista's gravatar image

3★betlista ♦♦
16.9k49115225
accept rate: 11%

Shouldn't the limit be "min(M-1, N-1)" instead of "max(M-1, N-1)"?

link

answered 14 May '13, 16:05

srihari's gravatar image

4★srihari
3113
accept rate: 0%

it should. thanks for pointing it out! Fixed.

(14 May '13, 17:51) gamabunta1★

I used Pascal's Triangle for precomputing nCr
Link for solution

link

answered 14 May '13, 16:59

milhaus's gravatar image

2★milhaus
464
accept rate: 0%

edited 15 May '13, 08:20

I used the natural logarithm while checking whether the number whose logarithm was being taken is 0 or not. C(1000,500) had approx. 300 digits, far too big to be stored in an integer. I rather stored the ln of the factorials, and computed ln C(n,k) = ln(n!)-ln(k!)-ln((n-k)!). My soln. had precalculated 1000 values, and so I was interested to know whether anyone else used logs or not, and was happy to read sanchit_h ' s comment!

If you don't have allergy to Pascal , here is my soln :

http://ww2.codechef.com/viewsolution/2080331

link

answered 14 May '13, 18:06

mbrc's gravatar image

6★mbrc
1252511
accept rate: 0%

In the fear of Overflow , I used 'Gamma function' for approx. factorial and got AC :)

link

answered 14 May '13, 20:16

sam_ooooo's gravatar image

3★sam_ooooo
1
accept rate: 0%

Hey.. I solved this problem by dynamic programming.. using pascal's triangle.

I was able to solve it using top-down approach.

However getting segmentation error in bottom up approach. :(

link

answered 28 May '13, 20:48

swapniel99's gravatar image

3★swapniel99
16123
accept rate: 0%

1

finally.. bottom dyn progrmmng up also wrkd.. :D http://www.codechef.com/viewsolution/2183722

(28 May '13, 21:22) swapniel993★
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:

×15,680
×1,173
×281
×246
×18

question asked: 14 May '13, 15:26

question was seen: 6,268 times

last updated: 13 Oct '13, 12:29