3128 - AND of Two
Forum rules
Remember that posting AC code is not allowed here. If you are going to ask a question or to post a solution, describe your algorithm instead. Posting AC code will be penalized.
Remember that posting AC code is not allowed here. If you are going to ask a question or to post a solution, describe your algorithm instead. Posting AC code will be penalized.
- ymondelo20
- Posts: 1968
- Joined: 9 years ago
- Location: Universidad de las Ciencias Informáticas
- Gender:
- Contact:
Re: 3128 - AND of Two
¿1000 ms no es un tiempo muy ajustado? La única solución java aceptada hasta el momento incluso sobrepasa ese tiempo 

- ymondelo20
- Posts: 1968
- Joined: 9 years ago
- Location: Universidad de las Ciencias Informáticas
- Gender:
- Contact:
Re: 3128 - AND of Two
La lectura es notable.
Probablemente si sea poco tiempo.
Escribe al autor, y que valore a ver.
Probablemente si sea poco tiempo.
Escribe al autor, y que valore a ver.
"Every problem has a simple, fast and wrong solution" OJ's Main Law. 

Re: 3128 - AND of Two
Alguna idea de como solucionar este problema en tiempo menor O(N^2).
Re: 3128 - AND of Two
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
1
3
3 3 16
teruel
-
- Posts: 97
- Joined: 6 years ago
- Gender:
Re: 3128 - AND of Two
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.
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
Suena muy bien, lo voy a intentar 
Edit: ¡TLE!

Edit: ¡TLE!

-
- Posts: 97
- Joined: 6 years ago
- Gender:
Re: 3128 - AND of Two
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.
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
Intentare filtrar los repetidos...
Edit: No, aun no.
Edit: No, aun no.