enunciado Torneo Chuck Norris

[Mario Storti]

COUNTSETS: CONTAR CONJUNTOS DIFERENTES
======================================

El problema consiste en determinar de una serie de N conjuntos de
enteros de tamaño variable S_j, cuántos de ellos son
diferentes. Los conjuntos vienen concatenados en un vector<int> v,
viniendo los elementos de cada conjuntos separados por un entero
-1. Por ejemplo si v=[3,2,1,-1,5,4,-1,3,2-1,4,5,-1] entonces los conjuntos
son S0={1,2,3}, S1={4,5}, S2={2,3}, S3={4,5}. En este caso el programa
debe retornar 3, ya que S1 y S3 son el mismo conjunto. La función a
escribir es int count_sets(const vector<int> &v);.

Como caso test, si tenemos

S0={4 }
S1={4 3 }
S2={8 2 3 4 7 }
S3={8 }
S4={6 1 9 4 7 }
S5={5 7 }
S6={8 7 4 9 }
S7={6 1 7 3 }
S8={3 7 9 }
S9={4 }
S10={7 8 1 9 }
S11={5 2 6 8 }
S12={3 6 1 7 }
S13={6 9 5 0 }
S14={8 0 }
S15={3 4 9 7 2 5 }
S16={5 4 }
S17={2 5 1 }
S18={5 0 7 }
S19={5 9 0 8 }

Entonces la función debe devolver 18, ya que de los 20 conjuntos dos
de ellos están repetidos (S9=S0 y S7=S12). (Este caso se puede generar
en el programa poniendo el juego de parámetros que está indicado como
"CASO DE PRUEBA".)

NOTAS:
. Los valores de los conjuntos están en el rango [0,RAND_MAX)

. El número de conjuntos es N=1000000, los conjuntos tienen un número
aleatorio de elementos de entre 1 y 5.

. Los elementos de los conjuntos están desordenados dentro del
vector.

. La función es llamada ntimes=40 veces (esto es sólo a efectos de
poder medir con mayor precisión el tiempo de ejecución) sobre 40
vectores distintos. Por lo tanto el programa imprime 40 números por
stdout. Concretamente los primeros 4 enteros son:

909549
909677
909488
909632

. Los datos están generados de manera que aproximadamente un 10% de
los conjuntos están repetidos. Es decir que los conteos de conjuntos
diferentes están cerca de 900000.

. Se provee un archivo template `countset.cpp' que implementa una
solución básica usando set<set<int>>. Está solución tarda unos 2.5min en
un i7-2630 @ 2.00GHz.

. Por si les sirve al llamar al compilador estamos agregando una
bandera DOMJUDGE, es decir (g++ -DDOMJUDGE...) de manera que en el
código pueden usar

#ifdef DOMJUDGE
// Aca seguro que estoy corriendo en el
// servidor DOMjudge del torneo...
#endif

para no tener que andar comentando código cada vez que hacen una
submisión.


--
-------------------------
Mario Alberto Storti [cel. +54-342-5122135]
CIMEC (INTEC/CONICET-UNL)
Predio CONICET-Santa Fe
Colect. Ruta Nac. 168 Km 472, Paraje El Pozo
3000 Santa Fe, Argentina
Tel: +54-342-4511594 (ext 1015), Tel/Fax: +54-342-4511169
Home: +54-342-4550193, e-mail: mario.storti at gmail.com
http://www.cimec.org.ar/mstorti
-------------------------