GOCC18: Google Online Coding Challenge 2020 – New Grad (India)

El desafío en línea de Google (GOCC 18) 2020 para nuevos graduados 2021 se llevó a cabo el 26 de septiembre de 2020.

Fue una prueba en línea de 60 minutos y 2 preguntas de codificación para resolver. El examen se realizó en la plataforma HackerEarth.

El proceso es que primero su currículum debe ser preseleccionado para el examen.

Duración del examen – 1hr

Primera pregunta: RANGO DE CONSULTAS

Se le da una array A con N enteros. Debe responder consultas Q del siguiente tipo:

LR

Determine el conteo de números primos distintos que divide todos los valores de la array desde el índice L hasta el R.

NOTA: Considere la indexación basada en 1

Formato de entrada: 

• La primera línea contiene un número entero T que indica el número de casos de prueba.
• La primera línea de cada caso de prueba contiene un número entero N.
• La segunda línea de cada caso de prueba contiene N enteros separados por espacios que denotan A.
• La tercera línea contiene el número entero Q.
• A continuación, las líneas Q contienen dos números enteros separados por espacios que indican las consultas.

Formato de salida;

Imprima el conteo de números primos distintos que divide todos los valores de la array desde el índice L hasta el R.

Experiencia: he resuelto esto usando árboles de segmentos https://www.geeksforgeeks.org/segment-tree-set-1-range-minimum-query/ vea este artículo sobre consulta de rango mínimo, es similar a este problema.

Segunda pregunta: EL VALOR DE UN ÁRBOL PONDERADO

Se le proporciona un árbol no dirigido ponderado con N Nodes. Cada borde tiene un peso asociado.

Debe encontrar el valor de la función ∑(i=1 a N-1) ∑(j=i+1 a N) F(i,j) donde F(i,j) denota la suma de los pesos de los bordes en un camino simple entre los Nodes i y j.

Formato de entrada:

• La primera línea contiene un número entero T que indica el número de casos de prueba.
• La primera línea de cada caso de prueba contiene un número entero N que indica el número de Nodes en el árbol.
• Las siguientes líneas N-1 contienen tres enteros separados por espacios uvw que denotan un borde entre uyv con peso w.

Formato de salida:

Para cada caso de prueba, imprima el valor de la función módulo 10^9 + 7 en una nueva línea.