2
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ From which site comes this problem? Are you interested in alternative implementations or a review of the code provided? Please take a look at the help center before answering the latter and modify your question accordingly. \$\endgroup\$ – Mast Oct 6 '19 at 18:12
  • \$\begingroup\$ Link to problem : codechef.com/OCT19B/problems/MARM \$\endgroup\$ – U_S02199 Oct 6 '19 at 18:13
  • \$\begingroup\$ I am looking for an alternative approach as i know my naive approach wouldn't work for large values of K \$\endgroup\$ – U_S02199 Oct 6 '19 at 18:14
  • 2
    \$\begingroup\$ @Mast Not looking for the review of my code is against the very purpose of this site: Code Review :) \$\endgroup\$ – dfhwze Oct 6 '19 at 18:17
  • 3
    \$\begingroup\$ For a next question, I give you this link (codereview.stackexchange.com/help/on-topic). I hope we can avoid ping-ponging your next question between sites :) \$\endgroup\$ – dfhwze Oct 6 '19 at 18:28
6
\$\begingroup\$

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.

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ One of the potential offenders is also the mod operation. It might (or might not) be faster to use an increment with an if after that. \$\endgroup\$ – Ilkhd Oct 6 '19 at 23:23
  • \$\begingroup\$ i have updated my implementation using the above algorithm getting right answer on most of the self-made cases but looks like one of case is not working properly. so Wrong Answer error \$\endgroup\$ – U_S02199 Oct 7 '19 at 14:16
  • \$\begingroup\$ I have rolled back your most recent edit. You may not edit your question to incorporate suggestions made in answers. See what should I do when someone answers my question in the help center. \$\endgroup\$ – AJNeufeld Oct 7 '19 at 14:27
  • \$\begingroup\$ sorry for the edit in question. I have posted my updated approach as a self -answer \$\endgroup\$ – U_S02199 Oct 7 '19 at 14:49
4
\$\begingroup\$

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/2\rfloor\$ and write \$ a = A_i \$ and \$b= A_{n-i}\$. Then each time through the list we execute \$ a \leftarrow a\wedge b \$ and then \$b\leftarrow a\wedge 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 x\wedge y\$, then \$b \leftarrow (x\wedge y)\wedge y = x\$
  2. First \$a \leftarrow (x\wedge y) \wedge x = y\$, then \$b\leftarrow y\wedge x\$
  3. First \$a \leftarrow y \wedge (y\wedge x) = x\$, then \$b\leftarrow x \wedge (y\wedge 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).

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ updated my implementation as per the algorithm suggested but still getting wrong answer on submission. It works perfectly on my self made test cases though \$\endgroup\$ – U_S02199 Oct 7 '19 at 14:19
0
\$\begingroup\$

**

Re:Updated implementation approach for the problem

**

After combining algorithm suggested my

@AJNeufeld and @vujazzman

Sequence remains same if loop is run upto any multiple of (N*3)

so we can save the overhead of running for all values of k

Rather find the closest multiple of (n*3) to K and then run loop for remaining value from the found multiple to k

Note:- Odd number n case to be handled separately in advance by set A[n//2] = 0

so i have came up with the following implementation:

for _ in range(int(input())):
    n,k=map(int,input().split())
    arr=list(map(int,input().split()))
    if n % 2 and k > n//2 :           #odd n case
        arr[ n//2 ] = 0
    rem= k % ( 3*n )
    closest_multiple_3n = ( k-rem )
    for i in range( closest_multiple_3n,k ):
        t=i % n
        arr[t] ^= arr[-1-t]
    print(*arr)

i have created some self made test cases like :-

t=1
n=11 k=9999999998
A[] = 20 7 27 36 49 50 67 72 81 92 99

output:- 20 7 27 36 49 0 67 72 81 92 119

note :- closest_multiple_3n = 9999999966
         rem = 32
        (20^92=119)

It works perfectly now

\$\endgroup\$
  • 2
    \$\begingroup\$ Code review is not intended to be used for collaborative coding to get things working (faster). While this post provides a (hopefully) improved code base, it's not a code review. I am converting it to a wiki answer (instead of deleting it). Please consider analyzing the actual performance of the code, and seeing if there is a different approach you can take. If it were me, I would benchmark your original code, then this code, and then possibly ask a new question if this revised code is faster, but not fast enough. \$\endgroup\$ – rolfl Oct 7 '19 at 16:36
  • \$\begingroup\$ okay i have updated my answer and the code in it works well !! \$\endgroup\$ – U_S02199 Oct 7 '19 at 16:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.