There exists an array with it's length (N) upto 7500. We can perform the following operation once: Select two integers l and r such that 1≤l≤r≤N . Reverse the order of the elements that are between the l -th element and the r -th element in the array, inclusive. Alice want to measure how effective this approach is. For each c=0…N , help Alice find the number of distinct operations (l,r ) that result in exactly c elements being checked. Two operations (l1,r1 ) and (l2,r2 ) are different if l1≠l2 or r1≠r2 . I've been trying to solve this problem, but could only come up with a very inefficient solution: N = int(input().strip()) a = list(map(int, input().strip().split())) b = list(map(int, input().strip().split())) ans = [0] * (N + 1) prefix = [0] * (N + 1) for i in range(1, N + 1): prefix = prefix[i - 1] + (1 if a[i - 1] == b[i - 1] else 0) for l in range(N): rev_a = a[:] for r in range(l, N): rev_a[l:r+1] = rev_a[l:r+1][::-1] aff = 0 for i in range(l, r + 1): if rev_a == b: aff += 1 total = ( prefix[l] + aff + (prefix[N] - prefix[r + 1]) ) ans[total] += 1 rev_a[l:r+1] = rev_a[l:r+1][::-1] print("\n".join(map(str, ans))) For the input N = 3, a = [1, 3, 2], and b = [3, 2, 1], the answer is [3, 3, 0, 0]. If Alice chooses (l=1,r=1 ), (l=2,r=2 ), or (l=3,r=3 ) then no elements will be checked. Note that those operations do not modify any of the elements' locations. The following operations result in one element being checked. For ranges l=1,r=2 : Alice reverses the order of the first and second elements so the new lineup will be [3,1,2] . The first element will be checked. For ranges l=2,r=3 : Alice reverses the order of the second and third elements so the new lineup will be [1,2,3] . The second element will be checked. For ranges l=1,r=3 : Alice reverses the order of the first, second, and third elements so the new lineup will be [2,3,1] . The third element will be checked. That was the sample input and output, and any assistance with optimizing my solution would be much appreciated. Continue reading...
