Could you please help me understand the logic behind the 'New Years Chaos' question?

Question

This is a coding challenge, but first I need to understand the problem and the solution from a purely thought/logical point of view.

I kind of worked out how to find the people in the list who have bribed their way forward, but I can't quite workout the logic behind finding out how many times they have bribed their way forward.

This is how much I know so far:

• For a queue of people that looks like this: 1, 2, 5, 3, 7, 8, 6, 4 I have figured out that by checking all the people in front of each person, the people with larger ID (number) would be those who have bribed their way forward.

So at the end, I get the following list of bribers: 5, 7, 8, 6

But how do I find how much times there has been a bribing. Basically, I need to know how much the briber has moved forward. That is the bit that I fail to grasp.

I can't simply compare their initial position to their final position. In the thought experiments I ran, some of the bribers ended up in their original queue slot because of other briber's movements.

This might help, an algorithm that I know works, but is not my solution so the problem still stands, however, this might help someone to understand the complete solution.

def minimumBribes(q):
    # variables
    # last index is 7
    lastIndex = len(q) - 1
    moves = 0
    swap = False

    # Check if too chaotic?
    for i, v in enumerate(q):
        if (v - 1) - i > 2:
            print('Too chaotic')
            return

    # figure out number of moves
    # 'i' is a range from 0 to 7
    for i in range(len(q)):
        # 'j' is in range from 0 to 7
        for j in range(lastIndex):
            if q[j] > q[j+1]:
                q[j], q[j+1] = q[j+1], q[j]
                moves += 1
                swap = True

        # check if any swap have occurred - if not it means the queue is sorted
        if swap:
            swap = False
            lastIndex -= 1
        else:
            print(moves)
            return
    print(moves)

Answer 1

It's important to note here that we're interested in the minimum number of bribes.

Firstly, note that a person can only move position in the queue if they either bribe someone, or accept a bribe. Other people's actions that don't involve them have no effect on their position. So since a person can only bribe a maximum of $2$ times, they can only be in $3$ possible positions. Their initial position ($k$), the position in front of their initial position ($k-1$) or the position two in front of their initial position ($k-2$). This is obviously considering the case where the queue length is $3$ or greater.

So now let's break the problem down into cases, by considering a queue of length $k$, and doing analysis on the position of person $k$ and using this position to break the problem into subproblems.

If person $k$ is at the back of the queue we can assume they never moved, as we're looking for a minimum, so just remove them and consider the ($k-1$)-person queue that's made of the first $k-1$ people in the queue we're looking at, as we can assume that person $k$ was never involved in any bribes.

If person $k$ is at position $k-1$, assume the sequence of bribes ended with them moving one step forward (this is fine as this doesn't affect the other bribes, so the order here doesn't matter). So the queue went from $(n_1,...,n_{k-1},k)$ to $(n_1,...,n_{k-2},k,n_{k-1})$ with this final step. So before this, person $k$ didn't move. So consider the $(k-1)$ person queue $(n_1,...,n_{k-1})$ and then add $1$ for the final bribe to the total that the subproblem gives us.

Finally, if person $k$ is at position $k-2$, assume the sequence ended with 2 bribes from them (this is fine again for the same reasons as above). So before these two bribes the queue looks like: $(n_1,...,n_{k-2},n_{k-1},k)$, and ends up looking like: $(n_1,...,n_{k-3},k,n_{k-2},n_{k-1})$. So consider the subproblem on the $k-1$ length queue $(n_1,...,n_{k-2},n_{k-1})$. Then add $2$ to the total that this subproblem gives us.

These three cases cover all possible legal queues. If person $k$ is at any other position, we know they must have bribed more than twice, which isn't possible. So the algorithm would return "too chaotic" in these cases.

Of course they could accept more bribes, but they'd only be able to move back as far as the final position in the queue. There's no way for them to be outside of these three positions, and we're only interested in the minimum possible, so we don't need to consider sequences of bribes that put us back into a position we've already been in, as these aren't minimal.

Answer 2

In your example of $1, 2, 5, 3, 7, 8, 6, 4$ you identified the bribers by the fact they are ahead of a smaller number

The number of bribes paid by a briber is at least (and optimally is equal to) the number of smaller numbers they are ahead of since they must have bribed them to get ahead of them, so you can conclude:

• $5$ is ahead of $3$ and $4$ so paid two bribes
• $6$ is ahead of $4$ so paid one bribe
• $7$ is ahead of $6$ and $4$ so paid two bribes
• $8$ is ahead of $6$ and $4$ so paid two bribes

so $7$ bribes were paid in total. A possible example is

Briber  Bribee  Pattern
                1   2   3   4   5   6   7   8
5       4       1   2   3   5   4   6   7   8
5       3       1   2   5   3   4   6   7   8
6       4       1   2   5   3   6   4   7   8
7       4       1   2   5   3   6   7   4   8
7       6       1   2   5   3   7   6   4   8
8       4       1   2   5   3   7   6   8   4
8       6       1   2   5   3   7   8   6   4