We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  • Hackerrank Home
  • Practice
  • Certification
  • Compete
  • Career Fair
  • Hiring developers?
  1. Practice
  2. Algorithms
  3. Constructive Algorithms
  4. New Year Chaos
  5. Discussions

New Year Chaos

Problem
Submissions
Leaderboard
Discussions
Editorial

Sort 1534 Discussions, By:

votes

Please Login in order to post a comment

  • lsming
    5 years ago+ 0 comments

    Since the question only asks the number of bribes, there's no need to really do a sorting, nor element swapping, nor "bubbling up" an element. All you need to do is to count the number of people who overtake a person.

    void calc(vector<int> q)
    {
        int ans = 0;
        for (int i = q.size() - 1; i >= 0; i--) {
            if (q[i] - (i + 1) > 2) {
                cout << "Too chaotic" << endl;
                return;
            }
            for (int j = max(0, q[i] - 2); j < i; j++)
                if (q[j] > q[i]) ans++;
        }
        cout << ans << endl;
    }
    
    1810|
    Permalink
  • amchap06
    2 years ago+ 0 comments

    No need to swap values, no need to loop backwards, no need to loop more than once. Just loop through each person in the queue and check two things: 1. Has this person moved more than two positions forward? 2. How many times has this person been bribed?

    In Python3:

    def minimumBribes(Q):
        #
        # initialize the number of moves
        moves = 0 
        #
        # decrease Q by 1 to make index-matching more intuitive
        # so that our values go from 0 to N-1, just like our
        # indices.  (Not necessary but makes it easier to
        # understand.)
        Q = [P-1 for P in Q]
        #
        # Loop through each person (P) in the queue (Q)
        for i,P in enumerate(Q):
            # i is the current position of P, while P is the
            # original position of P.
            #
            # First check if any P is more than two ahead of 
            # its original position
            if P - i > 2:
                print("Too chaotic")
                return
            #
            # From here on out, we don't care if P has moved
            # forwards, it is better to count how many times
            # P has RECEIVED a bribe, by looking at who is
            # ahead of P.  P's original position is the value
            # of P.
            # Anyone who bribed P cannot get to higher than
            # one position in front if P's original position,
            # so we need to look from one position in front
            # of P's original position to one in front of P's
            # current position, and see how many of those 
            # positions in Q contain a number large than P.
            # In other words we will look from P-1 to i-1,
            # which in Python is range(P-1,i-1+1), or simply
            # range(P-1,i).  To make sure we don't try an
            # index less than zero, replace P-1 with
            # max(P-1,0)
            for j in range(max(P-1,0),i):
                if Q[j] > P:
                    moves += 1
        print(moves)
    
    977|
    Permalink
  • xenialxerus
    4 years ago+ 0 comments

    Two points to bear in mind while solving this problem:

    • A person can bribe the one who is sitting just in front of him. The opposite is not possible.
    • A person can bribe atmost 2 different persons.

    Keeping this in mind, let's have a look at testcase-1.

    First case:

    Current position : 5 1 2 3 7 8 6 4
    Initial position : 1 2 3 4 5 6 7 8
    

    In the first test, the person-5 has occupied 1st seat. That means he has to bribe 4 persons in front of him to reach on the 1st seat So he violated the second rule here. So that answer is "Too chaotic" without further speculation.

    Second case:

    Current position : 1 2 5 3 7 8 6 4
    Initial position : 1 2 3 4 5 6 7 8
    

    So how did person-4 occupy at position 8? As per the rules, it's not possible for person-4 to bribe persons who are sitting behind him. Instead person 5, 6, 7 & 8 bribed person-4 as he is sitting infront of them. Here is the trasition from initial position to the current position.

    1 2 3 4 5 6 7 8  : 0 swap (initial)
    1 2 3 5 4 6 7 8  : 1 swap (5 and 4)
    1 2 3 5 6 4 7 8  : 1 swap (6 and 4)
    1 2 3 5 6 7 4 8  : 1 swap (7 and 4)
    1 2 3 5 6 7 8 4  : 1 swap (8 and 4)
    1 2 5 3 6 7 8 4  : 1 swap (5 and 3)
    1 2 5 3 7 6 8 4  : 1 swap (7 and 6)
    1 2 5 3 7 8 6 4  : 1 swap (8 and 6)
    

    Obviously no person violated the second rule here. Hence the output is minimum number of swaps 7.

    536|
    Permalink
  • mariogersbach
    3 years ago+ 0 comments

    There is a pretty simple solution using only a single for-loop.

    // Complete the minimumBribes function below.
    void minimumBribes(vector<int> q) {
        int totalBribes = 0;
        
        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;
            }
        }
        
        cout << totalBribes << endl;
    }
    
    356|
    Permalink
  • faogustavo
    5 years ago+ 0 comments

    Can some one help me? All tests are failing with me but i think i'm making everything allright. Here is my code

    let test = Int(readLine()!)!
    
    extern: for i in 1...test {
        let itemCount = Int(readLine()!)!
        var items = readLine()!.characters.split(" ").map{Int(String($0))!}
        var swaps = 0
        
        for j in 0 ..< items.count {
            let myPos = items[j]
            var dif = myPos - (j + 1)
            
            if dif < 0 {
                dif *= -1
            }
            
            if (dif > 2) {
                print("Too chaotic")
                continue extern
            }
        }
    
        var it = 0 // 0 = pos 1
        swapsLoop: while it < itemCount {
            for k in 0 ..< itemCount {
                if it + 1 == items[it] {
                    it += 1
                    continue swapsLoop
                }
    
                if items[k] == it + 1 {
                    var aux = items[k]
                    items[k] = items[k - 1]
                    items[k - 1] = aux
                    swaps += 1
                }
            }
        }
        print(swaps)
    }
    

    I bought one test case that is this:

    2
    8
    5 1 2 3 7 8 6 4
    8
    1 2 5 3 7 8 6 4
    

    And wait this response:

    Too chaotic
    7
    

    But the number 4 is too away of his place(both cases). He is 4 steps. It's more than 2, so it prints Too chaotic and i got the wrong anser. Can someone help me?

    228|
    Permalink
Load more conversations

Need Help?


View editorial
View top submissions
  • Contest Calendar
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy
  • Request a Feature