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.
  1. Prepare
  2. Algorithms
  3. Constructive Algorithms
  4. New Year Chaos
  5. Discussions

New Year Chaos

Sort by

recency

|

1944 Discussions

|

  • kearnssonnie321
     + 0 comments

    My solution- python 3

    def minimumBribes(q): # Write your code here bribes = 0 behind = 0 for number in q: if q.index(number) != (len(q)-1): #print(q.index(number)) #print(len(q)) behind = q[q.index(number)+1] if number > (q.index(number) + 1): difference = number - (q.index(number) + 1) bribes += difference #print("number:",number,"difference:", difference, "index:",q.index(number),"behind",behind)

            if difference >= 3:
            print("Too chaotic")
            return
    elif number > behind:

        bribes += 1
        if difference >= 3:
            print("Too chaotic")
            return


print(bribes)

  • kiraboibrahim
     + 0 comments

    Python Solution

    # Approach
# Start with a queue that has zero bribes - with everyone in order
# Move towards the current state of the bribed queue as you count the number of bribes done by someone
# If they exceed three, stop and print 'Too chaotic'
# Otherwise continue with bribing until you reach the final state of the bribed queue
numBribes = {}
positions = {}

rideQueue = None

def bribe(briberPos):
    global rideQueue
    
    bribeePos = briberPos - 1
    # Set the position of the briber to the one infront of him
    briber = rideQueue[briberPos]
    bribee = rideQueue[briberPos - 1]
    positions[briber] = briberPos - 1
    # Set the position of the bribed to the briber's position
    positions[bribee] = briberPos
    
    # Update number of bribes
    numBribes[briber] = numBribes.get(briber, 0) + 1

    # Switch places, bribe the person infront of the briber
    rideQueue[briberPos], rideQueue[bribeePos] = bribee, briber
    
    #print(rideQueue)
    
def isFinalPosBribed(finalPos, currPos):
    # currPos is the position currently held in the queue as the bribes take place
    return currPos > finalPos
    
    
def hasBriberExceededMaxBribes(briberId):
    return numBribes.get(briberId, 0) > 2

def minimumBribes(q):
    global rideQueue
    global numBribes
    global positions
    
    numBribes = {}
    positions = {}
    rideQueue = sorted(q)
    
    i = 0
    while i < len(q):
        finalPos = i
        briberId = q[i]
        unbribedPos = q[i] - 1
        # Get the current position of the person. Remember as the bribes take place, positions change, person 6 may endup infront of 4
        # Implying a person 4 can bribe 6 for as long as they are infront of them
        currPos = positions.get(q[i]) or unbribedPos
        if isFinalPosBribed(finalPos, currPos):
            #print(f"Person: {briberId} bribed")
            while currPos > finalPos:
                # Progress the person towards their bribed position
                bribe(currPos)
                currPos -= 1
                if hasBriberExceededMaxBribes(briberId):
                    print("Too chaotic")
                    return
        else:
            ...
            #print(f"Person: {briberId} didn't bribe")
        i+=1
    #print(rideQueue)
    print(sum(numBribes.values()))

  • gyrovorbis
     + 0 comments

    Irks me to no end that this question seeks to judge my abilities as a C++ developer, yet it cannot even be assed to use move semantics when copying freaking vectors around or to use std::vector<>::emplace_back() when inserting strings into a vector. or how about instead of copying all of these strings by value, you simply break them up using std::string_view?

    So you're essentially judging the speed at which I can decimate the heap. Nice.

  • maxfuller5
     + 0 comments

    C++ solution:

    void minimumBribes(vector<int> q) {
    int totalBribes = 0;

    for (int i = 0; i < q.size(); i++) {
        if (q[i] - (i + 1) > 2) { // If the difference between an elements' initial position and it's final position is greater than 2,
            // that means it moved to the left more than twice, which means it bribed more than twice. That means the line's Too Chaotic.
            cout << "Too chaotic" << endl;
            return;
        }

        // Start from one position ahead (in the line) of where q[i] *could* have started (i.e at an index of either index 0 or q[i] - 2, whichever is higher). 
        // Count how many people with a higher position than q[i] are in front of q[i] in the queue (i.e behind q[i] in the array), 
        // because each of those people must have bribed their way past q[i].
        for (int j = max(0, q[i] - 2); j < i; j++) {
            if (q[j] > q[i]) { 
                totalBribes++;
            }
        }
    }

    cout << totalBribes << endl;
}

  • pierinazaramella
     + 0 comments

    Hi. I did not understand the input. Are there more than one array and we need to promediate? and the 3rd expected output is just 4. And what happend with the two caothic string? Thanks!