Finding maximum homework grade ECOO 2018

Question

I'm trying to solve ECOO 2018 round 2(regionals) question 2 to prepare for the upcoming contest. Basically, in the question George has to achieve the maximum possible grade by completing the right assignments. Each assignment has a deadline and a weight value. I've came up with two solutions yet both only work for 7 of the cases and are extremely slow for the other 3. Here is the problem statement:

Problem 2: Homework

---

George has procrastinated too much on his N homework assignments, and now he is running out of time to finish them all.
Each of George’s N assignments has a weight that it contributes to his grade and a deadline in days from today. George will need one day to finish any of the assignments and he must complete an assignment before it’s deadline in order to submit it (he can’t complete it the day an assignment is due).
Help George figure out the order in which he should complete his assignments such that the total weight of the assignments he completes is maximized.

Input Specifications
DATA21.txt (DATA22.txt for the second try) will contain 10 datasets. Each dataset begins with an integer N (1 ≤ N ≤ 1,000,000).

The next N lines contain an integer D and decimal W (1 ≤ D ≤ 1,000,000; 0 < W ≤ 100), representing an assignment that has a deadline that is D days from today and a weight of W.

For the first seven cases, N ≤ 1000.

Output Specifications
For each dataset, output the maximum total weight of the assignments that George can complete, rounded to 4 decimal places (George is very meticulous about his grade).

Sample Input (Two Datasets Shown) Sample Output

3                                   3.0000
1 1.0                               17.0000
2 1.0
3 1.0
5
1 2.0  
1 1.0  
3 3.0  
7 10.0  
3 2.0  

(pixel raster of original Problem Statement (including it’s))

Solution #1: In this solution I adopted the elimination approach.
I store the deadline along with the assignments due in this day in a dictionary.
Then I sort all the assignments (keys) and iterate sequentially, each time picking the highest d assignments where d is the deadline (because you cannot complete more than 1 assignment in a day, 3 in 3 days and so on).
I estimated the complexity to be O(dlogd + dwlogw).

def main():
    from collections import defaultdict

    with open("DATA21.txt") as all_data:
        my_lines = iter(all_data.readlines())

    number_of_assignments = int(next(my_lines))

    homework_dict = defaultdict(list)

    for _ in range(number_of_assignments):
        d, w = [float(i) for i in next(my_lines).split()]
        d = int(d)
        # Setting up the dictionary

        homework_dict[d].append(w)


    all_deadlines = list(homework_dict.keys())

    all_deadlines.sort()

    # Algorithm starts here
    selected_assignments = []
    for deadline in all_deadlines:
        deadline_assignments = homework_dict[deadline]
        deadline_assignments.extend(selected_assignments)
        deadline_assignments.sort()

        difference = len(deadline_assignments) - deadline
        if difference < 0:
            selected_assignments = deadline_assignments
        else:
            selected_assignments = deadline_assignments[difference::]

    tot = sum(selected_assignments)
    new = format(tot, ".4f")
    print(new)

main()

Solution 2: In this solution I work directly,
I create a 2-dimensional list and sort in reverse order so that the weights are first.
Then I iterate through this list and look if it's possible to complete the current assignment by the deadline. I do this by creating a list of all the days and removing each deadline I already completed.
I estimate the complexity to be around O(nlogn + nd).

def main():
    with open("DATA21.txt") as all_data:
        my_lines = iter(all_data.readlines())

    n = int(next(my_lines))

    def take_second(elem):
        return elem[1]

    biggest = 0
    deadlines_weights_list = []
    for i in range(n):
        d, w = [float(x) for x in next(my_lines).split()]
        d = int(d)
        if d > biggest:
            biggest = d
        deadlines_weights_list.append([d, w])

    deadlines_weights_list.sort(key=take_second, reverse=True)

    possible_days = [day+1 for day in range(biggest)]

    total = 0
    for deadline, weight in deadlines_weights_list:
        # If there are no days left the code should be terminated 
        if len(possible_days) == 0:
            break

        while deadline not in possible_days:
            deadline -= 1
            # This means the only days left are really high, with much more time. 
            if deadline < possible_days[0]:
                break

        if deadline in possible_days:
            # One day cannot be used twice 
            possible_days.remove(deadline)
            total += weight


    total = format(total, ".4f")
    print(total)

main()

I apologize for posting two codes in one review, I'm more concerned about finding an algorithm that is fast enough for all of test cases rather than comparing this codes. Both solutions work for 7 test cases out of 10 but exceed the time limit for the other 3. Would appreciate any suggestions to optimize this solutions or a completely new way to solve this challenge.

Answer 1

Approach 1

def main():
    ... monolithic method ...

main()

Either this is a throwaway program, in which case you don't need to define main at all, or it isn't, in which case you should only call main() if __name__ == "__main__".

---

    from collections import defaultdict

    with open("DATA21.txt") as all_data:
        my_lines = iter(all_data.readlines())

    number_of_assignments = int(next(my_lines))

    homework_dict = defaultdict(list)

    for _ in range(number_of_assignments):
        d, w = [float(i) for i in next(my_lines).split()]
        d = int(d)
        # Setting up the dictionary

        homework_dict[d].append(w)

This looks to me like a method which should be factored out, so that there is clear isolation between the I/O and the processing.

I don't understand the use of float and int. Would it not be clearer to avoid the double-coercion with something like this?

        d, w = next(my_lines).split()
        homework_dict[int(d)].append(float(w))

---

    all_deadlines = list(homework_dict.keys())

    all_deadlines.sort()

I'm not sure what all_ adds to the name. deadlines works for me, or distinct_deadlines to be more explicit.

---

    # Algorithm starts here

See my previous point about factoring out methods.

---

    selected_assignments = []
    for deadline in all_deadlines:
        deadline_assignments = homework_dict[deadline]
        deadline_assignments.extend(selected_assignments)
        deadline_assignments.sort()

This is going to be doing a lot of sorts of already sorted data. That seems like a plausible bottleneck. I see at least three obviously better approaches:

1. Sort homework_dict[deadline] and then merge two sorted lists in linear time.
2. Use a priority queue of some kind for selected_assignments. Add homework_dict[deadline] to the queue and then pop it down to the desired length.
3. The asymptotically best option that I can see, although possibly not the fastest in practice, would be to append the new assignments and then use a linear time median finder to slice the merged list.

        difference = len(deadline_assignments) - deadline
        if difference < 0:
            selected_assignments = deadline_assignments
        else:
            selected_assignments = deadline_assignments[difference::]

difference is not an informative name. What does the difference actually mean? It's something like "number of assignments to discard". I might use excess as a name, or num_excess_assignments if I wanted to be more explicit.

---

It would be nice to see some comments in the code explaining why it's correct. I would say that having read it carefully a few times I find its correctness plausible, but I wouldn't be willing to guarantee it.

---

Approach 2

A lot of the comments (about structure, names, proof of correctness, ...) on approach 1 apply here too.

---

    possible_days = [day+1 for day in range(biggest)]

What is possible_days used for? in possible_days and possible_days.remove. This is a classic performance blunder (so don't feel bad, because you're far from the first person to stumble into it: clearly there are popular learning resources which should address this and don't). In general, the appropriate data structure for this use case is set, not list.

---

        while deadline not in possible_days:
            deadline -= 1
            # This means the only days left are really high, with much more time. 
            if deadline < possible_days[0]:
                break

However, it turns out that the use of possible_days is even more specialised than it seemed at first. Even if you replace the list with a set, this would still be a linear scan, and it doesn't need to be. You want the largest value smaller than a given one: if you keep the values in order then a binary chop will get there in logarithmic time rather than linear.

        if deadline in possible_days:
            # One day cannot be used twice 
            possible_days.remove(deadline)
            total += weight

However, updating the array needed for binary chop would not be logarithmic time. What you need is some kind of tree which allows searches and removals in logarithmic time. The access pattern is not going to be random, so to guarantee logarithmic time it probably needs to be a self-balancing tree, or some kind of self-pruning trie. I'm not aware of a suitable implementation in the standard library: I think you would have to write it yourself.

Actually, thinking about it some more, I reckon you could use an augmented union-find data structure to get amortised linear time. Initially each index (and -1 as a sentinel) is in a singleton set with associated data equal to the index. The search and delete becomes (pseudocode):

available = find(deadline).data
if available >= 0:
    total += weight
    union(available, available - 1)

ensuring that union chooses the smaller of the two associated data items.