# New Year Chaos

# New Year Chaos

lsming + 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; }

amchap06 + 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)

xenialxerus + 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.

faogustavo + 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?

prog149 + 0 comments I saw this following code by Isming , so can someone explain the logic behind max(0, q[i] - 2) in nested for loop?

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; }

t_serban88 + 0 comments Who would have thought that knowing bubble sort would ever come in handy...

kangnahua + 1 comment Since there are usually no Python codes for these exercises, I would post mine in case other beginners don't know how to read Java or C++. New Year Chaos, like others said, can be solved by using the bubble sort algorithm. It seems that one can also use merge sort. Here's a Python bubble sort code for your reference:

def NewYearChaos(queue): lastIndex = len(queue) - 1 swaps = 0 swaped = False # check if the queue is too chaotic for i, v in enumerate(queue): if (v - 1) - i > 2: return "Too chaotic" # bubble sorting to find the answer for i in xrange(0, lastIndex): for j in xrange(0, lastIndex): comps += 1 if queue[j] > queue[j+1]: temp = queue[j] queue[j] = queue[j+1] queue[j+1] = temp swaps += 1 swaped = True if swaped: swaped = False else: break return swaps

Let me know if you have a faster or shorter solution!

ShafaetChallenge Author + 0 comments Your code is nice, I will add it in the editorial!

Btw, you can do swap in python in just one line

a,b=b,a

CompSocialSci + 0 comments For some reason comments are blocked from @Isming's excellent solution posting here.

This is a python 3 translation of his C++ code:

def minimumBribes(q): bribes = 0 for i in range(len(q)-1,-1,-1): if q[i] - (i + 1) > 2: print('Too chaotic') return for j in range(max(0, q[i] - 2),i): if q[j] > q[i]: bribes+=1 print(bribes)

mariogersbach + 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; }

sv_piedpiper + 0 comments I got 22 score out of 40. 4 testcases (testcases 6 to 9) are failing. Error message says Terminated due to Timeout. Any way to make it faster..

static void minimumBribes(int[] q) { //if value at (index+1), index starts at zero, minus the index > 2, then it is // a chaotic situation for(int i=0;i<q.length;i++){ if((q[i] - (i+1)) > 2){ System.out.println("Too chaotic"); return; } } //now we just need to count number of Swaps int swaps=0; for(int i=0;i< q.length;i++){ for(int j=i+1;j<q.length;j++){ if(q[i] > q[j]){ int tmp=q[j]; q[j]=q[i]; q[i]=tmp; swaps++; } } } System.out.println(swaps); }

Sort 986 Discussions, By:

Please Login in order to post a comment