Subtarea 1

Debido a que el número de pasos elevados es el mismo que el número de pisos, cada piso del edificio antiguo y el nuevo edificio deben estar conectados a un paso elevado. Esto da como resultado solo una posible permutación si y solo si todas las reubicaciones cumplen las condiciones.

La complejidad de esta solución es ~O (N)~.

Subtarea 2

Esta Subtarea se puede resolver mediante una búsqueda completa. Para cada posible permutación, verifique que todas las reubicaciones sean elegibles.

La complejidad de esta solución es ~O(N!)~.

Subtarea 3

Para facilitar la discusión, usemos las siguientes definiciones:

• Definición 1. El número de pisos ~i~ del edificio antiguo conectados al puente ~h_j~ que satisface ~i > H [j]~ se expresa en ~P_j~.

• Definición 2. El número de pisos ~i~ del edificio nuevo conectados al puente ~h_j~ que satisface ~i > H [j]~ se expresa en ~P'_j~.

• Definición 3. El número de pisos ~i~ del antiguo edificio conectados al puente ~h_j~ que satisface ~i = H [j]~ se expresa en ~Q_j~.

• Definición 4. El número de pisos ~i~ del edificio nuevo conectados al puente ~h_j~ que satisface ~i = H [j]~ se indica en ~Q'_j~.

• Definición 5. El número de pisos ~i~ del antiguo edificio conectados al puente ~h_j~ que satisface ~i < H [j]~ se expresa en ~R_j~.

• Definición 6. El número de pisos ~i~ del edificio nuevo conectados al puente ~h_j~ que satisface ~i < H [j]~ se expresa en ~R'_j~.

Si un piso del edificio antiguo está conectado a un puente con la misma altura, entonces ese piso puede reubicarse en todos los pisos del nuevo edificio conectado al puente.

Del mismo modo, si un piso en el edificio nuevo está conectado a un puente con la misma altura, entonces ese piso puede ser el resultado de reubicar cualquier piso en el edificio antiguo conectado al puente. Hay ~4~ casos que cumplen con las reglas de reubicación existentes:

• ~P_i + Q_i = R'_i + Q'_i~ y ~R_i = P'_i~.

• ~P_i + Q_i = R'_i~ y ~R_i = P'_i + Q'_i~.

• ~P_i = R'_i~ y ~R_i + Q_i = P'_i + Q'_i~.

• ~P_i = R'_i + Q'_i~ y ~R_i + Q_i = P'_i~.

Tenga en cuenta que si ~Q_i = 0~, habrá varios casos que serán equivalentes entre sí.

Usando la regla de la suma, cuente el número de permutaciones en cada caso y luego súmelas para obtener la respuesta deseada. Pero también tenga en cuenta que el conjunto de soluciones a estos casos concluirá en los siguientes casos: ~P_i = P'_i~, ~Q_i = Q'_i~ y ~R_i = R'_i~, lo que hace que el caso anterior se cuente ~2~ veces. Utilice el principio de inclusión-exclusión para resolver el caso.

La complejidad de esta solución es ~O(N)~.

Subtarea 4

Tenga en cuenta que la cantidad de formas diferentes de reubicación a través de un paso elevado no se ve afectada por otro paso elevado, por lo que podemos calcular la cantidad de formas diferentes de reubicación para cada paso elevado y luego usar la regla de multiplicación para obtener la respuesta final.

En esta subpregunta, se aplican los límites de ~Q_i = 0~ y ~Q'_i = 0~. De modo que para cada puente, solo hay 1 caso que puede ocurrir y cumplir con las reglas de reubicación existentes, a saber: ~P_i = R'_i~ y ~R_i = P'_i~. Itere todos los puentes, luego multiplique el número de permutaciones en cada puente para obtener la respuesta que desea.

La complejidad de esta solución es ~O(N)~.

Subtarea 5

Itere todos los puentes existentes, luego, para cada puente, el número de posibles permutaciones se puede calcular usando la solución de la Subtarea 5. Luego, multiplique el número de permutaciones en cada puente para obtener el respuesta deseada.

La complejidad de esta solución es ~O(N)~.