La primera solución posible es utilizar la función next_permutation de C++ para iterar todas las permutaciones posibles de 8 elementos. Por cada una de ellas, podemos probar emparejar al primero con el segundo, al tercero con el cuarto, y así siguiendo. De todas las formas vistas, se toma la mejor. Esta implementación simple alcanza para 10 puntos.

El problema con el algoritmo de fuerza bruta anterior, es que enumera los mismos emparejamientos muchísimas veces. Por ejemplo 1 2 3 4 = 3 4 2 1, ya que para ambas permutaciones el emparejamiento resulta ser el 1 con el 3 y el 3 con el 4. En general, cada emparejamiento está duplicado 2^(N/2) (N/2)! veces, de modo que la cantidad de emparejamientos distintos en verdad es mucho menos que N!. De hecho es solamente el "factorial impar" que obtenemos multiplicando los impares hasta N. Esto se puede ver bien si pensamos que al 1 hay que emparejarlo con alguno de los otros N-1, y ahora al primero (en índice) de los que quedan aún libres hay que emparejarlo con alguna de las N-3 opciones que quedan, y así siguiendo podemos enumerar las (N-1) (N-3) ... 3 * 1 opciones verdaderamente diferentes. Esta solución de fuerza bruta sin repetir debería llegar sin problemas a obtener 30 puntos.

Para llegar a 60 puntos, la cantidad de posibles emparejamientos auténticamente diferentes ya es demasiado grande y no se pueden probar todas. Pero se puede implementar un algoritmo clásico de programación dinámica con máscara de bits: dp[S] = "la respuesta al problema para el subconjunto S". Para calcularla recursivamente, miramos el primer bit encendido de la máscara y consideramos las opciones de con qué otro bit encendido emparejarlo, llamando recursivamente a la máscara con ambos apagados. La complejidad final es N 2^N, y alcanza los 60 puntos cómodamente. Existe una versión alternativa de este método de programación dinámica, en el cual en cada paso probamos todas las posibles N^2 parejas, en lugar de buscar solamente el compañero del primer bit sin emparejar. Dependiendo de la eficiencia que tuviera la implementación de cada participante, estas soluciones N^2 2^N obtenían 60 o 30 puntos.

Finalmente, para obtener 100 puntos se puede mejorar la recursión anterior para no tener que guardar y considerar las 2^N máscaras, ya que en verdad solo algunas de ellas (muy pocas) son posibles de obtener con la recursión mencionada. Como siempre para la recursión apagamos el primer bit y algún otro, los únicos estados que importan son aquellos alcanzables desde la máscara inicial (1<<N)-1 mediante varios pasos de este tipo. Se puede comprobar que esta cantidad de máscaras es solamente Fibonacci de N, que es round[((1+sqrt 5)/2)^N / sqrt 5]. Como Fibonacci de 30 es menos que 1 millón, esto alcanza para obtener 100 puntos si se implementa eficientemente. Por ejemplo, se puede utilizar unordered_map para los mapeos y tener cuidado de iterar únicamente los bits encendidos de la máscara, en lugar de preguntar siempre por los N bits.

Para analizar que son pocos estados note que solo son alcanzables estados que tengan una cantidad par de bits activos, y además si hay B bits inactivos, los primeros B/2 bits deben estar inactivos, debido a que el primer bit siempre se apaga en cada paso.

Otra alternativa que obtenía 100 puntos era utilizar un arreglo para almacenar las máscaras pequeñas eficientemente, pero luego utilizar un unordered_map para las más grandes. Una idea similar que también funcionaba consiste en realizar los primeros pasos de la recursión sin memoization, llegando rápidamente a máscaras pequeñas que pueden almacenarse directamente en un arreglo, y a partir de allí sí utilizar memoization.

En este último paso, implementaciones no tan eficientes pero que igualmente utilizan memoization para aprovechar que se recorren solamente algunos estados posibles obtenían 81 puntos.