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. New Year Chaos
  2. Discussions

New Year Chaos

Sort by

recency

|

29 Discussions

|

  • davidsonekpokpo1
     + 0 comments

    Python 3 O(n) solution: Utilized sorting and then a dictionary for quick lookups:

    def minimumBribes(q):

    chaos = ""
    maxNum = len(q)
    allBribes = 0

    # Create a dictionary to track the indices of elements in the queue
    index_map = {value: i for i, value in enumerate(q)}

    while maxNum > 0:
        indxMaxNum = index_map[maxNum]
        while maxNum - (indxMaxNum + 1) > 0:
            if maxNum - (indxMaxNum + 1) > 2:
                chaos = "Too chaotic"
                break
            q[indxMaxNum], q[indxMaxNum + 1] = q[indxMaxNum + 1], maxNum

            index_map[q[indxMaxNum]] = indxMaxNum
            index_map[q[indxMaxNum + 1]] = indxMaxNum + 1

            indxMaxNum= index_map[maxNum]
            allBribes += 1
        if chaos:
            break
        maxNum -= 1
    print("Too chaotic") if chaos != "" else print(allBribes)

  • NaDan007
     + 0 comments

    How can the expected output from this q be 7?

    q = [1, 2, 5, 3, 7, 8, 6, 4]

  • BSharp
     + 0 comments

    Iterate from right to left, if you have seen 3 values lower than the current it's too chaotic, othewise add the seen list index to the bribe count.

    • j = 0, the value is smaller than any seen
    • j = 1, you have seen one value smaller
    • j = 2, you have seen 2 values smaller
    • j = 3 you have seen at least 3 values smaller, which is not valid.

    bisect used to maintain order, only need to keep the 3 smallest values seen.

    from bisect import bisect_left

def minimumBribes(q):
    
    bribes = 0
    seen = []
    for i in range(len(q)-1, -1, -1):
        v = q[i]
        j = bisect_left(seen, v)
        if j >= 3:
            print('Too chaotic')
            return
        bribes += j
        seen.insert(j, v)
        seen = seen[:3]
             
    print(bribes)

  • vdaons
     + 0 comments

    Python3: another O(N) (??? maybe ???)

    def minimumBribes(q):
    seen = set()
    bribes = {n: set() for n in range(0, len(q) + 1)}
    for n in q:
        seen.add(n)
        m = n - 1
        while m > 0 and m not in seen:
            bribes[n].add(m)
            m -= 1
        bribes[n] |= (bribes[m] - seen)
        if len(bribes[n]) > 2:
            return print('Too chaotic')
        
    print(sum(len(v) for v in bribes.values()))

  • alexander_zawad1
     + 0 comments

    Python - the key for me was to think about 'how many people to the right have numbers smaller than me' as those people must have been overtaken (bribed). Then it became a matter of doing the check in a fast enough way to handle the test cases...

    def minimumBribes(q):
    
    def find_smaller_than(n, sorted_list):
        # fast (enough) as we stop looking once n > n_bigger
        smaller_than = 0
        for number in sorted_list:
            if number < n:
                smaller_than += 1
            else:
                return smaller_than
        return smaller_than

    bribes = 0
    remaining_queue = sorted(q)
    for person in q:
        remaining_queue.remove(person)
        overtaken = find_smaller_than(person, remaining_queue)
        if overtaken > 2:
            print("Too chaotic")
            return
        bribes += overtaken
    print(bribes)