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

|

288 Discussions

|

  • anw_g01
     + 0 comments

    Python solution:

    def minimumBribes(arr: list) -> None:
    """Count bribes from the perspective of the person being overtaken."""
    bribes = 0
    for i, sticker in enumerate(arr): 
        pos = i + 1     # queue position is 1-indexed
        # check for 2+ bribes:
        if sticker - pos > 2:
            print("Too chaotic")
            return
        # for each person, count no. of overtakes
        # only have to check previous two positions:
        for j in range(max(0, sticker - 2), i):    # not i - 2
            if arr[j] > sticker:
                bribes += 1                    
    print(bribes)

  • huyln_work
     + 0 comments

    This approach is mostly about the fact that we only need to count all people in front of us (who could bribe the current person and not more than two bigger than us) def minimumBribes(q): bribes = 0 

    for i in range(len(q)):
    if q[i] - (i + 1) > 2:  
        print("Too chaotic")
        return

    for j in range(max(0, q[i] - 2), i):
        if q[j] > q[i]:  
            bribes += 1

    print(bribes)

  • atthepark33
     + 0 comments

    This works ( in py)

    def minimumBribes(q):    
    # Write your code here
    n = len(q)
    total = 0
    sorted_q = list(range(1, n + 1))
    for i in range (n):
        if q[i] == sorted_q[i]:
            continue
        elif q[i] == sorted_q[i + 1]:
            sorted_q[i], sorted_q[i + 1] = sorted_q[i + 1], sorted_q[i]  
            total += 1
        elif q[i] == sorted_q[i + 2]:
            sorted_q[i + 1], sorted_q[i + 2] = sorted_q[i + 2], sorted_q[i + 1]  
            sorted_q[i], sorted_q[i + 1] = sorted_q[i + 1], sorted_q[i]  
            total += 2
        else:
            print("Too chaotic")
            return
    print(total)
    return

  • atthepark33
     + 0 comments

    This doesn't fully work

    def minimumBribes(q):    
    # Write your code here
    # q is an arr
    #q = q[::-1]
    sorted_q = sorted(q)
    total_count = 0
    def find_diff(q, target, idx):
        # this finds whats the idx of target in arr q
        # returns the diff of that and idx, if q < idx, ignore
        # if not, add diff to total count
        return q.index(target) - idx
        
    for i in range(len(q) - 1, -1, -1):
        if sorted_q[i] == q[i]:
            continue
        else:
            diff = -find_diff(q, sorted_q[i], i)
            if diff > 2:
                print("Too chaotic")
                return
            elif diff > 0:
                total_count += diff
    print(total_count)

  • vuhuutuan0
     + 0 comments

    My answer with Typescript, idea & explain includes.

    function minimumBribes(q: number[]): void {
    /**
     * Idea: Reverse thinking, complete the numbers behind first, count the number 
     * of permutations of the argument.
     */

    // 0. fn that swap number in array
    const swap = (s: number[], i: number) => { [s[i], s[i + 1]] = [s[i + 1], s[i]] }

    // 1. create fresh new array to be start, a hash to couting swaped
    let s = Array(q.length).fill(0).map((_, i) => i + 1)
    let swap_count = new Map<number, number>()

    // 2. loop [q], find and swap to complete right side to left side, counting too.
    mainloop: for (let qi = q.length - 1; qi >= 0; qi--) {
        while (true) {
            let si = s.indexOf(q[qi])
            if (si < qi) {
                let swap_num = s[si + 1]

                swap(s, si)
                swap_count.set(swap_num, (swap_count.get(swap_num) || 0) + 1)
                continue
            }
            break;
        }
    }

    // 3. calc swaping is chaos or not
    let counts = Array.from(swap_count.values())
    let chaos = counts.some(e => e > 2)
    let sum = counts.reduce((p, v) => p + v, 0)

    if (chaos) console.log('Too chaotic')
    else console.log(sum)
}