Page 1 of 1

3526 - Unordered List

Posted: Thu Feb 18, 2016 8:23 pm
by ymondelo20

Re: 3526 - Unordered List

Posted: Sat Jun 11, 2016 10:30 pm
by frankr
Es posible resolver este problema en O(n log n) pero sin usar ABI (Fenwick Tree) ni Segment Tree?

Re: 3526 - Unordered List

Posted: Mon Jun 13, 2016 12:47 pm
by isaac
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.

Re: 3526 - Unordered List

Posted: Mon Jun 13, 2016 8:08 pm
by Marcelo
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.

Re: 3526 - Unordered List

Posted: Mon Jun 13, 2016 10:21 pm
by ymondelo20
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).

Re: 3526 - Unordered List

Posted: Tue Jun 14, 2016 9:17 pm
by frankr
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?

Re: 3526 - Unordered List

Posted: Fri Jun 17, 2016 7:51 am
by isaac
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