0

I have given a queue initial positions increment by 1 from 1 at the front of the line to n 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 n = 8 and Person 5 bribes Person 4, the queue will look like this:1,2,3,5,4,6,7,8.

minimumbribes must print an integer representing the minimum number of bribes necessary to create the original queue, or Too chaotic if the line configuration is not possible. If no of bribes for a person exceeds to 2 then the line configuration is not possible.

minimumBribes has the following parameter(s):

  • q: an array of integers.
  • 1 <= n <= 100000.

Sample Input

2
5
2 1 5 3 4
5
2 5 1 3 4

Output

3
Too chaotic

Using the sorting logic I have just counted the person that comes early and are greater than following person. And it also prints the total no of bribes if the line configuration is possible else it prints Too chaotic message. 

static void minimumBribes(int[] q) {
    int count = 0; // Counts the no of bribes by an individual.
    int j;
    int total = 0; // Total no of bribes.

   loop1 : for(int i = 0; i < q.length; i++) {
      loop2 :  for(j = i; j < q.length; j++) {
            if(q[i] > q[j]) {
                count++;
                if(count > 2) {
                    System.out.println("Too chaotic");
                    break loop1;
                }

            }
            else if (q[i] <= q[j]) {
                total += count;
                count = 0;

            }
        }
    }
    if(count <= 2)    
    System.out.println(total);
}

The upper mentioned code runs perfectly for a small queue but if an array has a large size, It exceeds the fixed time limit for processing.

Improve this question

2 Answers 2

Reset to default
1

I just solved this in python to get a better understanding of the problem.

I decided to start with the last person in the queue because there are a number of things we can immediately say about this person:

  1. They can only bribe forward (i.e. they have no one behind them to bribe them)
  2. They cannot bribe to be more than two positions away from the "EOQ" [, where EOQ means end of queue or initial position of this person].

We can apply this rule to everyone starting from person N to person 1.

Pseudocode:

FOR PERSON in [N to 1]:
  P = PERSON
  IF (P MORE THAN 2 POSITIONS FROM INITIAL POS; OR P IS FURTHER BACK IN QUEUE):
    PRINT 'Too chaotic'
    RETURN

  FOR POS in [CURR_POS[P] to INIT_POS[P]]:     
     SWAP POSITION OF P AND PERSON_TO_THE_RIGHT_OF_P
     INCREMENT COUNT OF BRIBES BY 1

PRINT COUNT_OF_BRIBES

Notes

  • INIT_POS[P] refers to the initial position of the person before any bribes took place, so INIT_POS[PERSON_5] = 5

  • CURR_POS[P] refers to the current position of P at the start of the algorithm or after any swaps.

  • At the end of this algorithm, (assuming the bribes were not chaotic) the following invariant should hold: CURR_POS[i] == i. The reason is because all we are doing is moving all the people back to their original positions before any bribes took place.

Improve this answer
Sign up to request clarification or add additional context in comments.

4 Comments

As I have already mentioned earlier the code posted in my question will run perfectly fine but the issue is it's not that efficient. If you will notice closely your code will take more time for the processing because it has to do the swap and then count. This can be done without swapping. Keep in mind the queue size can be of 100000 elements.
@apoorvasharma it's interesting you say it takes more time because I actually wrote this in Python and submitted (on hackerrank) and it finished all 11 problems just fine. Also this one is O(N) whereas yours is closer to O(N^2). The inner loop that does the swapping only runs at most twice (per iteration), so the swapping is constant
" The inner loop that does the swapping only runs at most twice (per iteration), so the swapping is constant " how?? I have tried everything but it is not running in java only 7/11 test cases runs the same as earlier.
@apoorvasharma It has to do with the way we think about the last person in the queue. As I stated above, this person cannot be more than two positions from the end of the queue. Also this person cannot bribe any other person than the person ahead of them. But this also applies to the person ahead of the last person in the queue - they cannot bribe anyone behind them and they cannot be more than two positions ahead of their origin. So all we need to do is check the positions of everyone starting from the last person and move them to their original position while validating their bribes.
0 
static void minimumBribes(int[] q) {
    int count = 0; // Counts the no of bribes by an individual.

    int total = 0; // Total no of bribes.

   loop1 : for(int i = 0; i < q.length; i++) {
              if((q[i]-(i+1))>2){//original position i should be person i+1 
                System.out.println("Too chaotic");
                break loop1;
              }  
              else if((q[i]-(i+1))>0){
                  count=q[i]-(i+1);
                  total += count;
                  count = 0;
              }
            }



    if(count <= 2)    //not sure what dose this sentence do?
    System.out.println(total);
}

Is this what you ask? Not sure I understand you correctlly

Improve this answer

5 Comments

I think you haven't understood the question. You have to print the total no of bribes took place at last. i.e you have to count all the possible bribes and add up to the total.
You mean print how many bribes have happened, according to the input queue?
Yes. And your code is correct about "Too chaotic" part.
Then, what's wrong with another part? I calculate the count per person, and add the count to total.
It will always print 0 because you are not incrementing the count.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.