Enunciado MiniTorneo 2013 (previa al Torneo Chuck Norris)

Dados dos vectores A,B de enteros encontrar el tamaño #C de su intersección C (en el sentido de conjuntos). El programa sólo debe retornar un entero, el tamaño de la intersección. Por ejemplo, si A=[2 21 24 12 14 3 28 19 16 1 35 7 24 24 28 26 1 8 39 16] y B=[4 33 0 7 18 32 7 27 14 1 35 32 19 7 37 23 7 17 13 14] entonces la intersección es C=[14 19 1 35 7] y por lo tanto su tamaño es #C=5, el programa debe imprimir por stdout sólo el número 5. Los vectores se generan aleatoriamente, se provee un programa intersec.cpp en el cual el participante sólo debe modificar la función

int intersect_sz(const vector &, const vector &);" 

de forma eficiente. Esta función debe retornar el tamaño de la intersección de los conjuntos A y B. ATENCION: los vectores A y B pueden tener elementos duplicados.

El concurso consiste en resolver el problema cuando el tamaño de los conjuntos es N=50.000.000 (5e7), en ese caso la solución es #C=15.480.308 (por supuesto el programa debe ser genérico y funcionar para cualquiera vectores A y B). En intersec.cpp se incluye una versión del algoritmo que es cuadrática (O(N^2)) (de manera que no traten de llegar a N=5e7). Es muy simple obtener soluciones casi óptimas (O(n log(n)) o menores) por ejemplo usando trivialmente conjuntos (la clase set<>). Una solución más eficiente es ordenar los elementos en los vectores y usar una variante del algoritmo que usamos en el curso para hacer la intersección de conjuntos implementados con listas. En un procesador i7 2630QM @ 2.00GHz tarda 192 segundos la primera versión usando sets y 10 segundos usando el vector. Otra idea, puede ser usar tablas de dispersión (la clase unordered_set de las STL)...