# IOM Blitz Contest Proposed Problems

###### tags: `informatics`

## 1

JeO has an array of integers: $[9, 6, 13, 7, 1, 15, 1, 5, 4, 6]$. JeO wants to spread the array by using zero or more operations.

In one operation, JeO can choose an element $e > 1$ from the array, erases it, then writes down two new elements depending on the parity of $e$.
- If $e$ is even, JeO writes $e/2$ twice.
- If $e$ is odd, JeO writes $e-1$ and $1$ in that order.

Note that if the array only consists of $1$s, then JeO would no longer be able to apply any operations.

Before doing the operations, JeO wants to arrange the array elements in such a way to maximize the number of different arrays JeO can get from applying zero or more operations to that array. Two arrays $A$ and $A'$ are different if $|A| \neq |A'|$ or if there exists an index $i$ such that $A_i \neq A'_i$.

Find the number of possible different arrays JeO can get by applying zero or more operations.

### Solution

:::spoiler
Notice that because what we do to an element of the array doesn't affect any other elements, we can simply consider each element separately and apply the product rule to get the number of possible arrays. Because of this as well, the arrangement operation at the start of the procedure is pointless.

Let's define $f(x)$ as the number of possible arrays we can get from an array $[x]$. The base case is clear: $f(1) = 1$, because we cannot transform the array $[1]$ any more.

If $x \neq 1$, we can either leave the array as $[x]$, or we can transform this array (into $[x/2, x/2]$ if $x$ is even or $[x-1, 1]$ if $x$ is odd) and split it into two subarrays of length $1$ which we will recursively consider. Thus,
$$
f(x) = \begin{cases}
1, & x = 1 \\
1 + \left( f(x/2) \right )^2, & x \text{ even } \\
1 + f(x-1), & x \text{ odd }
\end{cases}
$$

Therefore, we can get the values of $f(x)$ for $1 \leq x \leq 15$ as follows.

| $x$ | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ | $7$ | $8$ | $9$ | $10$ | $11$ | $12$ | $13$ | $14$ | $15$ |
| ------ | --- | --- | --- | --- | --- | ---- | ---- | ---- | ---- | ---- | ---- | ----- | ----- | ----- | ----- |
| $f(x)$ | $1$ | $2$ | $3$ | $5$ | $6$ | $10$ | $11$ | $26$ | $27$ | $37$ | $38$ | $101$ | $102$ | $122$ | $123$ |

Our answer would be the product of all $f(A_i)$, which is
$$
\prod_{i = 1}^{10} f(A_i) = 11 \, 178 \, 486 \, 000.
$$
:::