Petr contest


What is the approach to solve this problem, I tried to view this code

But I didn’t understand what logic he is using.

How the maximum possible teams could be = ((no. of players with no choice)/2)+1;

I mean, when petr tries to fill the choice of the players who have not filled the choice, he may get head every time so he will leave all those choices as it is, so answer could be equal to n if no player has filled the choice.

Lets first assume that all the choices except choice[0] are filled with no. other than -1.
so start with choice[1] till choice[n-1]. as you can only fill these choice with a number of the above coders so you will realise that we can only make one single teamof all the coders.
Now, if petr filled all the choices with -1 with some no. , there would be one team only as seen above otherwise each choice with-1 would make his individual team and this happens with a probability of 0.5.
hence if c be the no. of choice with -1(except the first one ). then
no. of teams=1(for all the choices without -1) + (no. of choice whichpetr did not fill himself )0.5
hence max no. of teams(when petr filled no choice and left all as -1) =1+ c

Thanks buddy!!