We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Data Structures
  3. Advanced
  4. Kindergarten Adventures
  5. Discussions

Kindergarten Adventures

  • wpopielarski
     + 0 comments

    this problem easily could be awarded with 100 points or even promoted as hard.

    there are many things to consider:

    • build ranges of availability for every preschooler
    • think about situation where ranges are overlapping in cycles
    • walk twice around a table to close all cyclest
    def solve(t):
    ranges, n = [], len(t)
    for i, e in enumerate(t):
        if e >= n or e == 0:
            # skip those who need to much time
            # and those who had done their drawing
            continue
        # add range from start (second value is 0) to end (is 1)
        ranges.extend([((i-n+1+n)%n+1, 0), ((i-e+n)%n+1, 1)]) 
    ranges.sort(key=lambda e: (e[0], e[1]))
    # max opened ranges, currently open ranges
    # and first index of max opened range		
    max_, current, first_index = 0, 0, 1
    for _ in range(2): # walk twice arround a table
        for i, v in ranges:
            if max_ == current:
                first_index = min(i, first_index) # get lowest index for all maxes
            if v == 0: # beginning of range
                current += 1
                if max_ < current:
                    max_ = current
                    first_index = i # set new first index
            else:
                current -= 1
    return first_index