Prioritise injured cats for treatment (dictionary/map search optimization Python and C++)

Question

I am once again attempting another CP problem, and I have ONCE AGAIN run into an optimization issue because of the time limit of one second: https://open.kattis.com/problems/doctorkattis

It is common for cats to have puncture wounds with different severity of infections. To help her local neighbourhood, Doctor Kattis decided to open a clinic! However, there are too many injured cats that come so she needs to prioritise her patients.

Given the names of N injured cats, their level of severity, and subsequent updates of their infection level, determine which cat Doctor Kattis needs to give her most attention to.

A cat with higher infection level has higher priority. If there are more than one cat with the same infection level, Doctor Kattis will give priority to the cat who arrived at the clinic first.

There will be 4 types of commands:

• ArriveAtClinic(catName, infectionLevel): This will be indicated by a starting integer 0 followed by catName and infectionLevel, e.g. 0 LUNA 31. catName is a String that is all UPPERCASE with length 1 to
  15 characters. The cat names are all unique. infectionLevel is an
  integer (30≤ infectionLevel ≤100).
• UpdateInfectionLevel(catName, increaseInfection): This will be indicated by a starting integer 1 followed by catName and
  increaseInfection, e.g. 1 LUNA 24. catName is guaranteed to have
  already arrived at clinic. increaseInfection is an integer (0≤
  increaseInfection ≤70). The infection level has a maximum value of
  100 and the update infection commands are given in such a way that
  the overall infection level of any cat will not exceed 100.
• Treated(catName): This will be indicated by a starting integer 2 followed by catName, e.g. 2 KITTY. catName is guaranteed to have
  already arrived at the clinic. catName leaves the clinic after being
  treated.
• Query(): This will be indicated by a single integer 3. Your job is to print the catName with the highest infection level or “The clinic is empty” if there are no more cats.

Input: The first line of input contains an integer N, denoting the number of commands (1≤N≤1000000). There will be up to 200000 cats. This will be followed by N commands as described above.

Output Each time the Query() command is encountered, the catName with highest infection level or “The clinic is empty” is to be printed in one line.

Subtasks:

• (30 points): 1≤N≤100, there will be up to 15 cats
• (30 points): 1≤N≤1000000, there will be up to 200000 cats. However, there is no call to UpdateInfectionLevel command and the cat with the highest infection level is always the first to be be treated, i.e.
  you can see this as Treated(Query())
• (40 points): 1≤N≤1000000, there will be up to 200000 cats. However, there will be frequent UpdateInfectionLevel commands and the cat with the highest infection level is not always the first to be treated

Explanation In the sample test case, we have N=15 commands:

• ArriveAtClinic(“LUNA”, 31)
• ArriveAtClinic(“NALA”, 55)
• ArriveAtClinic(“BELLA”, 42)
• Query(). You have to print out “NALA”, as she is currently the one with the highest infection level. To be precise, at the moment the order is:
  (NALA, 55), (BELLA, 42), (LUNA, 31).
• ArriveAtClinic(“KITTY”, 77)
• Query(). Now you have to print out “KITTY”. The current order is:
  (KITTY, 77), (NALA, 55), (BELLA, 42), (LUNA, 31).
• UpdateInfectionLevel(“LUNA”, 24). After this event, the one with the highest infection level is still KITTY with infectionLevel = 77. “LUNA” now has infection level = 31+24 = 55, but this is still 22 smaller than “KITTY”. Note that “NALA” also has infection level = 55 but “LUNA” is in front of “NALA” because “LUNA” arrived at the clinic earlier. The current order is:
  (KITTY, 77), (LUNA, 55), (NALA, 55), (BELLA, 42).
• Treated(“KITTY”). “KITTY” now has been treated ‘instantly’, and “KITTY” leaves Doctor Kattis’s clinic.
• Query(). Now you have to print out “LUNA”, as the current order is:
  (LUNA, 55), (NALA, 55), (BELLA, 42).
• Treated(“BELLA”). “BELLA” leaves Doctor Kattis’s clinic.
• Query(). The answer is still: “LUNA”. The current order is:
  (LUNA, 55), (NALA, 55).
• Treated(“LUNA”). “LUNA” leaves Doctor Kattis’s clinic.
• Query(). You have to answer: “NALA”. The current order is:
  (NALA, 55).
• Treated(“NALA”). “NALA” leaves Doctor Kattis’s clinic.
• Query(). You have to answer: “The clinic is empty”.

Sample Input 1

15
0 LUNA 31
0 NALA 55
0 BELLA 42
3
0 KITTY 77
3
1 LUNA 24
2 KITTY
3
2 BELLA
3
2 LUNA
3
2 NALA
3

Sample Output 1

NALA
KITTY
LUNA
LUNA
NALA
The clinic is empty

I put each cat into a dictionary/hashmap and set their names to the keys and their infection level as their value. Then I update them in order, delete them when they 'get treated' and return the key with the largest value when they ask a query. This is the fastest solution I can think of, and I'm pretty sure the Python program runs in O(n) time. After my Python program wasn't able to complete it in time, I spent some time translating it into C++, but that also didn't work. I'm not sure if that was because I barely know anything about C++ and I accidentally increased the time complexity with my for loops, or that there's a better solution.

My Python Program:

order = {}

n = int(input().strip())
for _ in range(n):
    line = input().strip().split()
    if line[0] == '0':
        order[line[1]] = int(line[2])
    elif line[0] == '1':
        order[line[1]] += int(line[2])
    elif line[0] == '2':
        order.pop(line[1])
    else:
        if len(order) > 0:
            print(max(order, key=order.get))
        else:
            print('The clinic is empty')

C++ Attempt:

#include <bits/stdc++.h>
using namespace std;

pair<string, int> findEntryWithLargestValue(map<string, int> sampleMap){
    pair<string, int> entryWithMaxValue= make_pair("", 0);
    map<string, int>::iterator currentEntry;
    for (currentEntry = sampleMap.begin();
         currentEntry != sampleMap.end();
         ++currentEntry) {
          if (currentEntry->second
            > entryWithMaxValue.second) {
  
            entryWithMaxValue
                = make_pair(
                    currentEntry->first,
                    currentEntry->second);
        }
    }
    return entryWithMaxValue;
}

int main(){
    int n;
    cin >> n;
    map<string, int> order;
    for (int i = 0; i < n; i++){
        int cmd, inf;
        string name;
        cin >> cmd;
        if (cmd == 0){
            cin >> name >> inf;
            order.insert(pair<string, int>(name, inf));
        }else if (cmd == 1){
            cin >> name >> inf;
            auto check = order.find(name);
            if(check != order.end()){
                check->second += inf;
            }
        }else if (cmd == 2){
            cin >> name;
            order.erase(name);
        }else{
            pair<string, int> query = findEntryWithLargestValue(order);
            if (query.first != ""){
                cout << query.first << '\n';
            }else{
                cout << "The clinic is empty" << '\n';
            }
        }
    }
    return 0;
}

I found another attempt using a heap, but that Python program didn't work either: https://github.com/jed1337/Kattis/blob/master/doctor_kattis.py

"""
A heap is used to order the patients by infection level, then arrival time at the clinic
"""


import heapq

INFECTION_INDEX = 0
ARRIVAL_INDEX = 1
NAME_INDEX = 2

command_count = int(input())

arrive_time = 0
patient_heap = []
for _ in range(command_count):
    command = input().split()
    opcode = command[0]
    if opcode == "0":
        _, name, infection = command
        # Store the infection in negative so that the most infected will be at the first
        heapq.heappush(patient_heap, [-int(infection), int(arrive_time), name])
        arrive_time += 1
    elif opcode == "1":
        _, name, increase_value = command
        for i in range(len(patient_heap)):
            if patient_heap[i][NAME_INDEX] == name:
                patient_heap[i][INFECTION_INDEX] -= int(increase_value)
                heapq.heapify(patient_heap)
                break
    elif opcode == "2":
        _, name = command
        for i in range(len(patient_heap)):
            if patient_heap[i][NAME_INDEX] == name:
                del patient_heap[i]
                heapq.heapify(patient_heap)
                break
    elif opcode == "3":
        if patient_heap:
            print(patient_heap[0][NAME_INDEX])
        else:
            print("The clinic is empty")

Am I missing another obvious solution? This probably isn't possible in Python since the solution statistics have no Python solutions in them, but there are many solutions in C, C++, Java, Kotlin, and Rust. If there is any way I could speed it up, please let me know.

Answer 1

I'm just reviewing the C++ code here.

Pass by reference where appropriate

Unlike Python, C++ by default passes parameters by value. This means that with your version of findEntryWithLargestValue(), a copy of the whole map is made every time you call it. Instead, pass by reference:

auto findEntryWithLargestValue(const std::map<string, int>& sampleMap) {
    std::pair<std::string, int> entryWithMaxValue{};
    ...
    return entryWithMaxValue;
}

Use range-for where appropriate

Make use of C++'s range-for for more concise code:

for (auto& currentEntry: sampleMap) {
    if (currentEntry.second > entryWithMaxValue.second) {
        entryWithMaxValue = currentEntry;
    }
}

But it can be simplified even further:

Consider using STL algorithms

The standard library comes with lots of useful algorithms that can operate on containers, for example it can find the largest element using std::max_element(). Using this, I would remove findEntryWithLargestValue() and just write this:

auto it = std::max_element(std::begin(order), std::end(order), [](auto &a, auto &b) {
    return a.second < b.second;
};

if (it != order.end()) {
    std::cout << it->first << '\n';
} else {
    std::cout << "The clinic is empty\n";
}

Add an index on infection level

The problem you have is that you have to be able to search both on a cat's name and on its infection level. The std::map you created is sorted on name, but to find the cat with the highest infection level, you are doing an expensive \$\mathcal{O}(N)\$ search. You can speed that up if you also have a map of cats sorted by infection level, so that you can find the next cat to treat in \$\mathcal{O}(1)\$ time.

Since unlike names, infection levels don't have to be unique, I would create a std::set with each element being a std::pair<string, int> repesenting a cat, and a custom comparator function that orders by infection level first and name second, like so:

static bool compare_by_infection(const std::pair<std::string, int> &a, const std::pair<std::string, int> &b) {
    return a.second != b.second ? a.second < b.second : a.first < b.first;
}

std::set<std::pair<std::string, int>, decltype(compare_by_infection)>
    order_by_infection(compare_by_infection);

It's a bit of work (it can be written more compact with recent versions of C++ though), but then looking up the cat with the highest infection level is just:

if (order_by_infection.empty()) {
    std::cout << "The clinic is empty\n";
} else {
    std::cout << order_by_infection.back().first << '\n';
}

Updating a cat's infection level is now a bit harder though; you have to remove it from order_by_infection, then change the level, then add it back.

Use a std::unordered_map to store cats by name

A std::map is not the best choice for order, as you don't need it to be sorted on name. A std::unordered map has faster insertion, removal and lookup (\$\mathcal{O}(1)\$ vs \$\mathcal{O}(\log N)\$ for std::map).

Use emplace() instead of insert()

Instead of:

order.insert(std::pair<std::string, int>(name, inf));

Write:

order.emplace(name, inf);

This avoids having to create a temporary std::pair, which avoids unnecessary copies.

Don't use <bits/stdc++.h>

You should not #include <bits/stdc++.h>. It is not standard C++. Just #include the proper header files, like <map>, <utility>, <string> and <iostream>.

Note that also using namespace std is considered bad practice, although it's valid C++. Coding challenge sites often teach you these bad habits, it saves a little bit of typing but it doesn't affect performance, and you might run into problems if you use these shortcuts in real programs.

Consider creating a struct Cat

A std::pair is a quick solution to pass two variables at once, but if you use them a lot you'll notice that you have to use .first and .second everywhere. It would be much clearer if you create a struct to group these variables, so you can give them proper names:

struct Cat {
    std::string name;
    int infection_level;
};

Answer 2

This probably isn't possible in Python since the solution statistics have no Python solutions in them

Now they do :-)

Some things about yours:

• Yours isn't \$O(n)\$ but rather \$O(nc)\$, where \$c\$ is the number of cats currently in the clinic. Because your max(order, key=order.get) goes through all \$c\$ cats to find the maximum. And \$c\$ can be as large as \$200000\$, so that's a problem.
• You don't need strip(), as split() takes care of that.
• max has a default parameter, so you can just do
  print(max(order, key=order.get, default='The clinic is empty'))
  instead of your if-else.

Now, how to make it fast enough to get accepted:

• Iterate sys.stdin instead of repeating input().
• Organize the cats in a heap.
• Some optimizations.

My solution (accepted in 0.76 seconds, a bit slower but cleaner than my fastest), notes below:

import sys, heapq

heap = [(0, 0)]
current = [heap[0]]
indexes = {}
names = ['The clinic is empty']

next(sys.stdin)
for line in sys.stdin:
    command, *args = line.split()
    if command == '0':
        name, level = args
        index = indexes[name] = len(names)
        names.append(name)
        entry = -int(level), index
        current.append(entry)
        heapq.heappush(heap, entry)
    elif command == '1':
        name, increase = args
        index = indexes[name]
        old_level = current[index][0]
        entry = old_level - int(increase), index
        current[index] = entry
        heapq.heappush(heap, entry)
    elif command == '2':
        name, = args
        index = indexes[name]
        current[index] = None
    else:
        while heap[0] is not current[heap[0][1]]:
            heapq.heappop(heap)
        print(names[heap[0][1]])

Notes:

• On my heap, I store pairs of (negated infection level, cat index). Negated level because Python's heapq module does min-heaps but I want larger levels first. And whenever a new cat arrives (command type 0), I give them a new index (1, 2, 3, etc). This ensures proper order among cats with the same infection level and allows fast heap entry comparisons. My names and indexes let me look up names and indexes from indexes and names.
• In current I keep, for every cat, a reference to its current heap entry. This allows me to recognize obsolete entries when answering queries (command type 3).
• I use a sentinel^(*) cat named 'The clinic is empty' which is perfectly healthy. It'll always be on the heap, so I don't need special checking code to test whether the clinic is empty.
  _{^(*) Darn, "feline" and "sentinel" share so many letters, but I couldn't come up with a nice portmanteau.}