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

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

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

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

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?

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.