3379 - I Don't Want Strawberry

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

3379 - I Don't Want Strawberry

Post by ymondelo20 » 5 years ago

http://coj.uci.cu/24h/problem.xhtml?pid=3379


"Every problem has a simple, fast and wrong solution" OJ's Main Law. ;)
Top
User avatar
ymondelo20
Posts: 1968
Joined: 9 years ago
Location: Universidad de las Ciencias Informáticas
Gender: None specified
Contact:
Contact ymondelo20

Re: 3379 - I Don't Want Strawberry

Post by ymondelo20 » 5 years ago

A la i-ésima persona que quiera fresa siempre le va a tocar el i-ésimo helado de fresa en la pila, lo mismo para los helados de chocolate. Por tanto para cada persona se conoce la posición del helado en pila que le toca.

Luego, para saber cuántas personas que se encontraban atrás compraron delante de una persona en específico, hay que buscar cuántas personas que se encuentran atrás tienen posiciones para comprar sus helados por delante de la posición de la persona en cuestión. Este tipo de información se puede manejar fácilmente con un Árbol Binario Indexado (Binary Indexed Tree en Inglés, también conocido por Fenwick Tree). TopCoder ofrece un excelente tutorial sobre la mencionada estructura:
https://www.topcoder.com/community/data ... xed-trees/
"Every problem has a simple, fast and wrong solution" OJ's Main Law. ;)
Top
Post Reply

Return to “Problem set”