P2210 [USACO13OPEN] Haywire B

Farmer John has $N$ cows ($4 \leq N \leq 12$, and $N$ is even). They set up a homemade system that allows cows and their friends to communicate through lines protected by hay bales. Each cow in the pasture has exactly $3$ friends, and the cows must be arranged in a single row of hay bales. A line of length $L$ occupies exactly $L$ hay bales to protect it. For example, if two cows are placed at hay bales $4$ and $7$ and they are friends, then we need $3$ hay bales to build the line that connects them. Assume that every pair of friends must be connected by a separate line, and we may rearrange the cows arbitrarily. Compute the minimum total number of hay bales required to build all the lines.

Line $1$: An integer $N$. For convenience, the cows are numbered $1 \sim N$. Lines $2, 3, \dots, N + 1$: Each line contains three integers in $1 \sim N$. The numbers on line $i + 1$ are the indices of cow $i$’s three friends. Obviously, if cow $i$ is one of cow $j$’s three friends, then cow $j$ is also one of cow $i$’s three friends.

A single integer representing the minimum number of hay bales required to build the lines.

Sample explanation: the best arrangement of the cows is $\{6, 5, 1, 4, 2, 3\}$, in which case we need only $17$ hay bales. Translated by ChatGPT 5