Наиболее эффективный способ реализации проблемы, основанный на большой последовательности и операции xor - PullRequest
Новая
       8

Наиболее эффективный способ реализации проблемы, основанный на большой последовательности и операции xor

0 голосов
/ 06 октября 2019

Мне дали следующие данные:

  1. n, где n - размер последовательности
  2. k - целое число
  3. последовательность A [0] A[1] A [2] ............ A [n-1]

Мне нужно выполнить для каждого i от 0 до (k-1) включительно

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

и выводим окончательный пробел последовательности, отделенные

Порядок дается: - 

 n<=10^4
 k<=10^12
 Ai<=10^7 for each i

Я применил наивный подход 

n,k=map(int,input().split())
arr=list(map(int,input().split()))
for i in range(k):
    t=i%n
    arr[t]=arr[t]^arr[n-(t)-1]
for i in arr:
    print(i,end=" ")

, но он показывает превышение лимита времени для больших тестовых случаев.

Хотелось бы получить эффективное предложение по реализации вышеупомянутого

1 Ответ

0 голосов
/ 07 октября 2019

**

Re: Обновлен подход к реализации проблемы

**

После объединения алгоритм предложил мой

@ AJNeufeld и @ vujazzman

Последовательность остается неизменной, если цикл выполняется до любого кратного (N*3)

, поэтому мы можем сохранить накладные расходы на запуск для всех значенийk

Скорее найдите ближайший кратный (n*3) to K, а затем run loop for remaining value from the found multiple to k

Примечание: - Нечетное число n дело должно быть обработано заранее заранее set A[n//2] = 0

, поэтому я придумал следующую реализацию: 

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)

Я создал несколько тестовых примеров, таких как: - 

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)

Теперь он отлично работает менее чем за1 сек

...