[keeping bribes minimum] New Year Chaos

 This question was particularly nasty for me, because the logic was so elegant, simple, yet elusive. My 3rd semester has started here at IIT Madras, and there is no mercy, so I haven't been coding too much recently. Maybe that's the cause, but a better reason might be that its a solid 65% success rate problem.

So, what's the deal?

My incorrect approach:

At every spot, Q[i] SHOULD have been equal to i + 1, but if it's not, the element there has either value greater or smaller than i + 1. We figure out the number of swaps by incrementing a swap counter by 

swapCounter += Q[i] - i - 1

only if this quantity is greater than zero, and then I reasoned that the ones where it is smaller than zero must have been swapped with some greater element. I thought that the smaller elements were the RESULT of a swap with an element strictly greater than itself. This logic misses cases like

3 2 1

My algorithm will totally ignore 2 and 1, but in reality in order to achieve such a configuration, we must  also switch 1 and 2 at some point, and that's where my algorithm fails. I realized this, and tried to work around this base solution to accommodate this case, but finally, failed.

The Correct Approach:

A very simple, elegant, no fancy math way of keeping track of swaps is to update 3 variables

expectedFirst, expectedSecond, expectedThird.

Initially, these are 1, 2, 3 respectively. However, we only update all 3, only the later 2, or only the 3rd one selectively depending upon the value we encounter at the queue.

    int expectedFirst = 1;
    int expectedSecond = 2;
    int expectedThird = 3;
    
    for (unsigned int i = 0; i < q.size(); ++i) {
        if (q[i] == expectedFirst) {
            expectedFirst = expectedSecond;
            expectedSecond = expectedThird;
            ++expectedThird;
        } else if (q[i] == expectedSecond) {
            ++totalBribes;
            expectedSecond = expectedThird;
            ++expectedThird;
        } else if (q[i] == expectedThird) {
            totalBribes += 2;
            ++expectedThird;
        } else {
            cout << "Too chaotic" << endl;
            return;
        }
    }

Ok. Let's break this down. What's the difference between this? 

At each step it compares the current number in the queue to what it expects to be. That is the smallest possible number, the next smallest, and so on.

When it encounters

3 2 1

1. it sees 3, updates totalBribes by 2, then sets the expected values to (1, 2, 4)

2. it sees 2, updates totalBribes by 1, then sets the expected values to (1, 3, 4)

3. it sees 1, updates totalBribes by 0  (as 1 == 1), then sets expected values to (3, 4, 5)

It needs to keep track of only 3 because the max number of bribes which can be given by any one person is 2, and one spot for the number itself.

There! Now that's elegance. I wonder when I will acquire such godlike abilities ;-;

I guess the correct way is "I never lose, I win, or I learn."

I've definitely learned today.