Hackerrank "New Year chaos" solution - permute sequence by swapping adjacent terms

Question

I was doing the Hackerrank "New Year chaos" problem. Here is the description:

It is New Year's Day and people are in line for the Wonderland rollercoaster ride. Each person wears a sticker indicating their initial position in the queue from 1 to n. Any person can bribe the person directly in front of them to swap positions, but they still wear their original sticker. One person can bribe at most two others.

Determine the minimum number of bribes that took place to get to a given queue order. Print the number of bribes, or, if anyone has bribed more than two people, print "Too chaotic".

The function is called with the desired permutation as its argument: minimumBribes([1,2,5,3,4]).

My solution below times out:

def minimumBribes(q):
    num_swaps = 0
    for i, p in enumerate(q):
        if p - (i+1) > 2:
            print('Too chaotic')
            return
        if i+1 != p:
            for j in range(min(i+1, len(q)), len(q)):
                if p > q[j]:
                    num_swaps += 1

While this solution, that I found online, passes:

def minimumBribes(q):
    bribes = 0

    for i, o in enumerate(q):
        cur = i + 1

        if o - cur > 2:
            print("Too chaotic")
            return
        
        for k in q[max(o - 2, 0):i]:
            if k > o:
                bribes += 1

    print(bribes)

I'm trying to understand what the difference is. Intuitive, my solution was "If an element is out of position, count how many elements behind it are smaller." I interpret the solution I found online as "If an element is out of position, count how many elements in front of it are larger."

I'd imagined these would be logically equivalent, but apparently not. Can anybody fill me in on what I'm missing?

Answer 1

Algorithm aside, it's easier to reason through the code if you:

• Use enumerate(q, 1) since the stickers are 1-indexed (to avoid the +1's)
• Use semantic variables

for position, sticker in enumerate(q, 1):
    ...

---

As for the algorithm:

I interpret the solution I found online as "If an element is out of position, count how many elements in front of it are larger."

But not all elements in front:

• Their version checks at most 2 positions ahead (their inner loop starts from max(sticker-2, 0), not from 0).
• Your version checks all elements behind (your inner loop goes to len(q)).

So the key difference is that they're taking advantage of the "chaotic" rule. There's no need to check beyond ±2 positions since no one can bribe more than twice.

This difference is especially noticeable when the bribing occurs near the front, e.g.:

q = [1, 4, 2, 3, 5, 6, 7, 8, 9, ..., n]
#       ^

Their algorithm:

[1] sticker: 1    check:
[2] sticker: 4    check:
[3] sticker: 2    check: [1, 4]
[4] sticker: 3    check: [4, 2]
[5] sticker: 5    check: [3]
[6] sticker: 6    check: [5]
[7] sticker: 7    check: [6]
[8] sticker: 8    check: [7]
[9] sticker: 9    check: [8]
...
[n] sticker: n    check: [n-1]

Your algorithm:

[1] sticker: 1    check:
[2] sticker: 4    check: [2, 3, 5, 7, 6, 8, 9, ..., n]
[3] sticker: 2    check: [3, 5, 7, 6, 8, 9, ..., n]
[4] sticker: 3    check: [5, 7, 6, 8, 9, ..., n]
[5] sticker: 5    check:
[6] sticker: 6    check:
[7] sticker: 7    check:
[8] sticker: 8    check:
[9] sticker: 9    check:
...
[n] sticker: n    check:

Now imagine thousands of bribers within n=1_000_000, and you can see how your version scales poorly.