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.
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.
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
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 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: 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.