Editorial for Alex y la IOI

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: dcordb

Denotemos como $a$ ~a~ y $b$ ~b~ al primer y segundo aeropuerto, $id[i]$ ~id[i]~ denota el $id$ ~id~ del $i$ ~i~-ésimo aeropuerto, entonces:

Si $id[a] = id[b]$ ~id[a] = id[b]~ la solución es $0$ ~0~, ya que ambos aeropuertos pertenecen a la misma compañía.
Si $id[a] \neq id[b]$ ~id[a] \neq id[b]~ la solución es $1$ ~1~. Para ver esto distinguimos tres casos:
- No hay aeropuertos entre $a$ ~a~ y $b \; (|a - b| = 1)$ ~b \; (|a - b| = 1)~, en este caso se puede volar directamente con costo $1$ ~1~.
- Existe un $0$ ~0~ entre los aeropuertos $a$ ~a~ y $b$ ~b~, en este caso se puede volar desde el aeropuerto con $id = 0$ ~id = 0~ hasta este y desde este hasta el otro aeropuerto.
- Existe un $1$ ~1~ entre los aeropuertos $a$ ~a~ y $b$ ~b~, en este caso se puede volar desde el aeropuerto con $id = 1$ ~id = 1~ hasta este y desde este hasta el otro aeropuerto.

Complejidad: $O(1) + O(n) = O(n)$ ~O(1) + O(n) = O(n)~ (el $O(n)$ ~O(n)~ viene por leer la entrada).

Comments

1

aniervs commented on March 20, 2021, 7:50 p.m.

La editorial no está explicando realmente por qué el costo es $1$ ~1~ cuando son diferentes. Le falta decir que se pueden elegir siempre dos aeropuertos de distintos $id$ ~id~ adyacentes.