Contest Duration: - (local time) (100 minutes) Back to Home

F - Figures Editorial by evima

Let $$S = \sum_i d_i$$.

If $$S \geq 2\left(N-1\right)$$:

We will choose one special hole for each part.

Let us use the $$N-1$$ connecting components one by one as follows:

• Do the following $$N - 2$$ times.

• Choose an unused non-special hole.
• Among the special holes in parts that are disconnected from the part with the chosen hole, choose an unused one.
• Connect these two holes.
• Finally, connect the two unused special holes.

Then, in each part, the hole nearest to the last added connected component will be the special hole.

The number of ways to complete the figure in this way is:

\begin{aligned} \prod_i d_i \times \left(S-N\right)\left(S-N-1\right)\cdots\left(S-2N+3\right) \times \left(N-1\right)! \end{aligned}

Here, each way to complete the figure is counted multiple times for different order of adding edges, so the answer in this case is:

\begin{aligned} \prod_i d_i \times \left(S-N\right)\left(S-N-1\right)\cdots\left(S-2N+3\right) \end{aligned}

If $$S < 2\left(N-1\right)$$:

In this case, there are not enough holes to insert connecting components, so the answer is $$0$$. Here, if $$\left(N \leq \right) S < 2 \left(N - 1\right)$$, we have the following:

\begin{aligned} \prod_i d_i \times \left(S-N\right)\left(S-N-1\right)\cdots\left(S-2N+3\right) = 0 \end{aligned}

\begin{aligned} \prod_i d_i \times \left(S-N\right)\left(S-N-1\right)\cdots\left(S-2N+3\right) \end{aligned}