3128 - AND of Two

[ymondelo20]

http://coj.uci.cu/24h/problem.xhtml?pid=3128

[rvargas]

¿1000 ms no es un tiempo muy ajustado? La única solución java aceptada hasta el momento incluso sobrepasa ese tiempo

[ymondelo20]

La lectura es notable.
Probablemente si sea poco tiempo.
Escribe al autor, y que valore a ver.

[Dariel]

Alguna idea de como solucionar este problema en tiempo menor O(N^2).

[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

[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.

[rvargas]

Suena muy bien, lo voy a intentar

Edit: ¡TLE!

[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.

[rvargas]

Intentare filtrar los repetidos...

Edit: No, aun no.