You are here: Foswiki>Main/AED Web>ChuckNorris>CountSetsProblem (22 Mar 2013, MarioStorti)Edit Attach

Enunciado Torneo Chuck Norris 2013

El problema consiste en determinar de una serie de N conjuntos de
enteros de tamaño variable S_j, cuantos de ellos son
diferentes. Los conjuntos vienen concatenados en un vector 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 &v);. 

Como caso test, si tenemos

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

Entonces la función debe devolver 16, ya que de los 20 conjuntos 4 de
ellos están repetidos (S9=S0, S12=S7, S13=S7, y S17=S15). (Este caso
se puede generar en el programa poniendo el juego de parámetros que
está indicado como "CASO DE PRUEBA".) El vector "v" que se pasaria
como argumento a count_sets() sería v=[4,-1,4,3,-1,6,5,9,0,-1,...]. 

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 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 que implementa una solución
básica usando set>. 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. 

TEMPLATE: countset.cpp
Topic revision: r2 - 22 Mar 2013, MarioStorti
This site is powered by FoswikiCopyright © by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding Foswiki? Send feedback