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

3526 - Unordered List

Post by ymondelo20 » 2 years ago



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

User avatar
frankr
Posts: 50
Joined: 7 years ago
Location: Las Tunas
Gender: Male

Re: 3526 - Unordered List

Post by frankr » 2 years ago

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: 3 years ago
Gender: None specified

Re: 3526 - Unordered List

Post by isaac » 2 years ago

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: 2 years ago
Gender: None specified

Re: 3526 - Unordered List

Post by Marcelo » 2 years ago

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
Posts: 1968
Joined: 7 years ago
Location: Universidad de las Ciencias Informáticas
Gender: None specified
Contact:

Re: 3526 - Unordered List

Post by ymondelo20 » 2 years ago

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: 50
Joined: 7 years ago
Location: Las Tunas
Gender: Male

Re: 3526 - Unordered List

Post by frankr » 2 years ago

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: 3 years ago
Gender: None specified

Re: 3526 - Unordered List

Post by isaac » 2 years ago

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

Post Reply

Return to “Problem set”