Page 1 of 1

3128 - AND of Two

Posted: Fri Mar 06, 2015 12:23 pm
by ymondelo20

Re: 3128 - AND of Two

Posted: Fri Mar 06, 2015 8:01 pm
by rvargas
¿1000 ms no es un tiempo muy ajustado? La única solución java aceptada hasta el momento incluso sobrepasa ese tiempo :?

Re: 3128 - AND of Two

Posted: Sat Mar 07, 2015 12:23 pm
by ymondelo20
La lectura es notable.
Probablemente si sea poco tiempo.
Escribe al autor, y que valore a ver.

Re: 3128 - AND of Two

Posted: Thu Mar 19, 2015 7:20 pm
by Dariel
Alguna idea de como solucionar este problema en tiempo menor O(N^2).

Re: 3128 - AND of Two

Posted: Fri Mar 20, 2015 12:38 pm
by HaZard
realmente con una implementación en O(n*(n+1)/2) da bien, el truco está en que los números están entre 0 y 1000, estuve revisando tu última solución y está bastante parecida la idea a la de rafa5, pero ¿qué pasa con el caso siguiente?:
1
3
3 3 16

Re: 3128 - AND of Two

Posted: Fri Mar 20, 2015 8:58 pm
by humbertodiaz
Existe una solucion que corre en tiempo O(N). La solucion depende de examinar los bits de los datos, desde el mas significativo hasta el menos significativo. Existen dos opciones para cada bit:

1. Existen al menos dos datos que tienen un 1 en el bit que se esta examinando. En ese caso, aplicarle AND a esos dos valores dara un resultado con un 1 en esa posicion tambien. Ese bit tiene un valor mayor que la suma de los bits que quedan a la derecha. Por lo tanto, cualquier dato que no tenga un 1 en esa posicion no podra dar un resultado mayor, y se pueden descartar esos datos.

2. No existen al menos dos datos que tienen un 1 en el bit que se esta examinando. Entonces, no se le puede aplicar AND a ninguna combinacion de datos para obtener un 1 en esa posicion. Es claro que irrespectivamente de que par se escoja al final, el resultado tendra un 0 en esa posicion.

Esas pistas deben dar una buena idea de lo que se necesita para completar una solucion rapida.

Re: 3128 - AND of Two

Posted: Sat Mar 21, 2015 1:51 am
by rvargas
Suena muy bien, lo voy a intentar :D

Edit: ¡TLE! :cry:

Re: 3128 - AND of Two

Posted: Sat Mar 21, 2015 3:03 am
by humbertodiaz
Te puedo ofrecer algunas optimizaciones adicionales que podrian ayudar, aunque no se que tan util esto sea en Python. No se si el TLE sea por el algoritmo, por alguna estructura de datos, o por lectura de datos (como en Java).

Nota que pueden haber hasta 10^5 datos, pero los valores deben estar en el rango [0, 10^3]. Eso quiere decir que van a haber datos repetidos en los peores casos. Los puedes filtrar con una tabla de frecuencias. Digamos que encuentras que un valor X es el valor maximo que aparece mas de una vez. Como X salio dos o mas veces, sabes que puedes aplicar X AND X, dando un resultado de X. Entonces no necesitas procesar ningun valor menor que ese X, por que cualquier AND con tales valores solo puede dar un resultado menor que X. Queda verificar si algun par de valores mayores que X da un resultado mayor. Ademas, X solo se tiene que incluir dos veces - no es util incluirlo mas veces.

Eso explica lo que Teruel sugirio antes - el algoritmo cuadratico (intentar todos los pares de numeros) puede ser practico cuando solo hay ~1000 datos. La optimizacion que mencione permite lograr eso.

Re: 3128 - AND of Two

Posted: Sat Mar 21, 2015 3:42 am
by rvargas
Intentare filtrar los repetidos...

Edit: No, aun no.