Пожалуйста, прочтите новое правило об ограничении использования AI-инструментов. ×

Блог пользователя AkeenL

How to iterate through hashmap efficiently?
Автор AkeenL, история, 3 года назад, По-английски

For problem BerPizza https://codeforces.me/contest/1468/problem/C the most easy solution is to store the key and values in a hashmap and loop through looking for either largest value or smallest index. This approach gives TLE and when I read the editorial they recommend a treeset but a treeset cannot store duplicate values. Is there a way to iterate through a map faster than o(n) or do I need to use priorityqueues for this problem?

  • Проголосовать: нравится
  • +1
  • Проголосовать: не нравится

»
3 года назад, # |
← Rev. 2   Проголосовать: нравится +13 Проголосовать: не нравится

Technically the fastest way to iterate over ALL elements of map is O(n) but you don't to iterate over all, you just need to know which is the one that will spend more money and the first one.

My approach was to maintain a priority_queue to retrieve the biggest value (you may as well use a set and get the biggest element with *set.rbegin() but i would recomend using a heap) to do it you need to maintain a pair with 2 informations, <money,index>, where money means the amount a costumer will spend and index means his position in line, you need to order it by the biggest money and if equal by who came first, you can create a custom function but instead i just set index to be negative, in this way if the money is equal, who came first will be on top.

I also used a set to maintain who was not served yet, with all the indexes that were not served yet.

When it asked to add someone to the line, i just insert {money,-index} on the heap and inserted index on the set;

When it asked to retrieve the one who came first, i just print *set.begin() and delete it from the set.

When it asked to retrieve the one who will spend more i just kept popping the top value of the heap until i found someone that was not served yet (which means that its index was on the set), printed its index, and removed it from the set.

Here's the link to my submission: https://codeforces.me/contest/1468/submission/111954036

Btw the complexity is O(nlogn) as every elements is inserted or removed 1 time from both the heap and the set, and insertion and removal are done in O(logn) in both data structures.

Hope it helped!

→ Ответить
»
3 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

I used two sets.

→ Ответить
»
3 года назад, # |
← Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

Seems like this question has been answered, but both Malheiros and tdpencil used C++ while AkeenL seems to use Java exclusively, so here's my Java solution for this problem: 111957362.

Basically, I made a custom class Customer which keeps track of the person's number, money, and whether they have already been served. Then I make two queues, one for Monocarp, the other for Polycarp. The Polycarp one needs to be a PriorityQueue, ordering by money from greatest to least, while for Monocarp, a regular queue suffices.

The rest of the code is pretty self-explanatory. For each query of type $$$1$$$, initialize a new instance of Customer and add it to both queues. For type $$$2$$$ or $$$3$$$, poll the corresponding queue until we meet the first customer that isn't already served, and serve them.

Note: The checker does not seem to distinguish between a space and a '\n', so you don't have to use a StringBuilder, just System.out.println() is good enough.

→ Ответить