3128 - AND of Two

Discussion around the problems of the COJ.
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.
Post Reply
User avatar
ymondelo20
Posts: 1968
Joined: 8 years ago
Location: Universidad de las Ciencias Informáticas
Gender: None specified
Contact:

3128 - AND of Two

Post by ymondelo20 » 4 years ago



"Every problem has a simple, fast and wrong solution" OJ's Main Law. ;)

rvargas
Posts: 37
Joined: 6 years ago
Gender: None specified

Re: 3128 - AND of Two

Post by rvargas » 4 years ago

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

User avatar
ymondelo20
Posts: 1968
Joined: 8 years ago
Location: Universidad de las Ciencias Informáticas
Gender: None specified
Contact:

Re: 3128 - AND of Two

Post by ymondelo20 » 4 years ago

La lectura es notable.
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. ;)

User avatar
Dariel
Posts: 51
Joined: 8 years ago
Location: Santiago de Cuba
Gender: None specified
Contact:

Re: 3128 - AND of Two

Post by Dariel » 4 years ago

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

HaZard
Posts: 114
Joined: 5 years ago
Location: Camagüey - Cuba
Gender: Male
Contact:
Cuba

Re: 3128 - AND of Two

Post by HaZard » 4 years ago

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
teruel

humbertodiaz
Posts: 97
Joined: 5 years ago
Gender: None specified

Re: 3128 - AND of Two

Post by humbertodiaz » 4 years ago

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
Posts: 37
Joined: 6 years ago
Gender: None specified

Re: 3128 - AND of Two

Post by rvargas » 4 years ago

Suena muy bien, lo voy a intentar :D

Edit: ¡TLE! :cry:

humbertodiaz
Posts: 97
Joined: 5 years ago
Gender: None specified

Re: 3128 - AND of Two

Post by humbertodiaz » 4 years ago

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
Posts: 37
Joined: 6 years ago
Gender: None specified

Re: 3128 - AND of Two

Post by rvargas » 4 years ago

Intentare filtrar los repetidos...

Edit: No, aun no.

Post Reply

Return to “Problem set”