Nacional 2019 Nivel 3: Ayudando al electricista

Problemas Nivel 3
#1

Hago este post para que discutamos ideas sobre el problema “Ayudando al electricista” de Nivel 3.

electricista.pdf (232,2 KB)

#3

Perdón por republicar el post pero me faltaron unos detalles y no podía editarlo :no_mouth:
¡Hola! Quiero tirar unas ideas que no pude terminar en código para saber si aunque sea estaba bien orientado.
Los casos en los que se debía devolver -1 se controlan con unos ifs pero prefiero entrar directo a la solución gorda.
Primero que nada la idea era contar cuántas hojas tenía el árbol y restar esa cantidad de cables ya que es obligatorio que pase un cable por cada roseta. Entonces voy a llamar c a la cantidad de cables restantes y r a la cantidad restante de rosetas (las no hojas). La idea era ir cambiando la disposición de los cables restantes entre las rosetas restantes quedando:
\frac{c \cdot (c - 1) \cdot (c - 2) \cdot \dots \cdot (c - r + 1)}{r!} \% mod.
El gran problema aparecía al momento de sacar el módulo ya que al ser división no era posible aplicar el truco de hacer el módulo en cada cálculo.
Para resolver esto pensé en factorizar cada multiplicando del numerador y guardar en una tablita la cantidad de factores cada factor que tiene. Sería con el siguiente código.

Código de la tablita de factores primos 1/2 
while(m != 1){ //m es cada multiplicando
  factores[criba[m]]++;
  m /= criba[m];
}

Y luego hacer lo mismo con cada multiplicando del denominador pero en vez de sumar 1 restar.

Código de la tablita de factores primos 2/2 
while(m != 1){ //m es cada multiplicando
  factores[criba[m]]--;
  m /= criba[m];
}

Entonces ya tenemos los factores primos del resultado, por lo que basta recorrer la tablita y multiplicar todo para tener el resultado. Acá ya se puede aplicar lo de aplicar el módulo por cada operación. Para que esto funcione en n \log n (n siendo el tamaño de la tablita) se debe elevar en tiempo logarítmico. Código abajo.

Operación final con la tablita 
ll res = 1;
for(int i = 2; i < n; i++){
  res *= expmod(i, factores[i]);
  res %= mod;
}
return int(res);

¿Es correcto esto o hay algún otro truco para hacer esa operación grande? Gracias :slight_smile:

3 Me gusta
#4

Correcto! Eso es muy parecido a la solución original del autor del problema, ya pueden probarlo en el juez online!! :slight_smile:

Un detalle es que no hace falta hacer potenciación logarítmica, ya que se multiplican pocos factores (del orden de n \lg \lg n como máximo) y de hecho todos esos factores que se van a multiplicar ya se iteraron al sacar la factorización, así que si pudimos recorrerlos, podemos multiplicarlos.

3 Me gusta