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.
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.
$$ 1 \leq T \leq 10 $$ $$ 1 \leq n \leq 10^5 $$
For 60% score $$1 \leq n \leq 10^3$$ For 100% score $$1 \leq n \leq 10^5$$
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).
2 5 2 1 5 3 4 5 2 5 1 3 4
3 Too chaotic
Any help/advice/suggestion is welcome.
#!/bin/python3 import sys inp0 = sys.stdin.read() inp1 = inp0.split('\n') T = int(inp1) del inp1 # 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)