Editorial for COCI '12 Contest 5 #6 Mnogomet

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Before understanding the solution of the problem itself, some basic probability theory is required.

Independent events. If two events are independent, the probability of both events being realized is equal to the product of their individual probabilities.

Total probability. A complete set of alternatives is a set of disjoint events which together cover the entire sample space. If the only methods available to commute to school are by tram or on foot, then those two events form a complete set of alternatives for commuting to school. Now, the probability of an event in the same space can be expressed as follows:

$\displaystyle P(A) = P(N1) P(A \mid N1) + P(N2) P(A \mid N2) + \dots$ $P (A) = P (N 1) P (A ∣ N 1) + P (N 2) P (A ∣ N 2) + \dots$

For the commuting to school example, it can be applied as: the probability of arriving to school today ( $P(A)$ $P (A)$ ) is equal to the probability of going on foot ( $P(N1)$ $P (N 1)$ ) times the probability of arriving if going on foot ( $P(A \mid N1)$ $P (A ∣ N 1)$ ) plus the probability of going by tram ( $P(N2)$ $P (N 2)$ ) times the probability of arriving if going by tram ( $P(A \mid N2)$ $P (A ∣ N 2)$ ).

Input. From the input data it is possible, in a straightforward way, to find the probability of a player $A$ $A$ coming into possession of the ball one second after a player $B$ $B$ had the ball, as well as the probability of each team scoring if a player $C$ $C$ has the ball.

Computation. We will solve the problem in two steps. In the first step, we find the probabilities of events of the following types:

$\displaystyle \begin{align*} Pg(X, Y, T) &= P(\text{the first player of team }X\text{ has the ball, }T\text{ seconds later team }Y\text{ scores}) \\ Pm(X, T) &= P(\text{the first player of team }X\text{ has the ball, }T\text{ seconds later no team has scored}) \end{align*}$ $\begin{aligned} P g (X, Y, T) & = P (the first player of team X has the ball, T seconds later team Y scores) \\ P m (X, T) & = P (the first player of team X has the ball, T seconds later no team has scored) \end{aligned}$

where $X$ $X$ and $Y$ $Y$ are the labels of one of the teams, and $T$ $T$ is a positive integer. The probabilities $Pm$ $P m$ and $Pg$ $P g$ can be computed using dynamic programming, with the state {entity, number of seconds, team that had the ball in the beginning}, and the value for each state being the probability that the entity has the ball after the number of seconds has passed, where an entity can be any player or the goal of one of the teams. The relation relies only on the states in the previous second. In this step we assume that once a goal is scored, the ball remains in the goal. The time complexity of the first step is $\mathcal O(N^2 T)$ $O (N^{2} T)$ .

In the second step, we can ignore the individual players and their probabilities; the state is modelled by {current result, team, number of seconds}, with the value being the probability that after the number of seconds since game start, the team has just scored a goal, leading to the current result. For each state, the previous result is uniquely determined. The required probability can be decomposed to a complete set of alternatives which describe the second and the team that scored a goal in that second leading to that previous result. The solution for the current state is obtained as the sum, over all the alternatives, of the products of the probability of the alternative and the probability of a goal just being scored to obtain the current result, which can be read from the array $Pg$ $P g$ . The time complexity of the second step is $\mathcal O(R^2 T^2)$ $O (R^{2} T^{2})$ .

Output. The probability of an outcome can also be decomposed to a complete set of alternatives, describing the second when the last goal was scored. There must have been no scored goals from that moment to the end of the game, which is included by multiplying the probability from the second step with the $Pm$ $P m$ value for the appropriate time period.

However, if we are processing a winning result (with $R$ $R$ goals scored by one of the teams), we must not multiply in the $Pm$ $P m$ value, since the game has ended at that moment and the remaining time period is zero.

Comments

There are no comments at the moment.