• + 0 comments

    Here's my solution in Python. My basic idea is that when a student goes from being first to be visited by the teacher to being last, they gain len(t)-1 minutes, while all other students lose a minute. Instead of re-building a dictionary in every iteration, I use the fact that the student going from first to last gains len(t) minutes relative to all other students. Unless the student required 0 minutes, going from first to last guarantees that they will be able to finish their drawing, incrementing the count by 1. But then the count is decreased by the number of students who previously had just enough time. `from collections import deque def solve(t): completed = 0

    # create dictionary indicating how much extra time/excess time each student has if the teacher starts with student 1 (index 0 in Python)
    d = {}
    for i in range(len(t)):
        if (t[i]-i) not in d.keys():
            d[t[i]-i] = deque()
        d[t[i]-i].append(i)
        if t[i]-i <= 0:
            completed += 1
    
    # if all students already completed their drawing, no solution can be more optimal
    if completed == len(t):
        return 1
    
    max_completed = completed
    start_with = 1
    for i in range(len(t)-1):
        d[t[i]-i].popleft()
        if (t[i]-i-len(t)) not in d.keys():
            d[t[i]-i-len(t)] = deque()
        d[t[i]-i-len(t)].append(i)
        if t[i] > 0:
            completed += 1
        if -i in d.keys():
            completed -= len(d[-i])
        if completed > max_completed:
            max_completed = completed
            start_with = i + 2
    
    return start_with`