SOCIAL - Editorial

PROBLEM LINKS

Practice
Contest

DIFFICULTY

MEDIUM

EXPLANATION

The chef chooses a random derangement of the chairs as the follow-ups. If we focus our attention on a single guest, that guest will be back in their original seat after R ringings if and only if the cycle they belong to has a length that divides R. Thus, for each divisor D of R not exceeding N, we count the number of derangements where a specific element (say, the first one) belongs to a cycle of length D, then divide by the total number of derangements. This will give us the probability of a single guest being back in his/her original seat. To get the expected number of guests, simply multiply by the total number of guests. The total number of derangements where the first element belongs to a cycle of length D is the total number of possible cycles ((N-1)!/(N-D)!), times the number of derangements on (N-D) elements. The number of derangements is calculated by the recurrence derange[0]=1, derange[1]=0, derange[i]=(i-1)*(derange[i-1]+derange[i-2]).

SETTER’S SOLUTION

Can be found here.

TESTER’S SOLUTION

Can be found here.

//