3526 - Unordered List

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.
User avatar
ymondelo20
COJ Administrator
Posts: 1968
Joined: Sun Nov 13, 2011 12:32 pm
Location: Universidad de las Ciencias Informáticas
Gender: None specified
Contact:

3526 - Unordered List

Postby ymondelo20 » Thu Feb 18, 2016 8:23 pm



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

User avatar
frankr
Posts: 49
Joined: Fri Nov 18, 2011 8:09 pm
Location: Las Tunas
Gender: Male

Re: 3526 - Unordered List

Postby frankr » Sat Jun 11, 2016 10:30 pm

Es posible resolver este problema en O(n log n) pero sin usar ABI (Fenwick Tree) ni Segment Tree?

User avatar
isaac
Posts: 83
Joined: Mon Oct 26, 2015 6:20 pm
Gender: None specified

Re: 3526 - Unordered List

Postby isaac » Mon Jun 13, 2016 12:47 pm

Frank, creo que si. Estuve probando y mi solucion fue de lo mas simple. Tengo una cola Q que guarda enteros, inicialmente vacia. Leo los datos de forma habitual y voy del final hasta el inicio de los enteros de entrada haciendo la siguiente operacion:

1-> Busco la posicion del primer numero mayor que el actual (upper_bound de algorithm).
2-> Guardo en otro arreglo, en esa posicion, la cantidad que hay en la cola - la posicion encontrada, que es la cantidad requerida.
3-> En esa posicion de la cola, inserto el numero actual analizado.

La cuestion es ir del final al inicio y tener los datos analizados, ordenados para poder hacer una busqueda binaria, lo cual daria mas o menos n log n.

Marcelo
Posts: 2
Joined: Sun Apr 03, 2016 9:53 pm
Gender: None specified

Re: 3526 - Unordered List

Postby Marcelo » Mon Jun 13, 2016 8:08 pm

isaac, la solucion que tu le das al problema no tiene la complejidad O(nlogn), no se como esta implementado exactamente el deque de c++, pero de seguro o hacer upper_bound es lineal, o hacer insert es lineal, y por tanto la complejidad de tu solucion es O(n^2). Creo que el deque esta implementado con vectores, en cuyo caso hacer insert es O(n) en el peor caso.

User avatar
ymondelo20
COJ Administrator
Posts: 1968
Joined: Sun Nov 13, 2011 12:32 pm
Location: Universidad de las Ciencias Informáticas
Gender: None specified
Contact:

Re: 3526 - Unordered List

Postby ymondelo20 » Mon Jun 13, 2016 10:21 pm

Las pilas y colas de C++ son ciertos tipos de dequeue con restricciones de inserción y eliminación, el dequeue en concreto es una lista doblemente enlazada que sin restricciones permite insertar y eliminar en ambos extremos. Como es de imaginar, las operaciones de búsqueda e insertar en cierta posición son lineales. Insertar/eliminar en los extremos, así como acceder a un elemento si es O(1).
"Every problem has a simple, fast and wrong solution" OJ's Main Law. ;)

User avatar
frankr
Posts: 49
Joined: Fri Nov 18, 2011 8:09 pm
Location: Las Tunas
Gender: Male

Re: 3526 - Unordered List

Postby frankr » Tue Jun 14, 2016 9:17 pm

Todavía sigue abierta mi pregunta:
Es posible resolver este problema en O(n log n) pero sin usar ABI (Fenwick Tree) ni Segment Tree?

User avatar
isaac
Posts: 83
Joined: Mon Oct 26, 2015 6:20 pm
Gender: None specified

Re: 3526 - Unordered List

Postby isaac » Fri Jun 17, 2016 7:51 am

Marcelo, creo que el analisis que hiciste no es correcto. Yo inicialmente guardo los numeros en un arreglo y luego los voy agregando a la cola. El upper_bound, como es una busqueda binaria, me reporta un log2(N) de tiempo y yo hago eso N veces. Si se tiene en cuenta que hice N inserciones tambien, el resultado estaria rondando el n log n


Return to “Problem set”

Who is online

Users browsing this forum: No registered users and 1 guest