Bases de Liga de Programación de omegaUp

omegaUp Invita a todos los estudiantes de nivel media superior y superior a participar a la 2° edición de la Liga de programación omegaUp.

 

Reglas:

 

  • Deben ser estudiantes de Preparatoria, Licenciatura, Maestría, Doctorado o Postdoctorado.
  • Los puntos otorgados por cada problema serán tomados como parte del puntaje final.
  • El primer AC de cada etapa recibirá 10 puntos extras.
  • Problemas resueltos parcialmente serán tomados en cuenta.
  • Para determinar los ganadores se utilizará como criterio el número de puntos obtenidos y como segundo criterio el número de AC que tenga a lo largo de las etapas, es decir gana el quien tenga mayor cantidad de puntos y en caso de ser necesario mayor número de problemas resueltos correctamente. 

 

Dinamica:

 

  • La Liga de Programación omegaUp contará con diferentes etapas a lo largo del 2022 y parte del 2021.
  • Al final de cada concurso se entregan los puntos correspondientes a cada participante.
  • Al llegar a la etapa final de la liga de programación de omegaUp se sumarán todos los puntos de cada participante que se obtuvieron durante todas las rondas y se premiará al participante que más puntos haya sumado.

 

Premios:

 

  • Los premios para los primeros 3 lugares se darán trofeos únicos.
  • Cada participante recibirá una constancia de participación.
  • Se entregará un reconocimiento especial y playeras personalizadas a los mejores 10 participantes.
  • Los participantes tendrán la oportunidad de hacerte notar con empresas de tecnología que están buscando talento en Ingeniería de Software.

 

Lenguajes de programación permitidos:

 

  • C
  • C++
  • Java

 

Cualquier punto no especificado en esta convocatoria, será resuelto por el Comité Organizador y su decisión será inapelable.

Resolviendo problemas con un límite bajo de memoria

Gracias @Rodrigo-RCC por este aporte!

El límite de memoria de un problema puede cambiar drásticamente la forma en la que podemos resolverlo. Por ejemplo, el problema https://omegaup.com/arena/problem/La-especie-dominante-en-marte nos pide encontrar el número que más se repite en una secuencia, si además sabemos que ese número aparece al menos más de la mitad de las veces. Si estamos usando C++ y conocemos relativamente bien la biblioteca estándar del lenguaje, nuestro primer intento sería algo así:

#include <iostream>
#include <map>

int main( ) {
 std::map<int, int> frecuencias;
 for (int n; std::cin >> n;) {
    frecuencias[n] += 1;
 }
 // revisar qué valor apareció más e imprimirlo
}

Si enviamos el código anterior, nos llevaremos la desagradable sorpresa de obtener `MLE` (memoria límite excedida). Aunque esta publicación no tiene por objetivo explicar cómo se resuelve el problema, sí podemos mencionar que lo adecuado es un *algoritmo de streaming* que surgió en el área de lo que ahora se conoce como *Big Data*. Entonces, el límite bajo de memoria es un intento de obligar al usuario a deducir dicho algoritmo, el cual usa únicamente tres variables enteras. Desafortunadamente, incluso el siguiente código…

#include <iostream>

int main( ) {
 // leer la entrada y no hacer nada con ella
 // no nos sabemos el algoritmo y tenemos poca memoria :(
 for (int n; std::cin >> n;) {
    continue;
 }
}

¡También supera la memoria límite del problema!

Un usuario podría pensar (equivocadamente) que entonces el problema es imposible de resolver. Para evitar esta confusión, los usuarios de la plataforma deben tomar en cuenta lo siguiente:

– Existe un único límite de memoria por problema, el cual es independiente del lenguaje de programación usado. En el problema descrito previamente, el autor no quiso aumentar artificialmente el límite de memoria sólo para aceptar envíos en todos los lenguajes, porque eso implicaría que alguien que use un lenguaje eficiente podría idear un algoritmo que no era el que el autor quería permitir. Entonces, es verdad que algunos problemas no se pueden resolver en ciertos lenguajes de programación, pero el autor debería garantizar que el problema se puede resolver de forma razonable en por lo menos un lenguaje de programación (de preferencia C y C++).
– La biblioteca `<iostream>` de C++ consume mucha más memoria de la que uno podría imaginar inicialmente. Esto se puede verificar resolviendo un problema de “Hola Mundo” usando `<iostream>` y luego comparándolo con uno que sólo usa `<stdio.h>`. Peor aún, basta incluir `<iostream>` para que el consumo de memoria del programa aumente, ya que la inclusión de ese archivo al menos provoca que los objetos globales `std::cin` y `std::cout` se inicialicen.

El siguiente código no calcula la respuesta correcta, pero al menos al menos no superará el límite de memoria 🙂

#include <stdio.h>

int main( ) {
 // leer la entrada y no hacer nada con ella
 // no nos sabemos el algoritmo :(
 for (int n; scanf("%d", &n) == 1;) {
    continue;
 }
}

Esperamos que esta publicación les haya ayudado a tener una idea más cercana de cómo atacar cierto tipo de problemas inusuales y los invitamos a resolver el problema mencionado en el juez en línea.

Análisis de diferencias en salidas para envíos de problemas educativos

Hemos liberado una nueva funcionalidad que será muy útil para los usuarios que comienzan a utilizar la plataforma, ya que contarán con una herramienta más para apoyarlos en su aprendizaje. Esta funcionalidad les permitirá ver un análisis de las diferencias entre las salidas que dan sus programas y las salidas oficiales para los envíos de problemas educativos.

¿En qué consiste el análisis de las diferencias?

Para todos los problemas educativos que accedan vía cursos, los usuarios podrán comparar el resultado que obtuvo la salida de la solución que acaban de enviar, contra el resultado que se espera de acuerdo a los casos que subió el creador del problema.

Ventajas

El uso de esta herramienta traerá beneficios, tanto para profesores como para estudiantes, los cuales se describen a continuación:

Profesor

  • Tiempo: Al permitir a los estudiantes ser más autodidactas, el profesor tendrá más tiempo para revisar temas de mayor relevancia o donde los estudiantes presentan más problemas. 

Alumno

  • Problemas auto didácticos: Al recibir retroalimentación más completa desde la plataforma, el estudiante puede realizar más problemas, los cuales lo irán guiando con las pistas para llegar a la solución de los problemas sin necesidad de contar con la figura del profesor.

¿Cómo funciona esta nueva herramienta?

Profesor

Lo primero que se debe tomar en cuenta por parte del profesor / creador de problemas es que el problema sea meramente educativo, quiere decir, que este no vaya a ser tomado en cuenta o ya se esté usando en concursos, ya que esto podría dar ventaja a usuarios que ya hayan visto las salidas esperadas. 

Una vez que ya se definió que el problema se utilizará con fines educativos se procede a la configuración. 

Si el problema es nuevo, se sigue el mismo procedimiento como para crear cualquier problema: Menú > Problemas > Crear un problema, donde se encontrará el siguiente campo:

Las opciones disponibles son:

  • Ninguno (predeterminado): El problema continúa como siempre ha existido, sin mostrar diferencias de salidas en los casos.
  • Sólo ejemplos: Se mostrarán las diferencias de salidas para todos los casos que se guardaron en el directorio examples.
  • Todos: Se mostrarán las diferencias de salidas para todos los casos que se agregaron en el archivo .zip, incluidos los ejemplos.

En caso de que el problema ya exista y se desee agregar esta configuración, se debe ingresar a la sección de editar problema de la forma tradicional: Menú > Usuario > Mis problemas, y después dar clic en el icono de Editar problema . En este formulario también se encontrará disponible la configuración:

El siguiente paso es agregar el problema a algún curso; recuerda que esta configuración sólo funciona en ese lugar.

 

Estudiante

Para que los estudiantes puedan aprovechar esta herramienta deben estar inscritos al curso que contenga problemas educativos. 

1.- El primer paso a realizar es ingresar al curso, tal como se hace tradicionalmente, seleccionar la tarea en la que estará trabajando y elegir el problema educativo.

2.- Después se debe enviar una solución y esperar a que el juez de omegaUp evalúe el envío. En el listado de envíos aparece el botón para ver los detalles, dar clic.

3.- En la ventana que aparece se mostrará la información de los casos, con su respectivo puntaje por cada grupo.

4.- Puedes presionar cualquiera de los botones   para ver la diferencia en las salidas de los casos, si todos los casos del grupo son los mismos que los esperados o si hay alguna salida que no coincide.

En la siguiente animación se puede ver su funcionamiento tal como le aparecerá al estudiante en el curso:

 

Cursos en omegaUp

Descubriendo y preparando al talento de Latinoamérica

Conoce nuestros cursos

En omegaUp los profesores:

  • Cuentan con más de 2000 problemas de calidad para utilizar como tareas y exámenes
  • Pueden observar el avance de sus estudiantes
  • Pueden identificar los temas que se están complicando a sus estudiantes.

En omegaUp los estudiantes:

  • Obtienen retroalimentación automática de sus soluciones
  • Aprenden habilidades que les serviran en su vida profesional

Conoce nuestros cursos

 

 

 

 

 

 

 

Soluciones de problemas en omegaUp

En este post queremos describirles cómo ver soluciones a los problemas en omegaUp. Para los autores de problemas también daremos algunos detalles sobre como agregar las soluciones a sus problemas.

En la vista de problema, en la parte superior podemos ver dos pestañas, Problemas y Soluciones.

Si ya resolviste el problema y quieres comparar tu solución con la solución oficial, al dar click en la pestaña de Soluciones, te mostrará un mensaje como este,

Y así verás la solución,

Por otro lado, si no has resuelto el problema el proceso para ver la soluciones será distinto.

  • Primero intenta resolverlo,
  • También puedes usar tokens para ver las soluciones. Por cada 10 problemas que resuelvas obtendrás un token. Ver una solución solo usa 1 token.
  • Si ves la solución sin antes resolver el problema, éste no te dará puntos en el ranking.

Puedes ver los tokens que tienes disponibles en las vistas de soluciones dando click en “Ver mis tokens actuales”,  y te mostrara un mensaje como en la imagen,

Para los autores de problemas

Si quieres incluir las soluciones a tus problemas debes añadir una nueva carpeta /solutions al archivo zip del problema. Dentro de la carpeta se debe agregar el archivo markdown con la solución. Las soluciones se pueden editar desde la plataforma, tal como las descripciones del problema.

Mas información aquí.

 

Reglas del Coder del Mes

El reconocimiento del Coder del Mes en omegaUp se hizo con el objetivo de reconocer a coders activos en la plataforma. A continuación listamos las reglas del programa.

  • Existen dos programas de Coder del Mes: Coder del Mes para Ellas y Coder del Mes General. Cada inicio de mes se publicarán los ganadores de los dos programas de Coder del Mes.
  • La ganadora del Coder del Mes para Ellas será elegida entre las usuarias que se han identificado con el género femenino en su perfil.
  • El Coder del Mes general no hará distinción de género.
  • Las personas ganadoras serán publicadas en la página principal de omegaUp.com durante el mes correspondiente.
  • La persona con el mayor puntaje acumulado durante el mes resolviendo problemas con distintivo de calidad* será el ganador del Coder del Mes General.
  • La usuaria con el mayor puntaje acumulado durante el mes resolviendo problemas con distintivo de calidad* será la ganadora del Coder del Mes para Ellas.
  • Debes seguir el Código de Conducta de omegaUp.
  • Es posible que se haga una publicación en redes sociales felicitando a los ganadores. Esto dependerá de los recursos disponibles de omegaUp. Dicha publicación incluye compartir información como el alias del usuario y el nombre del usuario.
  • Los administradores de los programas tienen el derecho de determinar la honestidad de los usuarios en sus soluciones utilizando diferentes métodos y descalificar al usuario si se encuentran violaciones.
  • Cualquier violación a estas reglas dará lugar a disposiciones de penalización, incluyendo descalificación al Rank General o a los programas de Coder del Mes.
*Los problemas con distintivo de calidad son aquellos que muestran EN el título del problema el siguiente icono: Dicho distintivo es asignado por el departamento de Educación de omegaUp.

 

omegaUp se reserva el derecho de declarar vacío el reconocimiento de ambos programas de Coder del Mes en cualquier momento. Así como de modificar en cualquier momento cualquiera de los puntos anteriores con o sin previo aviso.

Código de Conducta en omegaUp

omegaUp es una plataforma educativa y creemos que debemos fomentar un ambiente con respeto y la mismas oportunidades para todos. Por ello creamos el siguiente Código de Conducta, que debes cumplir para utilizar omegaUp.com.

  1. En general y en especial en los concursos, cursos, el blog y redes sociales de omegaUp se crea una comunidad, donde se espera que los usuarios actúen con respeto y empatía hacia los demás.
  2. Todos los códigos enviados por los usuarios deben estar dirigidos a resolver el problema y no a violar las reglas o desestabilizar el sistema (el juez).
  3. Los usuarios no deben participar en ninguna actividad injusta que influya en los resultados propios o de cualquier otro usuario.
  4. Se debe asegurar con el profesor del curso, u organizador del concurso, si está permitido el uso de libros, notas, herramientas y código que hayas escrito previamente.
  5. Todos deben respetar los derechos de autor. Esto significa que, si  se utiliza código de otra persona, el usuario debe contar con permiso explícito del autor original para hacerlo. Igualmente, los usuarios que desean añadir un problema de un tercero a la plataforma, deben seguir las reglas de reproducción o contar con permiso explícito del autor para hacerlo.
  6. El contenido que aporten los usuarios a la plataforma no debe ser inapropiado, ni ofensivo. Esto quiere decir que no se permite contenido que promueva insultos, acoso de ningún tipo, comentarios despectivos o publicar información personal de otros.
  7. Intentar extraer el código de otro usuario sin su permiso se considera trampa.
  8. Cualquier violación a estas reglas dará lugar a disposiciones de penalización, incluyendo descalificación al Rank General o a los programas de Coder del Mes o desactivación de la cuenta.

 

Soluciones de la Fase 2 de la Liga de Programación omegaUp

  1. Problema A

Las siguientes observaciones son claves para resolver el problema.

  1. Si p \leq n, entonces (w % p) < n. Así que el máximo residuo posible es n - 1.
  2. Si w satisface la condición del enunciado, entonces hay n - 1 diferentes residuos, luego los residuos son un subconjunto de n - 1 elementos, de la colección \lbrace 0, 1, \ldots , n - 1\rbrace.
  3. El mínimo común múltiplo de 1, 2, \ldots , n es mayor o igual al producto de los primos menores o iguales a n.
  4. El producto de los primos menores o iguales a 50 es mayor a 10^{18}

Veamos el caso donde 0 no forma parte de los residuos. De 1, vemos que

w % n = n - 1

w % n - 1 = n - 2

\ldots

w % 2= 1 .

Entonces w + 1 es un común múltiplo de 2, 3, 4,  \ldots,  n.

(*) Luego, de la observación 3 vemos que

mcm(2, 3, 4,  \ldots,  n) \geq P_n

 Donde P_n es el producto de los primos menores o iguales a n.

(*) Pero P_{50} > 10^{18}. Así que si w + 1 es un común múltiplo de 2, 3, 4,  \ldots,  n entonces n \leq 50.

Ahora el caso donde 0 sí forma parte de los residuos. Se sigue que existe 1 < k \leq n tal que w % k = 0. Con la misma lógica, de 1, vemos qué

w % k - 1 = k - 2

\ldots

w % 2= 1 .

Con ayuda de  (*), vemos que k \leq 50.  ¿Cuál es el orden de los residuos mayores a k?. Para esto, consideremos el mismo orden que usamos en el caso donde 0 no forma parte de los residuos.

El residuo k - 1 que originalmente pertenecía a k tiene dos direcciones: ser el residuo de un numero mayor que k, o k - 1 es el residuo que queda  descartado.

Sea M - 1 el residuo que queda descartado, entonces w + 1 debe ser común múltiplo de n, n - 1, n - 2, \ldots , M + 1, y para esto,

(w + 1) \geq n * (n - 1) * (n - 2)  * \ldots * (M + 1)

Lo cual sería imposible si n - M  \geq 50.

Ahora, si no descartamos los residuos de k + 1, \ldots , k + 50, entonces w + 1 \geq  (k + 1) * \ldots  * (k + 50) lo cual sería de nuevo imposible.

Por lo tanto, M + 50 > n y M - 50 < 1.

De modo que, si n > 100, la respuesta es “No”.  El problema ahora se limíta a n \leq 100 y w \leq 10^{18}.

Para éste problema, podemos guardar todos los residuos de w con los números menores o iguales a n en una estructura que nos maneje operaciones básicas de conjuntos, como un set. Usando el set, la respuesta es “Si”, si el tamaño del set después de añadir los residuos es n - 1, y “No” en caso contrario.

Tratemos cada query de manera independientemente, y nos tomamos a_1, a_2, \ldots, a_k como los puntos dados en la query.

El problema es equivalente a encontrar un círculo con el menor radio r posible, tal que todos los puntos de la query están dentro de él.  La respuesta sería el radio r.

Él cuál es un problema equivalente a encontrar el menor radio r tal que existe al menos un punto contenido en cada círculo con centro a_1, a_2, \ldots a_n y radio r.

Si dicho punto p existe, entonces existe al menos un par de círculos que se intersecten en algun punto T. Por supuesto, la distancia de p a T es menor o igual a r.

Por lo tanto, la respuesta puede ser encontrada con una búsqueda binaria.

  1. Fíjamos el radio r, el cual mandamos a la búsqueda binaria.
  2. Enumeramos los k círculos.
  3. Encontramos y enumeramos las intersecciones para cada par de círculos.
  4. Para cada intersección, recorremos cada centro. Si hay un centro a_ique tiene una distancia menor o igual a r entonces el menor radio que buscamos sí es menor o igual a r.

El costo de cada chequeo en la búsqueda binaria es O(k^3). Y la búsqueda binaria tiene un costo de aproximádamente 50 operaciones. Pero precalculando las soluciones, de 4, para todos los l puntos antes de contestar las preguntas, reducimos el costo del chequeo a O(k^2), lo cual ya es suficiente para resolver el problema.

Lo que buscamos, es la cantidad de subconjuntos tales que su \&  es igual a 0. Esta cantidad puede verse como la cantidad de subconjuntos totales, menos la cantidad de subconjuntos tales que su \& es diferente de 0. Ahora, esta cantidad puede verse como la cantidad de subconjuntos cuyo  \& tienen exactamente un bit prendido, más la cantidad de subconjuntos cuyo \& tienen exactamente dos bits prendidos, \ldots, más la cantidad de subconjuntos cuyo \& tienen exactamente 20 bits prendidos (esto ya que 10^6 \leq 2^{20}).

Para esto usaremos el principio de inclusión – exclusión. De modo que la cantidad que buscamos esta dada por

S_ 0 - S_1 + S_2 - S_3 + \ldots + S_{20}

Donde S_i nos dice cuantos subconjuntos tienen  un ~and~ con al menos i bits prendidos.

Ahora, S_i puede ser calculado con la ayuda de una SOS (Sum Over Subsets) DP.

Para esto,  sea mask alguna máscara de bits en [1, 2^{20}], y definamos m como el ~and~ de algún subconjunto del arreglo, tal que mask \& m = mask. Es decir, mask es una submáscara de m. Entonces, DP[mask] nos dice cuántas diferentes m existen. (dos m se consideran diferentes, si las posiciones de los elementos en el arreglo que la componen no son todas iguales). Está DP puede calcularse de la siguiente manera.

  1. Los casos base los formamos añadiendo la cantidad de ocurrencias de x en el arreglo, a DP[x].
  2. Fíjamos bit \in [1, 20], de izquierda a derecha.
  3. Para cada mask en [0, 2^{20}], tal que mask tiene el bit-ésimo bit apagado  (mas formalmente, mask \& (1 << bit)  = 0 ) se hace la transición DP[mask | (1 << bit)] += DP[mask].

De modo que S_i = 2^{DP[m]}, para cada m una máscara con al menos i bits prendidos.

Sean p_1, p_2, \ldots, p_m las posiciones de la cadena en donde hay un 1.

Definimos r cómo la posición donde yace la rana, y b como la cantidad de brincos que ha dado hasta el momento. Inicialmente, r = p_1 y b = 0. La respuesta puede encontrarse mediante siguiente algoritmo.

  1. Encontrar j tal que p_j - r \leq k y p_{j + 1} > k
  2. Hacemos

    b = b + 1 y r = p_j

  3. Repetimos mientras r \neq p_m.

La respuesta final es b. El algoritmo se puede implementar con complejidad lineal usando la técnica de two pointers (usando r y j como los pointers).

Rescatando la cantidad de ocurrencias para cada vocal (no hay que olvidarse de contar las mayúsculas) mientras recorremos la cadena, estamos listos para imprimir las tres respuestas. Las cuales son

(a)  Tamaño de la cadena.

(b)  Suma de las ocurrencias de cada vocal.

(c)  Imprimir la cadena de derecha a izquierda.

Salvemos los dos vectores dados a_1, a_2, \ldots , a_n y b_1, b_2, \ldots , b_n, y generemos un nuevo vector c_1 = (a_1 + b_1), \ldots, c_n = (a_n + b_n). La solucion es imprimir c_1, c_2, \ldots, c_n.

 

Todos los videos del curso de Introducción la Programación con C++

Actualización 10/04/20: El curso ha terminado y este post incluye los 11 videos.

Como parte de la iniciativa #QuédateEnCasaConOmegaUp estuvimos impartiendo un curso de Introducción a C++ en vivo a través de Facebook Live.

El material del curso está disponible de forma abierta y gratuita en la plataforma de omegaUp y puedes acceder en este enlace  (https://omegaup.com/course/introduccion_a_cpp) para ver el material y resolver los ejercicios en línea.

Aquí te dejamos un enlace a todos los videos y estaremos actualizando este post con cada video nuevo en la serie:

Continue reading “Todos los videos del curso de Introducción la Programación con C++”

Soluciones de la Fase 1 de la Liga de Programación omegaUp

Para este problema, consideramos un arreglo de ocurrencias O sobre los elementos del arreglo. De modo que la respuesta está dada por

\sum\limits_{i=A}^B O_{i}

Si consideramos el mismo arreglo de ocurrencias O sobre los elementos del arreglo, la respuesta está dada por O_k.

Podemos generar todos los elementos de la secuencia de Fibonacci hasta 30000, y guardarlos en un mapa M, de modo que M_k = 1 si k es un elemento de Fibonnaci, y M_k = 0 en caso contrario. Generamos la respuesta simplemente iterando desde i = 4 hasta i = N - 1, e imprimimos i si M_i = 0.

La clave para este problema, es usar variables que no provoquen un desbordamiento, por ejemplo, unsigned long long. Luego, es conocido que la serie de Fibonacci crece rápidamente, lo suficiente, como para generar la secuencia con todos sus elementos menores o iguales a N, guardando por cada uno su respectiva posición en ella. Por lo tanto, basta con checar si N es un elemento, e imprimir su posición. En caso de no serlo, imprimimos -1.

Este tipo de problema es conocido como straight-forward. Podemos guardar las estaciones de radio, y checar cuál estación es la mas cercana a la frecuencia dada, con una simple resta. En caso de haber dos estaciones con la misma distancia, la respuesta es la mayor. Solo debemos cuidar que la frecuencia esté dentro del rango permitido.

En este problema lo que tenemos es un grafo dirigido acíclico con aristas pesadas (intuitivamente, es un árbol, sin la propiedad de que cualquier par de nodos estan conectados por un único camino).
Los vértices son los eventos temporales, las aristas son dirigidas de p_i a i, y su peso es d_i. Además, cada vértice contiene un valor extra r_i. Un grafo que podemos asociar al primer caso de ejemplo es el siguiente.

Sean v_1 y v_k dos vértices distintos, tales que v_1 es ancestro de v_k. Es decir, existe un camino v_1 \rightarrow v_2 \rightarrow \ldots \rightarrow v_k en el grafo. Definimos S(v_1, v_k) como

\sum\limits_{i=1}^{k - 1} d_{v_i}

 

Es decir, la suma de los pesos en las aristas del camino.
De modo que el problema se convierte en: Para cada vertice v, contar cuántos vértices u en su “subárbol” \; existen tales que

r_u - S(v, u) \geq 0

Porque esto siginifica que tenemos suficientes segundos para viajar por el tiempo desde u hasta v.

Consideremos un arreglo E, donde la entrada E_v guarda cuántos descendientes u de v satisfacen

r_u - S(v, u) \geq 0

Pero

r_u - S(p_v, u) < 0

Donde p_v es el padre de v. Si v = 0, entonces no hace falta considerar a su padre, puesto que no podemos viajar por el tiempo a algún ancestro de 0 (ya que ni siquiera existe alguno).

En otras palabras, E_v guarda cuántos descendientes de v llegan a lo mas al vértice v.

También consideremos un arreglo D, donde la entrada D_v guarda cuántos descendientes u de v satisfacen

r_u - S(v, u) < 0

Es decir, D_v guarda cuántos descendientes de v no pueden llegar al vertice v.

Y además mantengamos un arreglo T, donde la entrada T_v guarda el tamaño del “subárbol” de v (incluyendo a v). En otras palabras, cuántos descendientes tiene v en total mas el mismo.

Por lo tanto, la respuesta final para el vértice v está dada por

(T_v - 1) - \sum\limits_{v \rightarrow u} (E_u + D_u)

donde u es un hijo directo de v.
Ya que esto calcula cuántos descendientes de v si pueden llegar a v.

Para el cálculo de nuestros arreglos, hacemos una dfs sobre el “árbol”  (partiendo del vertice 0). Para cada vértice u, hacemos una búsqueda binaria sobre un arreglo que mantenga la suma acumulada de los costos sobre las aristas que forman parte del camino de 0 a u, que nos devuelva el máximo ancestro v al que podemos llegar desde u.  Lo que nos dice que  E_v actualiza su valor a E_v + 1 (inicialmente, E_1 = E_2  = \ldots = E_n = 0). Esto se puede hacer usando un arreglo global. La idea es añadir la suma acumulada, luego explorar recursivamente el subárbol de u, y luego quitar la suma acumulada que añadimos. Esto es particularmente sencillo si usamos un vector de la STL para el arreglo global.

El arreglo T se calcula facilmente en la misma dfs, ya que

T_v = 1 + \sum\limits_{v \rightarrow u} (T_u)

Ahora podemos generar D, al estilo de programacion dinámica usando E. Notemos que

D_v = \sum\limits_{v \rightarrow u} (E_ u + D_u)

Lo que se puede hacer en la misma DFS.

Por lo tanto, nuestro algoritmo tiene complejidad O(Nlog(N)).

Primero reescribamos la expresión dada como

k = \dfrac{xy}{x + y}

De donde podemos despejar y como

y = \dfrac{xk}{x - k}

Sin perdida de generalidad, supongamos x \leq y, entonces se tiene

x \leq \dfrac{xk}{x - k}

x^2 \leq 2xk

x \leq 2k

Por lo tanto, podemos iterar x desde 1 hasta 2k, obtenemos y, y verificamos que k = \dfrac{xy}{x + y}, y > 0.

Guardamos las parejas que satisfazcan dichas condiciones y las imprimimos en el orden requerido, cuidando no repetir alguna respuesta.

Lo que nos deja con un algoritmo de complejidad O(k).

Una solución alternativa es la siguiente:

Te puedes dar cuenta que x, y > k, entonces el problema se convierte a  buscar a y b que cumplan

\dfrac{1}{k} = \dfrac{1}{k + a} + \dfrac{1}{k + b}

con a,b > 0. Si simplificas la igualdad llegas a que k^2 = ab, así que todo se reduce a encontrar las parejas de divisores a, b de k^2.  Lo que deja también un algoritmo de complejidad O(k).

Nota: Agradezco a José Tapia y a Carlos Galeana por su colaboración en el problema G.