Saturday, January 26, 2019

New Year Chaos - Hacker Rank Solution

New Year Chaos - Hacker Rank Solution

It's New Year's Day and everyone's in line for the Wonderland rollercoaster ride! There are a number of people queued up, and each person wears a sticker indicating their initial position in the queue. Initial positions increment by  from  at the front of the line to  at the back.

Any person in the queue can bribe the person directly in front of them to swap positions. If two people swap positions, they still wear the same sticker denoting their original places in line. One person can bribe at most two others. For example, if and  bribes , the queue will look like this: .
Fascinated by this chaotic queue, you decide you must know the minimum number of bribes that took place to get the queue into its current state!
Function Description
Complete the function minimumBribes in the editor below. It must print an integer representing the minimum number of bribes necessary, or Too chaotic if the line configuration is not possible.
minimumBribes has the following parameter(s):
  • q: an array of integers
Input Format
The first line contains an integer , the number of test cases.
Each of the next  pairs of lines are as follows: 
- The first line contains an integer , the number of people in the queue 
- The second line has  space-separated integers describing the final state of the queue.
Constraints
Subtasks
For  score 
For  score 
Output Format
Print an integer denoting the minimum number of bribes needed to get the queue into its final state. Print Too chaotic if the state is invalid, i.e. it requires a person to have bribed more than  people.
Sample Input
2
5
2 1 5 3 4
5
2 5 1 3 4
Sample Output
3
Too chaotic
Explanation
Test Case 1
The initial state:
After person  moves one position ahead by bribing person :
Now person  moves another position ahead by bribing person :
And person  moves one position ahead by bribing person :
So the final state is  after three bribing operations.
Test Case 2
No person can bribe more than two people, so its not possible to achieve the input state.

New Year Chaos - Hacker Rank Solution
Let's consider an example for n = 5. Initially, the array was : [1, 2, 3, 4, 5].
Let's say after some number of bribes the array became : [1, 5, 4, 2, 3].
The  person moved from it's initial position to  position. For that, he must have bribed  people, which are  and . Also,  person moved from it's initial position to  position by bribing person  and person .
So the transformation goes something like this:
[1, 2, 3, 4, 5] -> [1, 2, 3, 5, 4] -> [1, 2, 5, 3, 4] -> [1, 5, 2, 3, 4] -> [1, 5, 2, 4, 3] -> [1, 5, 4, 2, 3]
Observation:
The number of people the  person (for ) has bribed is equal to the number of people on the right of that person with a value less than  (where array  represents the given array or final state of the people).
To get to the current position, each person has to bribe all the people who are behind them and have a smaller number. This is the same as counting inversions of an array.
So, if that number is greater than  for any index  we print Too chaotic else print the total sum of bribes.
Brute Force Approach:
Run two loops, and for every integer , we find the number of 's such that , where  and .
Time complexity: , but we can do better.
Optimised (Linear Time) Approach:
We start from the end of the array . If  is not equal to , where , then we know that the last element must have bribed and moved towards the left since it cannot move to the right being the last element. Also, we know that it will be present either in position  or . This is because if it is in the position left to , he must have bribed more than 2 people. In that case, we just print Too chaotic and terminate our program. Else if  is equal to  just swap the two elements and increment the counter by . Else shift  to  to  and put  equal to  and increment the counter by . Repeat the process until we reach the start of the array.
Note: For the answer to be a valid count, our condition that if  is not equal to , it will be present either in position  or  holds for all the elements because at every step we reorganize the array and make  equal to  for . So, if we are at index , we are sure that  is equal to  for .
Time complexity: .
Please check the code below for more clarity:

C++

void minimumBribes(vector<int> A) 
{
    int n = A.size();
    int cnt = 0;
    for(int i = n - 1; i >= 0; i--)
    {
        if(A[i] != (i + 1))
        {
            if(((i - 1) >= 0) && A[i - 1] == (i + 1))
            {
                cnt++;
                swap(A[i], A[i-1]);
            }
            else if(((i - 2) >= 0) && A[i - 2] == (i + 1))
            {
                cnt += 2;
                A[i - 2] = A[i - 1];
                A[i - 1] = A[i];
                A[i] = i + 1;
            }
            else
            {
                printf("Too chaotic\n");
                return;
            }
        }      
    }
    printf("%d\n",cnt);
    return;
}
Problem Setter's code:

Python 2

t = int(raw_input())

for _ in range(t):
    n = int(raw_input())
    arr = map(int, raw_input().split())
    org = range(n+1)
    pos = range(n+1)
    cnt = [0]*(n + 1)
    ans = 0
    invalid = 0
    
    for i in xrange(n - 1, -1, -1):
    
            if invalid:
                break
            
            # Get position where arr[i] should have been if no one bribed after this point
            
            oldp = pos[arr[i]]
            
            # Get the position where arr[i] currently is.
            
            newp = i + 1
            
            # oldp != newp indicates that even after this point, bribes took place
            # counting the number of furthter bribes that took place to bring arr[i] to i
            
            while oldp != newp:
                
                ans = ans + 1
                
                # arr[i] is at the right of org[oldp + 1] in the given array
                # that means org[oldp + 1] bribed arr[i] at some point
                # so increasing its count by 1
                
                cnt[org[oldp + 1]] += 1
                
                
                if cnt[org[oldp + 1]] > 2:
                    invalid = 1
                    break
                    
                # updating the original array to match the array after this bribe took place
                
                org[oldp], org[oldp+1] = org[oldp+1], org[oldp]
                
                
                # update the positions also due to the change 
                # caused by bribe that took place so far
                
                pos[org[oldp]] = oldp
                pos[org[oldp + 1]] = oldp + 1
                
                oldp = oldp + 1
                
    if invalid:
        ans = "Too chaotic"
        
    print ans

4 comments:

  1. Hello friend! I have read and understood your explanation.
    But in the optimised version where you wrote Ai is equals to Ai-1 I think the sentence is "Ai is equals to i-1".

    Congratulations for your amazing blog!
    Best regards

    ReplyDelete
  2. void minimumBribes(int q_count, int* q) {
    int minswap=0;int swap=0;int temp=0;int ct=0;int i=0,k=0;
    while(ctq[j+1])
    {
    temp=q[j];
    q[j]=q[j+1];
    q[j+1]=temp;
    swap+=1;
    minswap+=1;
    if(minswap>2)
    {
    printf("Too chaotic\n");
    return;
    }
    continue;
    }
    minswap=0;
    }
    i++;
    }
    printf("%d\n",swap);
    return;
    }


    This also works fine.

    ReplyDelete
  3. Firstly, thank you for the brilliant solution. Second, I have a few points to make:

    1) You are mutating the values in the array passed by reference to the function. This is bad form. You should clone the array and use the clone instead.

    2) It is unnecessary to swap when A[i-1] == i+1, simply making A[i-1] = A[i] will suffice; likewise, it is unnecessary to assign A[i] = i+1 when A[i-2] == i+1. You need only make A[i-2] = A[i-1] and A[i-1] = A[i]. Values to the right of i are never looked at again.

    3) You needn't visit A[0], since it is always going to be 1 when you get to it. This saves checking if i>1 in the if.

    4) The second return is extraneous. A void function will return implicitly;

    5) Too many extraneous parentheses. Order of operations works fine. Don't make it less readable.

    6) Why use a vector? The array never changes size. (I'm not that familiar with C++ so this may not be a well informed question)

    Here's my code in Java:

    static void minimumBribes(int[] q) {
    int[] a = q.clone();
    int bribes = 0;
    for (int i = a.length-1; i>0; i--) {
    if (a[i-1] == i+1) {
    a[i-1] = a[i];
    bribes++;
    } else if (i>=2 && a[i-2] == i+1) {
    a[i-2] = a[i-1];
    a[i-1] = a[i];
    bribes+=2;
    } else if (a[i] != i+1) {
    System.out.println("Too chaotic");
    return;
    }
    }
    System.out.println(bribes);
    }

    Thanks for the clear explanation. I probably wouldn't have understood the O(n) solution without it!

    ReplyDelete

Powered by Blogger.