PROBLEM LINK:
Author: Kaushambi Gujral
Tester: Shivani Srivastava
Editorialist: Kaushambi Gujral
DIFFICULTY:
EASY
PREREQUISITES:
Bubble Sort
PROBLEM:
There are ‘n’ girls standing with a ticket in a queue, waiting for their chance to get a ride.
Some girls are thinking to bribe the person standing just in front of them.
After the bribe, the positions get swapped. Given the sequence of the queue after the bribe, you have to tell what is the number of bribes performed.
Note that, any girl cannot bribe more than 2 other girls, so in a case where this isn’t taken care of, print “Not Allowed”
QUICK EXPLANATION:
The answer is the number of inversions if for every element ‘i’, there are <=2 elements smaller than it on the right.
EXPLANATION:
Each person ‘i’ would be bribed by the people standing behind her as their chance would come later. We can keep the count of how many bribes have taken place by maintaining the number of inversions. In other words, apply the bubble sort algorithm, and count the number of swaps.
To check the condition that a girl cannot bribe more than 2 girls, here’s a trick. Subtract each element’s value from its index. If the result is more than or equal to 3,
you’ll know if this situation occurred. This can be computed in O(n) as in the worst case, you have to check for each element.
For example, if we have the following:
Given-
1 5 2 3 4
Now, while checking for each element in the given array, we see that ‘5’ appears at position 2.
5 - 2 = 3
this means that ‘5’ must have performed 3 swaps which was not allowed.
You could verify this using the following approach. The original array would have been
1 2 3 4 5
Here, ‘5’ appears at position 5. But in the given array, it appears at position 2.
AUTHOR’S AND TESTER’S SOLUTIONS:
The solution can be found here.