New Year Chaos
New Year Chaos
+ 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; }
+ 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)
+ 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.
+ 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; }
+ 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?
Sort 1771 Discussions, By:
Please Login in order to post a comment