Index

In this problem, we consider two partitions of the number $n$: \lambda = a_1 + a_2 + \dots + a_k and \mu = b_1 + b_2 + \dots + b_l. Each partition defines certain edges in a graph with $n$ vertices as follows:

For the first partition, vertices $1$ and a_1, $2$ and a_1-1, and so on, are connected. If a_1 is odd, the middle vertex remains unconnected. For the second partition, vertices a_1+1 and a_1+a_2, a_1+2 and a_1+a_2-1, etc., are connected in a similar fashion. Edges corresponding to the second partition are added in the same way (multiple edges may occur in the graph).

For example, if n = 10, \lambda = 3+4+2+1, and \mu = 3+5+2, then in the resulting graph there will be two edges between vertices $1$ and $3$, vertex $4$ will be connected to $7$ and $8$, $5$ to $6$ and $7$, $6$ only to $5$, $7$ to $4$ and $5$, $8$ to $4$ and $9$, $9$ to $8$ and $10$, and $10$ only to $9$.

Vitya is interested in the index of a pair of partitions, which is defined as 2b + a, where $a$ is the number of chains in the graph and $b$ is the number of rings. A chain is a connected component that allows an ordering of the vertices such that every two consecutive vertices are connected by an edge and there are no other edges. A ring is a chain with an additional edge connecting its end vertices. A connected component is a connected subgraph to which no vertex can be added without losing connectivity. An isolated vertex is considered a chain.

In the example above, the graph has one ring (consisting of vertices $1$ and $3$) and two chains: $(2)$ and (6, 5, 7, 4, 8, 9, 10). Therefore, the index of this pair of partitions is $4$.