Editorial for Puentes aéreos


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: humbertoyusta

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).


Comments


  • 3
    Josue_17904  commented on May 7, 2021, 1:46 a.m.

    Creo q hay un pequeño error en la explicacion de la subtarea 5.