1,000 participantes toman un examen que consta de 100 preguntas y 5 opciones por pregunta. ¿Cuál es el mejor enfoque (algoritmo) para encontrar todos los pares posibles de participantes con al menos un 80% de coincidencia en las opciones que eligieron?

Inicialmente pensé en el árbol de 5 arios. El siguiente nodo de cada nodo depende de la opción elegida. Esto significaría que el número total de nodos presentes son 5 ^ 0 + 5 ^ 1… + 5 ^ 99 = 5 ^ 100 -1. Luego, preprocesamos los nodos hoja y conectamos todos los nodos que se pueden obtener con un máximo de 20 opciones que se eligieron de manera diferente. Una vez hecho esto, podemos atravesar el árbol hacia abajo y luego, al llegar al nodo más inferior, podemos atravesar los nodos conectados que son 80% similares (ya que están conectados como una lista vinculada) y pueden tener cubos que contienen las personas que llegaron a esos nodos por el recorrido del árbol. Por lo tanto, obtienes los pares, pero el procesamiento previo involucrado es grande. Entonces, si el número de personas es n y el número de preguntas es k, entonces el tiempo máximo que necesita es O (k) para encontrar los pares una vez que se realiza el preprocesamiento.