My code given below will produce the correct output but it tends to take way too much time with larger data thus timing out for some of the test cases. I've linked to the problem description here:
It's New Year's Day and everyone's in line for the Wonderland rollercoaster ride!
There are n people queued up, and each person wears a sticker indicating their initial position in the queue (i.e. 1, 2, ..., n - 1, n: with the first number denoting the frontmost position).
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 place in line. One person can bribe at most two other persons.
That is to say, if n = 8 and Person 5 bribes Person 4, the queue will look like this:
1, 2, 3, 5, 4, 6, 7, 8.Fascinated by this chaotic queue, you decide you must know the minimum number of bribes that took place to get the queue into its current state!
Note: Each Person X wears sticker X, meaning they were initially the Xth person in queue.
Input Format
The first line contains an integer, T, denoting the number of test cases. Each test case is comprised of two lines; the first line has n (an integer indicating the number of people in the queue), and the second line has n space-separated integers describing the final state of the queue.
Constraints
$$ 1 \leq T \leq 10 $$ $$ 1 \leq n \leq 10^5 $$
Subtasks
For 60% score $$1 \leq n \leq 10^3$$ For 100% score $$1 \leq n \leq 10^5$$
Output Format
Print an integer denoting the minimum number of bribes needed to get the queue into its final state; print Too chaotic if the state is invalid (requires Person X to bribe more than 2 people).
Sample Input
2 5 2 1 5 3 4 5 2 5 1 3 4
Sample Output
3 Too chaotic
Any help/advice/suggestion is welcome.
#!/bin/python3
import sys
inp0 = sys.stdin.read()
inp1 = inp0.split('\n')
T = int(inp1[0])
del inp1[0]
# Swaps the i'th and (i-1)'th elements and returns the list
def swap(intermediate_q,i):
intermediate_q[i],intermediate_q[i-1] = intermediate_q[i-1],intermediate_q[i]
return(intermediate_q)
# Increment bribes and total_bribes
def compute_bribes(bribes,total_bribes):
if(bribes+1==3):
return (-1,-1)
return (bribes+1,total_bribes+1)
for i in range(0,(2*T)-1,2):
n = int(inp1[i])
final_q = list(int(i) for i in inp1[i+1].split(' '))
initial_q = list(i+1 for i in range(n))
total_bribes,chaos_flag=0,0
for i in range(n):
bribes = 0
# If the position in the initial/transition queue is not equal to the position in the final queue
# final_q is the input against which swaps are made in my initial_q.
if(final_q.index(initial_q[i]) != initial_q.index(initial_q[i])):
index_in_initial_q = initial_q.index(final_q[i])
index_in_final_q = final_q.index(final_q[i])
while(index_in_initial_q != index_in_final_q):
initial_q = swap(initial_q,index_in_initial_q)
bribes,total_bribes = compute_bribes(bribes,total_bribes)
if(bribes == -1):
print("Too chaotic")
chaos_flag=1
break
index_in_initial_q-=1
if(chaos_flag == 1):
break
if (chaos_flag == 1):
continue
print(total_bribes)