Dificultad: Fácil
Problema:
Dadas $N$, ($1 ≤ N ≤ 10000$) ubicaciones enteras $A_i$ ($0 ≤ A_i ≤ 10^9$) y un entero $K$ ($0 ≤ K ≤ 10^9$) para cada rana, determinar si la rana $A$ ubicada en la posición $i$ puede comunicarse con la rana $B$ en posición $j$. Las ranas en posicion $i$ y $j$ se pueden comunicar siempre que entre ellas la distancia sea $ ≤ K$ o entre ellas existan otras ranas que cumplan con la anterior condición. Las ranas son muy amigas y entre ellas se pasan el mensaje.
Solución:
Nos damos cuenta que cuando a una rana le llegue un mensaje esta se lo podría pasar a cualquiera otra que estuviera a menos de una distancia $K$ de su posición, por tanto partiendo de ese punto formaremos grupos de ranas que estarán comunicadas entre si, para lo cual usaremos union-find.
De entrada lo que debemos de hacer es ordenar las posiciones de cada rana, manteniendo el índice original en el cual estaban, posteriormente recorremos nuestro arreglo ya ordenado para unir a las ranas que se pueden comunicar.
De entrada lo que debemos de hacer es ordenar las posiciones de cada rana, manteniendo el índice original en el cual estaban, posteriormente recorremos nuestro arreglo ya ordenado para unir a las ranas que se pueden comunicar.
Complejidad: $O(N log N)$ debido a la ordenación de las ubicaciones.
Código (C++):
Para facilitarnos las cosas emplearemos un arreglo la clase
pair
, otro arreglo de enteros llamado roots
(necesario para la estructura union-find y las funciones join
y root
habituales) y unas definiciones para darle un poco de claridad al código:
#define place second #define distance first typedef std::pair<int,int> frog;
Una vez leídas las posiciones de las ranas, las ordenamos con respecto a la distancia en la que están, y recorremos el arreglo para unir a las que se puedan comunicar:
for(int i = 1; i <= N; i++){ roots[i] = i; scanf("%d", &frogs[i].distance); frogs[i].place = i; } std::sort(frogs+1, frogs+N+1); for(int i = 1; i < N; i++){ if(frogs[i + 1].distance - frogs[i].distance <= K){ join(frogs[i + 1].place, frogs[i].place); } }
Una vez terminada las uniones basta con leer las consultas y determinar si la rana $A$ se puede comunicar con la rana $B$:
root(a) == root(b) ? printf("Yes\n") : printf("No\n");
No hay comentarios on "Chef and Frogs (FROGV - CodeChef)"