Mfcttrf

This is a programming challenge.

I have been given the following input:

1. 
   $n$ where n is size of sequence


2. 
   $k$ is an integer


3. a sequence $A_0, A_1, A_2, ldots A_n-1$
   

I need to perform for each index from 0 to (k-1) inclusive

find a,b
where a = A[i % n] and b = A[n - (i % n) - 1]
then set A[i % n] = a XOR b

and output the final sequence, separated by spaces

The inputs are within the ranges:

$n leq 10^4$
$k leq 10^12$
$A_i leq 10^7$

I have applied the following naive approach

n,k=map(int,input().split()) 
arr=list(map(int,input().split())) #read input sequence and store it as list type
for i in range(k): #iterate over 0 to (k-1)
 t=i%n #module of i wrt n
 arr[t]=arr[t]^arr[n-(t)-1] #xor between two list elements and then set result to the ith list element 
for i in arr:
 print(i,end=" ") #print the final sequence

This code runs in 2 seconds when $K leq 10^6$, but it shows Time Limit exceeded for large test cases.

I am looking for an alternate suggestion for the problem

Now that that pesky "Not looking for the review of my code" is gone...

Step 1: White space

Follow the PEP 8 guidelines, specifically (but not limited to) put a space around operators and after commas:

n, k = map(int, input().split()) 
arr = list(map(int, input().split())) # read input sequence and store it as list type
for i in range(k): # iterate over 0 to (k-1)
 t = i % n # module of i wrt n
 arr[t] = arr[t] ^ arr[n - (t) - 1] # xor between two list elements and then set result to the ith list element 
for i in arr:
 print(i, end=" ") # print the final sequence

Much easier to read.

Step 2: Avoid multiple lookups

Python is an interpreted language, and the meaning of a line of code -- or even a fragment of code -- can change by the time the interpreter returns to execute the code as second time. This means the interpreter cannot truly compile the code; unless something is a well defined short-circuiting operation, every operation must be executed.

Consider:

arr[t] = arr[t] ^ arr[n - (t) - 1]

The interpreter must compute the address of arr[t] twice; once to fetch the value, and a second time to store the new value, because some side-effect which occurs during the execution of arr[n - (t) - 1] may change the meaning of arr[t]. In your case, arr is a list, and n and t are simple integers, but with user-defined types, anything can happen. As such, the Python interpreter can never make the following optimization:

arr[t] ^= arr[n - (t) - 1]

It is a tiny speed-up, but considering the code may execute $10^12$ times, it can add up.

Step 3: Avoid calculations

Speaking of avoiding work: because we know the length of the array is fixed, arr[n - 1] is the same as arr[-1]. So we can further speed up the line of code as follows:

arr[t] ^= arr[-1 - t]

Instead of two subtractions, we now have only one. Yes, Python has to index from the back of the array, which internally is going to involve a subtraction, BUT that will be an optimized, C-coded subtraction operation on ssize_t values, instead of subtraction on variable byte length integers, which must be allocated and deallocated from the heap.

Step 4: Printing space-separated lists

The following is slow:

for i in arr:
 print(i, end=" ")

This is faster:

print(*arr)

And for long lists, this may be fastest:

print(" ".join(map(str, arr)))

For a detail discussion, including timing charts, see my answer and this answer on another question.

Step 5: The Algorithm

Consider the list [A, B, C, D, E].

After applying a single pass of the operation on it (ie, k = n), you'll get:

[A^E, B^D, C^C, D^(B^D), E^(A^E)]

which simplifies to:

[A^E, B^D, 0, B, A]

If we apply a second pass (ie, k = 2*n), you'll get:

[(A^E)^A, (B^D)^B, 0^0, B^((B^D)^B), A^((A^E)^A)]

which simplifies to:

[E, D, 0, B^D, A^E]

A third pass, (ie, k = 3*n) gives:

[E^(A^E), D^(B^D), 0^0, (B^D)^(D^(B^D)), (A^E)^(E^(A^E))]

or:

[A, B, 0, D, E]

Now k does not need to be an exact multiple of n, so you'll have to figure out what to do in the general cases, but you should be able to use the above observation to eliminate a lot of unnecessary calculations.

Implementation left to student.

Any solution which does something $k$ times will be hopelessly slow. We have to make use of the structure of the problem here. Suppose $i<lfloor n/2rfloor$ and write $ a = A_i $ and $b= A_n-i$. Then each time through the list we execute $ a leftarrow awedge b $ and then $bleftarrow awedge b$. Lets record the values of $a $ and $b$ on each iteration of the loop, starting with values $x$ and $ y$ for $a$ and $ b$, respectively:

1. First $a leftarrow xwedge y$, then $b leftarrow (xwedge y)wedge y = x$
   


2. First $a leftarrow (xwedge y) wedge x = y$, then $bleftarrow ywedge x$
   


3. First $a leftarrow y wedge (ywedge x) = x$, then $bleftarrow x wedge (ywedge x) = y$
   

Notice that the effect of three such iterations is to do nothing at all. Therefore we can subtract any multiple of $ 3n$ from $k$ and not change the result. If you reduce $k$ mod $3 n$ before executing your original code, you should be good. (Actually we have to be a little careful to handle the case of odd $n$, because the middle element has to be handled specially. I leave this as an exercise).