Khushi and Pokemon Cards from (game of codes) contest

general
1

I am getting WA but can figure it out .

Can anyone point out the mistake in the code /approach .Thanks

Link to question: https://www.codechef.com/GOC2018/problems/KHCARD

Link: https://www.codechef.com/viewsolution/17837277

2

@john_smith_3 can u explain the mistake/approach?

3

Soultions are not visible, I wonder why. I tried using the birthday paradox formula, didn’t work.

4

Initially ans = 1.0, i =1
The solution was to simply iterate from 2:
ans = ans*(N-i)/N
If ans < 0.5: print i; break
Else i++;

Reason this works
This won’t give tle because of birthday paradox. The loop terminates pretty quickly.

Even for N = 1e9, loop terminates around 38000, thus getting AC.

2 Likes
5

I tried using the birthday paradox formula:

ans=floor(sqrt(-2 x log(.5) x n));

Which gives the number of people needed to get probability of same choice 0.5.

Any idea why this didn’t work?

6

@taran_1407 can u explain the approach i.e y we are using the formula ??

7

Yes.
Just see that when i people have been invited, the next person has (n-i) choices out of possible n choices, so that all invited people see distinct cards. This way, ans represent probability of i people selecting cards. If ans*(N-i)/N is greater than 0.5, it makes sense to invite one more person, so the loop continues. Otherwise we report answer.